Number Theory

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.
 
nitro said:
...So the above theorem says that all primes leave a remainder of 1 or 3 when divided by 4.
....
More...

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
 
nitro said:
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.
More...

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.)
 
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).

zedDoubleNaught said:
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.)
More...
 
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
 
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?
 
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>
 
nitro said:
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?
More...

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
 
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'?
 
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.
 
You must log in or register to reply here.
Back
Top