High School Mathematics Extensions/Primes/Problem Set/Solutions
HSME |
Content |
---|
Primes |
Modular Arithmetic |
Problems & Projects |
Problem Set |
Project |
Solutions |
Exercise Solutions |
Problem Set Solutions |
Misc. |
Definition Sheet |
Full Version |
PDF Version |
At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.
If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.
Question 1[edit | edit source]
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[edit | edit source]
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[edit | edit source]
Find x
Solution
Notice that
- .
Then
- .
Likewise,
and
- .
Then
Question 4[edit | edit source]
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[edit | edit source]
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