High School Mathematics Extensions/Primes/Problem Set

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

HSME
Content
Primes
Modular Arithmetic
Problems & Projects
Problem Set
Project
Solutions
Exercise Solutions
Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Problem Set

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 x² ≡ y, 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.