Math Olympiad problem (Oct-3)

[sirio11]

Prove that if n is an odd number, n divides 2^(n!) - 1

[Double Ice]

gcd(n,2) = 1, so 2^(n-1) = 1 mod n by Fermat's little theorem. But n! is a multiple of n-1.

[sirio11]

WHITE !!!!!!!!!!!!!!!!!

Fermat's is only true for primes

[Usual]

OK, so can we use Euler's theorem:
2^phi(n) = 1 mod n
where phi(n) is Euler's Totient function
(if n has prime representation p_1^k_1...p_r^k_r
then phi(n) = (p_1-1)p_1^(k_1-1)...(p_r-1)p_r^(k_r-1))
Does phi(n) divides n! ?
We need to check all the (p_i-1)'s and p_i^(k_i-1)'s are distinct.
Well clearly the p_1^(k_i-1)'s are distinct, and all the (p_i-1)'s are distinct.
So can (p_i-1) = p_j^(k_j-1) for any i,j?
No since all the p_i's are odd.

[TomCowley]

<font color="white"> This is a little sloppy, but it should do. When z=xy, 2^z-1 can be factored as (2^x - 1)(Sum i = 0 to y-1 of 2^xi). In our case, z=n!, so we can choose any 1&lt;=x&lt;=n, so our problem can be solved by proving that there exists a q&lt;=n such that 2^q-1 is divisible by n (except for the trivially true n=1 case), which is equivalent to 2^q==1 mod n. Euler's theorem states that a^phi(n)==1 mod n if a and n are coprime, and since 2 (use a=2) and n are coprime (n is odd), and phi(n)&lt;=n, we're done. </font>

[Usual]

Sorry for non-whiteness of my earlier reply. Can someone edit it?
Tom you made a small mistake, your last statement isn't true.

[TomCowley]

PM me what's wrong with it. I don't see what's wrong with the statement of the theorem, the relation of 2 and n, or the relation of the function and n.

[bigpooch]

This is easy. n=1 is trivial. If n is odd, and n&gt;=3, then
n and 2 are coprime and so by Euler's theorem,

2^phi(n) is congruent to 1 (mod n).

where phi(n) is the totient function of n; thus, it is an
integer between 1 and n inclusive, or obviously divides n!.
Thus, n! = k phi(n) for some integer k and thus,

2^(n!) = 2^(k phi(n)) = (2^phi(n))^k.
Since 2^(phi(n)) is congruent to 1 (mod n), 2^(n!) is
congruent to (1)^k = 1 (mod n).

[Usual]

Sorry Tom, you are completely correct! [img]/images/graemlins/blush.gif[/img]

[sirio11]

Pretty good !

Now try to solve it guys for n^2, n odd

This is, prove n^2 divides 2^(n!) - 1