High School Mathematics Extensions/Primes/Problem Set/Solutions

Question 1 Is there a rule to determine whether a 3-digit number is divisible by 11? If yes, derive that rule. Solution Let x be a 3-digit number We have now We can conclude a 3-digit number is divisible by 11 if and only if the sum of first and last digit minus the second is divisible by 11. Question 2 Show that p, p + 2 and p + 4 cannot all be primes. (p a positive integer and is great than 3) Solution We look at the arithmetic mod 3, then p slotted into one of three categories 1st category we deduce p is not prime, as it's a multiple of 3 2nd category so p + 2 is not prime 3rd category therefore p + 4 is not prime Therefore p, p + 2 and p + 4 cannot all be primes. Question 3 Find x _à=7-a(mod 7) Solution Notice that . Then . Likewise, and . Then {|- | | |- |- | | |- |- | | |} Question 4 9. Show that there are no integers x and y such that Solution Look at the equation mod 5, we have but {|- | |- | |- | |- | |} therefore there does not exist a x such that Question 5 Let p be a prime number. Show that (a) where E.g. 3! = 1×2×3 = 6 (b) Hence, show that for p ≡ 1 (mod 4) Solution a) If p = 2, then it's obvious. So we suppose p is an odd prime. Since p is prime, some deep thought will reveal that every distinct element multiplied by some other element will give 1. Since we can pair up the inverses (two numbers that multiply to give one), and (p - 1) has itself as an inverse, therefore it's the only element not "eliminated" {|- | |} as required. b) From part a) since p = 4k + 1 for some positive integer k, (p - 1)! has 4k terms there are an even number of minuses on the right hand side, so it follows and finally we note that p = 4k + 1, we can conclude