Number Theory

Discussion in 'Chit Chat' started by nitro, Feb 11, 2014.

  1. nitro

    nitro

    Of course, we should first prove that there are an infinite number of primes. This was proved more than two thousand years ago in one of the most beautiful elementary proofs in elementary mathematics in Euclid's Elements. So you can take it as a theorem:

    Theorem: There are an infinite number of primes.
     
    #11     Feb 25, 2014
  2. I think I can prove this one: In the array [0, 1, 2, 3, 4, ... infinity], every 4th element is divisible by four, thus not a prime. "Every 4th element" is like a cycle. That leaves 3 elements in between the cycle that could possibly be a prime. The second element is divisible by 2, so it's not a prime. The first and third elements could be prime, and does this really happen?

    [ ..., 16, 17, 18, 19, 20, ...]
    In this case, the first and third elements in the cycle, 17 and 19, are primes. And they leave modulos of 1 and 3.

    But it does not prove every number that leaves #1 or 3 (4) is prime, proved by this case:

    [..., 24, 25, 26, 27, 28, ...]
    Here the first and third elements in the interval are 25 and 27, they leave modulos of 1 and 3. But, they are not prime:
    25 / 5 = 5
    27 / 9 = 3
     
    #12     Feb 25, 2014
  3. OK, I'll try this one: Suppose the number line from the first prime, 2, to infinity. Next consider 2 as a generator, and all the numbers in the set generated by 2 are thus not prime. So, we can drop this set from the number line. This would reduce the number line by half. However, since the number line is to infinity, it would lead to:
    infinity * 0.5 = infinity (by defintion)

    Move to next prime for generator: 3. This would remove every third number from the number line after the removal of the 2's. This would lead to:
    infinity * 0.6667... = infinity (by definition)

    Move to next prime: 5. This would remove every ... I don't know, but it doesn't matter because infinity divided by any finite number is infinity, so there will always be another prime to move the generator forward to. Plus, note the reduction factor: .5, .6667-- it gets bigger, not smaller, so each remaining set has a larger share of the previous set, than the previous set had of its previous set. (Each child has a larger percent of the parent than the parent had of the grand-parent.)
     
    #13     Feb 25, 2014
  4. nitro

    nitro

    The original proof is very pretty:

    Suppose that you have a finite number of primes, p1, p2, p3...,pn. Form a new number where you multiply the list of finite of primes (the little p's) by each other, then add one to that number, P = (p1*p2*...*pn) + 1. Now it is easy to show that there must be a prime that is not in the list, since all the ones that are on the list would leave a remainder of 1 when you divide P by any of the little p's. So either P is prime, or if composite, there is a prime not on the list of little p's that divide it.

    This is a proof by contradiction. Assume finite list of primes=>contradiction.

    This proof however assumes another theorem, the Fundamental Theorem of Arithmetic:

    Theorem: Every integer greater than 1 either is prime itself, or is the product of prime numbers (where the order is not relevant).

     
    #14     Feb 27, 2014
  5. nitro

    nitro

    Ok here is the proof:

    Since X^3 - 1 has a factor of (x - 1),

    X^3 - 1 = (x - 1)(x^2 + x + 1) (you can verify this yourself)

    [This part is a bit technical but not really necessary: (x^2 + x + 1) cannot be further factored in the Ring of Integers.]

    Now we use the definition of a prime. A prime is a number that is divisible ONLY by 1 or itself. Since we have stated as a hypotheses that x^3 - 1 is prime, and we have factored it, look closely at the factorization.

    The (x - 1) part is easily set to 1. So

    (x - 1) = 1 so x must be 2.

    Plug 2 into the other side giving

    (x^2 + x + 1) = 2^2 + 2 + 1 = 7

    This is a really pretty proof. It is amazing that no matter how far out into infinity you go, no number of the form x^3 - 1, where x is a member of Z (Z is the standard name for the Ring of Integers) is a prime other than 7, with x = 2.

    Incredible
     
    #15     Feb 27, 2014
  6. nitro

    nitro

    Ok, here is another one, that is easier than the one above, but it uses a very similar technique:

    For what primes p, is 3 * p + 1 = x^2?

    Note that 5 works, 3 * 5 + 1 = 4^2.

    Can you prove that 5 is the only prime? Or are there an infinite number of primes such that 3 * p + 1 = x^2?
     
    #16     Feb 27, 2014
  7. nitro

    nitro

    Finally,

    Prove that x^n + y^n = z^n, where x,y,z are members of Q and n is a member of Z (Q is the Ring of Fractions, or the Rationals) has no non-trivial solutions.

    Doesn't seem that much harder than the above problems right? Well, it took 350 years to prove, with absolutely first rate mathematicians failing at it, until Wiles:

    <iframe width="640" height="360" src="//www.youtube.com/embed/7FnXgprKgSE?feature=player_detailpage" frameborder="0" allowfullscreen></iframe>
     
    #17     Feb 27, 2014
  8. start with algebra:
    3p + 1 = x^2

    solve for p and factor:
    3p = x^2 - 1
    p = (x^2 - 1) / 3
    p = [(x + 1)(x - 1)] / 3

    rewrite to show the point:
    p = (x + 1) * [(x-1) / 3]

    for any value greater than x = 4, the term (x-1) / 3 (with a result in Z the Ring of Integers) will be greater than 1, leading to p having factors other than one and itself

    Therefore: 5 is the only prime
     
    #18     Feb 27, 2014
  9. If it's not too much trouble, what about my proof of infinite primes? I'm sure there's always a standard proof that a mathmetician came up with, but I'm interested to see how my amateur reckoning and logic stood in comparison.
    Did it succeed in proving, fail in proving, incompletely prove, or somewhere in between like 'proved successfully but too long and convoluted'?
     
    #19     Feb 27, 2014
  10. Carl K

    Carl K

    1^3 - 1 = 0

    One is the first Fibonacci number, but not a prime number at all.

    Two is the only even prime, and raising any other prime to a power
    and subtracting 1 from it would make it even and a composite.
    I know this is not proof but logic.
     
    #20     Mar 1, 2014