Number Theory

1. Let x and y be integers. Prove that 2x + 3y is divisible by 17 iff 9x + 5y is divisible by 17.
Answer:-
17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒17 | (9x + 5y),
and conversely, 17 | (9x + 5y) ⇒ 17 | [4(9x + 5y)], or17 | (36x + 20y) ⇒ 17 | (2x + 3y).

Example 1.3. Suppose that a1, a2, . . . , a2n are distinct integers suchthat the equation (x − a1)(x − a2)· · ·(x − a2n) − (−1)n (n!)2 = 0 has an integer solution r. Show that 

r =a1 + a2 + · · · + a2n/2n

Useful facts:-

1. Bertrand’s Postulate. For every positive integer n, there exists a prime p such that n ≤ p ≤ 2n

2.  Let 0 < a1 < a2 < · · · < amn+1 be mn + 1 integers. Prove that you can select either m + 1 of them no one of which divides any other, or n + 1 of them each dividing the following one.

(1966 Putnam Mathematical Competition) 

Solution. For each i, 1 ≤ i ≤ mn + 1, let ni be the length of the longest sequence starting with ai and each dividing the following one, among the integers ai, ai+1, . . . , amn+1. If some ni is greater than n then the problemis solved. Otherwise, by the pigeonhole principle, there are at least m + 1values of ni that are equal. Then, the integers ai corresponding to these nicannot divide each other.