Number Theory Solutions

1. Suppose by contradiction that there exists some integer a such that 2ª -1 = 0 mod (a) (a is obviously odd because it divides an odd integer 2ª -1). Let p be the smallest prime which divides a, so it follows that 2ª -1 = 0 mod (p) but we know that Ord2(p) / p-1 (by Fermat's little theorem), and also Ord2(p)/ a, contradiction because p is the smallest prime which divides a.

2. The first part is trivial. For the second part suppose that a is composite and take p the smallest prime such that p / a. So by the statement a divides all the binomial coefficients and in particular the one involving p which is equal to a! / p! (a-p)! That is ((a-p)+1)((a-p)+2)........(a) / p! Let a=kp for some integer k. Then a / {((a-p)+1)((a-p)+2)........(a-1 )k /( p-1)!} , but since (a,a-p+1)=(a,a-p+2)=..............=(a,a-1)=1 then a / k. This is a contradiction.

3. Let S={x1,x2,.....,xN} be a set of N integers . Consider y1=x1 , y2=x1+x2, ...... yN=x1+x2+.....+xN, if some yi is 0 mod (N) we are done, so suppose not. Then we get N numbers yi and N-1 residues mod (N), so by the pigeonhole principle there exist i and j such that yi = yj mod (N) and we are done.

4. Consider the first n primes , P1,P2, ...Pn. By the Chinese Remainder Theorem there exists some Y which is the solution of the system of congruences: Y = -1 mod (P1²) , Y = -2 mod (P2²),....Y = -n mod (Pn²) (since if "i" is different from "j" , (Pi², Pj²)=1) And so the n consecutive numbers Y+1,..., Y+n do the job.

5. If one of the n+1 numbers is 1 we are done. So suppose not and consider the n subsets: {2,3}, {4,5},..., {2n,2n+1} , now we have n subsets and n+1 integers which are in these subsets, then by the pigeonhole principle there exist two distinct integers which are in the same subset, which means that they are consecutive and so relatively prime.

6. Let S = {x(1),x(2),..., x(n+1)} be a set of n+1 integers selected from {1,2,.......2n}. Then for any i consider x(i) = (2^ri)*yi where yi is odd. Since there are just n odd numbers in the set {1,2,...,2n} then by the pigeonhole principle there exist two distinct integers i and j such that yi=yj, so without any loss of generality suppose that ri >= rj then you get x(j)/x(i).