# 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{\pmod {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{\pmod {3}}\!$
we deduce p is not prime, as it's a multiple of 3
2nd category
$p\equiv 1{\pmod {3}}\!$
$p+2\equiv 0{\pmod {3}}\!$
so p + 2 is not prime
3rd category
$p\equiv 2{\pmod {3}}\!$
$p+4\equiv 0{\pmod {3}}\!$
therefore p + 4 is not prime

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

### Question 3

Find x

${\begin{matrix}x\equiv 1^{7}+2^{7}+3^{7}+4^{7}+5^{7}+6^{7}+7^{7}\ {\pmod {7}}\\\end{matrix}}$

Solution

Notice that

$-a\equiv 7-a{\pmod {7}}\!$ .

Then

$1^{7}\equiv (7-6)^{7}\equiv (-6)^{7}\equiv -(6^{7}){\pmod {7}}\!$ .

Likewise,

$2^{7}\equiv -5^{7}{\pmod {7}}\!$

and

$3^{7}\equiv -4^{7}{\pmod {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{\pmod {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{\pmod {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{\pmod {5}}\!$

### Question 5

Let p be a prime number. Show that

(a)

$(p-1)!\equiv -1\ {\pmod {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}}!{\pmod {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}}!$