Prove that for ,
Note: There is a very simple solution (in terms of not requiring the use of theorems, not neccesarily in terms of length )
Moderator approved. CB
Note: LaTeX colour tags don't work now, but they used to, hence the words "red" and "black" in my LaTeX.
Note #2: Since that thread is kind of long, you can find the main part of the proof here
Denote by the -th Fermat Number. Observe that (1)
What happens? At each stage we take the rightmost term and factor it into: ; continuing this way gives the above factorization of .
Now we can write (1) in the following form: (2) .
Suppose that . Then by (2), , where is a positive integer. It follows that any common divisor of and must divide , and therefore is equal to or . Fermat Numbers are odd, so the only common divisor they have is .
Incidentally, the result of this problem is one of the proofs that there are infinitely many prime numbers....
Let's assume , then there's a prime that divides both and .
Thus and but without loss of generality -by symmetry- we may assume that and then which implies thus which is abusrd since both numbers are odd.
Remark: In fact one may observe that implies that the order of 2 module p is so applying this to both m and n yields