Number Theory Problems

Questions: 1. Which of the following diophantine equations cannot be solved?why? (a) 6x + 51y = 22 (b) 33x + 14y = 115 2. It has been conjectured that there are infinitely many primes of the form n^2 - 2. Exhibit five such primes. 3. Find all primes that divide 50! 4. A conjecture of Lagrange asserts that every odd integer greater than 5 can be written as a sum p1 + 2p2, where p1 and p2 are both prime. Confirm this for all odd integers through 75. 5. Prove: If ca congruent to cb(mod m) , then a congruent to b(mod m/d) where d=(c,n). 6. What is the remainder when the sum 1^5 + 2^5 + 3^5 + 4^5 + ........+ 99^5 + 100^5 is divided by 4? 7. Prove that if a is an odd integer, then a^2 is congruent to 1(mod8) Answers: ) (a) cannot be solved, since for any choice of x,y integers, the number 6x+51y is a multiple of 3 (since 6 and 51 are!), but 22 is not! (b) can be solved, since 33 and 14 are coprime ==> there exist x,y integer s.t. 33x+14y=1 ==> 33(115)+14(115)=1*115=115 (actually, 33(3)+14(-7)=1 so 33(115)+14(-805)=115). 2)For n = 2, 3, 5, 7, 9 we get 2, 7, 23, 47, 79, all of them prime! 3)As 50! = 1*2*...*50, then a prime p divides 50! iff p divides some of the numbers 1, 2,...,50 ==> the primes that divide 50 are exactly the ones that are between 2 and 47, including! 4)For example, 49 = 43 + 2(3) , 75 = 71 + 2(2), 61 = 47 + 2(7) , etc. 5) ca = cb (mod m) <==> ca-cb = km, for some integer k <==> c(a-b) = km ==> a-b = km/c . Let d = (k,c) ==> c = dr , k = ds, s,r integers, so: a-b = km/c = (ds)m/dr = ms/r. 6) Clearly, n^5 = 0 (mod 4) for any even k, and then clearly: n^5 = 3 (mod 4) for n = 3 (mod 4), and n^5 = 1 (mod 4) for n = 1 (mod 4), so: 1^5 + 2^5 +...+100^5 = 1^5 + 5^5 +...+ 97^5 + 3^5 + 7^5 +...+ 99^5 = 25(1) + 25(3) = 1 + 3 = 0 (mod 4). Another way: in the odd integers sum we have pairs: (1^5 + 3^5)+(5^5 + 7^5)+...+(97^5 + 99^5) and each and every one of these pairs equals 0 mod 4, so the whole sum is also 0 mod 4 and we're done! 7) a = 2k + 1, so a^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1 ==> as k or k + 1 is pair,

we have that k(k+1) is pair ==> 4k(k+1) is divisible by 8 ==> a^2 -1 is divisible by 8 ==> a^2 = 1 (mod 8) !