|
#1
|
|||
|
|||
Math Olympiad problem (Oct-3)
Prove that if n is an odd number, n divides 2^(n!) - 1
|
#2
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
gcd(n,2) = 1, so 2^(n-1) = 1 mod n by Fermat's little theorem. But n! is a multiple of n-1.
|
#3
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
WHITE !!!!!!!!!!!!!!!!!
Fermat's is only true for primes |
#4
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
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. |
#5
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
<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<=x<=n, so our problem can be solved by proving that there exists a q<=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)<=n, we're done. </font>
|
#6
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
Sorry for non-whiteness of my earlier reply. Can someone edit it?
Tom you made a small mistake, your last statement isn't true. |
#7
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
Pretty good !
Now try to solve it guys for n^2, n odd This is, prove n^2 divides 2^(n!) - 1 |
#8
|
|||
|
|||
Re: Math Olympiad problem (Oct-3)
This is easy. n=1 is trivial. If n is odd, and n>=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). |
|
|