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. $13=13\cdot 1$
2. $26=13\cdot 2$
3. $59=59\cdot 1$
4. $82=41\cdot 2$
5. $101=101\cdot 1$
6. $121=11\cdot 11$
7. $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

Recursive Factorisation Exercises

Factorise using recursion.

1. $45=3\cdot 3\cdot 5$
2. $4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5$
3. $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:

$\begin{array}{cccccccccc}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{array}$

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. $(-1)\cdot (-5)mod11=5$
2. $3\cdot 7mod11=21=10$
3. $2^1=2,2^2=4,2^3=8,2^4=16=5$
   $2^5=32=10,2^6=64=9,2^7=128=7$
   $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