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

$x=100a+10b+c$

now

$x\equiv a+10b+c\equiv a-b+c(\mathrm{mod}11)$

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

$p\equiv 0(\mathrm{mod}3)$

we deduce p is not prime, as it's a multiple of 3

2nd category

$p\equiv 1(\mathrm{mod}3)$

$p+2\equiv 0(\mathrm{mod}3)$

so p + 2 is not prime

3rd category

$p\equiv 2(\mathrm{mod}3)$

$p+4\equiv 0(\mathrm{mod}3)$

therefore p + 4 is not prime

Therefore p, p + 2 and p + 4 cannot all be primes.

Question 3

Find x

$\begin{array}{c}x\equiv 1^7+2^7+3^7+4^7+5^7+6^7+7^7(\mathrm{mod}7)\end{array}$

Solution

Notice that

$-a\equiv 7-a(\mathrm{mod}7)$.

Then

$1^7\equiv (7-6{)}^7\equiv (-6{)}^7\equiv -(6^7)(\mathrm{mod}7)$.

Likewise,

$2^7\equiv -5^7(\mathrm{mod}7)$

and

$3^7\equiv -4^7(\mathrm{mod}7)$.

Then

$x$	$\equiv 1^7+2^7+3^7+4^7+5^7+6^7+7^7$
	$\equiv 1^7+2^7+3^7-3^7-2^7-1^7+7^7$
	$\equiv 0(\mathrm{mod}7)$

Question 4

9. Show that there are no integers x and y such that

$x^2-5y^2=3$

Solution

Look at the equation mod 5, we have

$x^2=3(\mathrm{mod}5)$

but

$1^2\equiv 1$

$2^2\equiv 4$

$3^2\equiv 4$

$4^2\equiv 1$

therefore there does not exist a x such that

$x^2\equiv 3(\mathrm{mod}5)$

Question 5

Let p be a prime number. Show that

(a)

$(p-1)!\equiv -1(\mathrm{mod}p)$

where

$n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n$

E.g. 3! = 1×2×3 = 6

(b) Hence, show that

$\sqrt{-1}\equiv \frac{p-1}{2}!(\mathrm{mod}p)$

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

$(p-1)!=(p-1)(p-2)(p-3)\cdots 2$

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"

$(p-1)!\equiv (p-1)\equiv -1$

as required.

b) From part a)

$-1\equiv (p-1)!$

since p = 4k + 1 for some positive integer k, (p - 1)! has 4k terms

$-1=1\times 2\times 3\times \cdots 2k\times (-2k)\cdots \times (-3)\times (-2)\times (-1)$

there are an even number of minuses on the right hand side, so

$-1=(1\times 2\times 3\times \cdots 2k{)}^2$

it follows

$\sqrt{-1}=1\times 2\times 3\times ...2k$

and finally we note that p = 4k + 1, we can conclude

$\sqrt{-1}=\frac{p-1}{2}!$