Some Proofs, Relative Prime and Egyptian Fractions

[Derek1148]

I could use some help with the following proofs:

1. Prove that 2^(2^n) + 1 and 2^(2^m) + 1 are relatively prime where m and n are integers.


2. Essentially a proof of egyptian fractions. Show that for any m,n that m/n = 1/R1 + 1/R2 + .... + 1/Rk.


Thanks in advance.

[AlphaNumeric]

They are known as Fermat Primes.

There's a STEP II question from 2002 (question 5?) which walks you through how to prove they are relatively prime due to them obeying some iterative relation which I cannot currently remember. I had to do that question during an exam, hence how I remember 'Fermant Primes' but I dont remember the relation unfortunately.

Equation (5) here might be useful.

[mr_homm]

Is the second question not trivial? There must be some further restriction on the possible values of the R's, or maybe of k, because otherwise you could just use 1/n + 1/n + ... + 1/n for m terms.

I think some clarification is necessary before the problem can be approached successfully.

As for the first problem, I think there is a non-iterative proof:

Let k be a common factor of the two numbers. Then 2^(2^n)+1 = 0 mod k, and 2^(2^m)+1 = 0 mod k. Therefore, 2^(2^n) = -1 mod k, and 2^(2^m) = -1 mod k. Now suppose n>m; then 2^(2^n) = (2^(2^m))^(2^(n-m)). Reducing modulo k gives (-1)^(2^(n-m)) = -1. But the exponent here is even unless n=m, and (-1)^(even) = 1, both in the usual integers and in modular arithmetic. Hence, k can be a common factor of the two given numbers only if n=m or if -1=1 mod k. The case n=m is explicitly disallowed (of course, since then the two numbers are equal and the theorem would be trivially false). The equation -1=1 mod k can only be true if 1+1=0 mod k, so k must be 2. But both the given numbers are obviously odd, so 2 is not a factor of either of them. This eliminates all possible common factors. QED

Hope this helps!

--Stuart Anderson

[Derek1148]

Thanks.

This post has been edited by Derek1148 on Sep 17 2007, 08:02 PM