Primes and Modular Arithmetic
edit
Factorisation Exercises
edit
Factorise the following numbers. (note: I know you didn't have to, this is just for those who are curious)
13
=
13
⋅
1
{\displaystyle 13=13\cdot 1}
26
=
13
⋅
2
{\displaystyle 26=13\cdot 2}
59
=
59
⋅
1
{\displaystyle 59=59\cdot 1}
82
=
41
⋅
2
{\displaystyle 82=41\cdot 2}
101
=
101
⋅
1
{\displaystyle 101=101\cdot 1}
121
=
11
⋅
11
{\displaystyle 121=11\cdot 11}
2187
=
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
{\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}
Recursive Factorisation Exercises
edit
Factorise using recursion.
45
=
3
⋅
3
⋅
5
{\displaystyle 45=3\cdot 3\cdot 5}
4050
=
2
⋅
3
⋅
3
⋅
3
⋅
3
⋅
5
⋅
5
{\displaystyle 4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5}
2187
=
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
{\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}
Prime Sieve Exercises
edit
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:
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
{\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
edit
(
−
1
)
⋅
(
−
5
)
mod
11
=
5
{\displaystyle (-1)\cdot (-5)\mod {11}=5}
3
⋅
7
mod
11
=
21
=
10
{\displaystyle 3\cdot 7\mod {11}=21=10}
2
1
=
2
,
2
2
=
4
,
2
3
=
8
,
2
4
=
16
=
5
{\displaystyle 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
{\displaystyle 2^{5}=32=10,2^{6}=64=9,2^{7}=128=7}
2
8
=
256
=
3
,
2
9
=
512
=
6
,
2
10
=
1024
=
1
{\displaystyle 2^{8}=256=3,2^{9}=512=6,2^{10}=1024=1}
