Math Olympiad problem (Oct-3)

[bigpooch]

This is easy to see using the slightly sharper result that

2^((n-1)!) is congruent to 1 (mod n).

[ By Euler's theorem, since phi(n) <= n-1, using the same
argument as before. ]

Then, 2^((n-1)!) = 1 + an for some integer a. By the
binomial theorem,

2^(n!) = (2^((n-1)!))^n = (1+an)^n
= 1 + n(an) + C(n,2)(an)^2 + higher powers of n
= 1 + n^2(b) for some integer b.