Interesting and difficult (for me anyway) combinatorics problem

[MelchyBeau]

I just took a combinatorics test and had this problem

for n greater than or equal to 3 and odd

show that there is at least one number in the set

{(2^1)-1, (2^2)-1, .... ,(2^n-1)-1} which is divisible by n

Melch

[AlphaWice]

By Euler's Totient Theorem: (Mathworld Link (http://mathworld.wolfram.com/EulersTotientTheorem.html))

2^(totient of n) = 1 mod n

Since the totient of n is between 1 and n-1 inclusive, we are done.



edit: I think this page has the proof of the theorem. Page (http://mcraefamily.com/MathHelp/BasicNumberCoprimesTotientTheoremEuler.htm)

[bigpooch]

If you are familiar with abstract algebra, or number theory,
there will be at least two of the numbers in the sequence

2^1, 2^2, 2^3, ..., 2^n

that have the same remainder when divided by n since 2 and
n are relatively prime and hence there is some j and k, j>k,
with j and k between 1 and n inclusive for which 2^j - 2^k
is divisible by n (the pigeon-hole principle applied to
congruence classes modulo n). Dividing by 2^k (which is
coprime with n), 2^(j-k) - 1 must be divisible by n.


If the above is not clear:


A congruence class is simply the set of integers that have
the same remainder when divided by n (here, all you know is
that n is odd and >=3), so there are n congruence classes.
Usually, [0] denotes the class of integers divisible by n,
and [a] denotes the congruence class that contains a. The
congruence classes [0], [1], ... [n-1] partition the
integers into disjoint sets. Note that the difference of
two elements in the same congruence class is a multiple of
n.

The n numbers

2^1, 2^2, ..., 2^n are all NOT divisible by n (since n is
odd) and hence two of these MUST be in the same congruence
class which essentially means that there are two of these,
2^j and 2^k for which 2^j - 2^k is a multiple of n and the
result follows immediately.


There is a well-known theorem of Euler that number theorists
know:

if a and n are relatively prime integers, and n>=2

a^phi(n) - 1 is divisible by n

where phi is the Euler totient function [the number of
integers between 1 and (n-1) that are relatively prime
to n] and phi(n)<= (n-1) for all n [phi(n) = n-1 iff n
is prime].

Thus, the result follows also immediately from the theorem.