High School Mathematics Extensions/Primes/Problem Set

From Wikibooks, open books for an open world
Jump to: navigation, search
HSME
Content
100%.svg Primes
100%.svg Modular Arithmetic
Problems & Projects
100%.svg Problem Set
100%.svg Project
Solutions
100%.svg Exercise Solutions
50%.svg Problem Set Solutions
Misc.
100%.svg Definition Sheet
100%.svg Full Version
25%.svg PDF Version

Contents

Problem Set[edit]

1. Is there a rule to determine whether a 3-digit number is divisible by 11? If so, derive that rule.

2. Show that p, p + 2 and p + 4 cannot all be primes if p is an integer greater than 3.

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}

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

x^2 - 5y^2 = 3 \!

5. In modular arithmetic, if

x^2 \equiv y \pmod{m} \!

for some m, then we can write

x \equiv \sqrt{y} \pmod{m}

we say, x is the square root of y mod m.

Note that if x satisfies x2y, then m - x ≡ -x when squared is also equivalent to y. We consider both x and -x to be square roots of y.

Let p be a prime number. Show that

(a)


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

for p ≡ 1 (mod 4), i.e., show that the above when squared gives one.