# High School Mathematics Extensions/Solutions to Problem Sets

## Primes and Modular Arithmetic

### Factorisation Exercises

Factorise the following numbers. (note: I know you didn't have to, this is just for those who are curious)

1. ${\displaystyle 13=13\cdot 1}$
2. ${\displaystyle 26=13\cdot 2}$
3. ${\displaystyle 59=59\cdot 1}$
4. ${\displaystyle 82=41\cdot 2}$
5. ${\displaystyle 101=101\cdot 1}$
6. ${\displaystyle 121=11\cdot 11}$
7. ${\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}$

### Recursive Factorisation Exercises

Factorise using recursion.

1. ${\displaystyle 45=3\cdot 3\cdot 5}$
2. ${\displaystyle 4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5}$
3. ${\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}$

### Prime Sieve Exercises

1. Use the above result to quickly work out the numbers that still need to be crossed out in the table below, knowing 5 is the next prime:
${\displaystyle {\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}}$
The next prime number is 5. Because 5 is an unmarked prime number, and 5 * 5 = 25, cross out 25. Also, 7 is an unmarked prime number, and 5 * 7 = 35, so cross off 35. However, 5 * 11 = 55, which is too high, so mark 5 as prime ad move on to 7. The only number low enough to be marked off is 7 * 7, which equals 35. You can go no higher.

2. Find all primes below 200.

The method will not be outlined here, as it is too long. However, all primes below 200 are:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

### Modular Arithmetic Exercises

1. ${\displaystyle (-1)\cdot (-5)\mod {11}=5}$
2. ${\displaystyle 3\cdot 7\mod {11}=21=10}$
3. ${\displaystyle 2^{1}=2,2^{2}=4,2^{3}=8,2^{4}=16=5}$
${\displaystyle 2^{5}=32=10,2^{6}=64=9,2^{7}=128=7}$
${\displaystyle 2^{8}=256=3,2^{9}=512=6,2^{10}=1024=1}$
An easier list: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1