High School Mathematics Extensions/Primes/Problem Set/Solutions

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Note: The best way to view these pages is to set your Math Preferences to "Always Render PNG".

HSME
Content
100%.png Primes
100%.png Modular Arithmetic
Problems & Projects
100%.png Problem Set
100%.png Project
Soultions
100%.png Exercise Solutions
50%.png Problem Set Solutions
Misc.
100%.png Definition Sheet
100%.png Full Version
25%.png PDF Version

Contents

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.


[edit] 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.

[edit] Question 2

Show that p, p + 2 and p + 4 cannot all be primes. (p a positive integer)

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.

[edit] 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} \!

[edit] 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} \!

[edit] 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\times2 \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\times2 \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}!
Retrieved from "http://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Primes/Problem_Set/Solutions"