1.3#
Exercises from Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.
Table of Contents#
Programming Environment#
import math
import numpy as np
1#
Use the Sieve of Eratosthenes to find all prime numbers less than \(250\).
math.sqrt(250)
15.811388300841896
integers = list(range(2, 250 + 1))
primes = []
print(primes)
print(np.array(integers))
[]
[ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
236 237 238 239 240 241 242 243 244 245 246 247 248 249 250]
prime = integers.pop(0)
primes.append(prime)
integers = list(integer for integer in integers if integer % prime != 0)
print(primes)
print(np.array(integers))
[2]
[ 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37
39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73
75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109
111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145
147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181
183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217
219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249]
prime = integers.pop(0)
primes.append(prime)
integers = list(integer for integer in integers if integer % prime != 0)
print(primes)
print(np.array(integers))
[2, 3]
[ 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55
59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109
113 115 119 121 125 127 131 133 137 139 143 145 149 151 155 157 161 163
167 169 173 175 179 181 185 187 191 193 197 199 203 205 209 211 215 217
221 223 227 229 233 235 239 241 245 247]
prime = integers.pop(0)
primes.append(prime)
integers = list(integer for integer in integers if integer % prime != 0)
print(primes)
print(np.array(integers))
[2, 3, 5]
[ 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71
73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137
139 143 149 151 157 161 163 167 169 173 179 181 187 191 193 197 199 203
209 211 217 221 223 227 229 233 239 241 247]
prime = integers.pop(0)
primes.append(prime)
integers = list(integer for integer in integers if integer % prime != 0)
print(primes)
print(np.array(integers))
[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 121 127 131 137 139 143 149 151 157 163
167 169 173 179 181 187 191 193 197 199 209 211 221 223 227 229 233 239
241 247]
prime = integers.pop(0)
primes.append(prime)
integers = list(integer for integer in integers if integer % prime != 0)
print(primes)
print(np.array(integers))
[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 169 173
179 181 191 193 197 199 211 221 223 227 229 233 239 241 247]
prime = integers.pop(0)
primes.append(prime)
integers = list(integer for integer in integers if integer % prime != 0)
print(primes)
print(np.array(integers))
[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 211 223 227 229 233 239 241]
print(np.array(primes + integers))
[ 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 211 223 227 229 233 239 241]
2#
Show why, when using the sieve method to find all primes less than \(n\), you need only strike out multiples of the primes whose square is less than or equal to \(n\).
\(Claim\)
Each composite up to \(n\) has a prime factor less than or equal to \(\sqrt{n}\).
\[
\forall n \in \mathbb{P} \,\,
[\,\,
Composite(n)
\implies
\exists p \in \{2, 3, 5, \dots, \sqrt{n}\} \,\,
(\,\,
p \mid n
\,\,)
\,\,]
\]
\(Proof\)
Let \(n\) be composite.
Then \(n\) has a factor \(1 \lt a \lt n\).
\(a \mid n \iff ab = n\) for some positive integer \(b\).
\(1 \lt a \lt n \iff b \lt (ab = n) \lt nb\)
\(b \lt ab \implies b \lt n\)
\(n \lt nb \implies 1 \lt b\)
\(\therefore 1 \lt b \lt n\)Let \(a \gt \sqrt{n}\) and \(b \gt \sqrt{n}\).
Then \(ab \gt \sqrt{n}\sqrt{n} = n\). \(Contradiction!\)
So either \(a \le \sqrt{n}\) or \(b \le \sqrt{n}\) or both.
ALTERNATIVELY
So either \(a \le \sqrt{n}\) or \(a \ge \sqrt{n}\) or both.Let \(a \le \sqrt{n}\).
\(a \le \sqrt{n} \iff \frac{1}{a} \ge \frac{1}{\sqrt{n}} \iff \frac{n}{a} = b \ge \sqrt{n} = \frac{n}{\sqrt{n}}\).
\(\therefore a \le \sqrt{n} \iff b \ge \sqrt{n}\).Let \(a \ge \sqrt{n}\).
\(a \ge \sqrt{n} \iff \frac{1}{a} \le \frac{1}{\sqrt{n}} \iff \frac{n}{a} = b \le \sqrt{n} = \frac{n}{\sqrt{n}}\).
\(\therefore a \ge \sqrt{n} \iff b \le \sqrt{n}\).Therefore either \(a \le \sqrt{n}\) or \(b \le \sqrt{n}\) or both.
\(n\) has a positive divisor not exceeding \(\sqrt{n}\) since both \(a\) and \(b\) are divisors of \(n\).
This divisor is either prime or, by the fundamental theorem of arithmetic, has a prime divisor less than itself.
In either case, \(n\) has a prime divisor less than or equal to \(\sqrt{n}\).
\(\blacksquare\)
\( \begin{aligned} \lfloor\sqrt{n}\rfloor^2 &\le n && && \le \lceil\sqrt{n}\rceil^2 \\ 1^2 &\le 1 = 1^2 && && \le 1^2 \\ 1^2 &\le 2 = 1^2 + 1 && && \le 2^2 \\ 1^2 &\le 3 = 2^2 - 1 && = 1^2 + 1 + 1 && \le 2^2 \\ 2^2 &\le 4 = 2^2 && = (1^2 - 1) + 2 + 2 && \le 2^2 \\ 2^2 &\le 5 = 2^2 + 1 && = (1^2 - 1) + 2 + 2 + 1 && \le 3^2 \\ 2^2 &\le 6 = 2^2 + 2 && && \le 3^2 \\ 2^2 &\le 7 = 2^2 + 3 && && \le 3^2 \\ 2^2 &\le 8 = 3^2 - 1 && = 2^2 + 2 + 2 && \le 3^2 \\ 3^2 &\le 9 = 3^2 && = ( 2^2 - 1) + 3 + 3 && \le 3^2 \\ 3^2 &\le 10 = 3^2 + 1 && = ( 2^2 - 1) + 3 + 3 + 1 && \le 4^2 \\ \vdots \\ 14^2 &\le 224 = 15^2 - 1 && = 14^2 + 14 + 14 && \le 15^2 \\ 15^2 &\le 225 = 15^2 && = (14^2 - 1) + 15 + 15 && \le 15^2 \\ 15^2 &\le 226 = 15^2 + 1 && = (14^2 - 1) + 15 + 15 + 1 && \le 16^2 \\ \vdots \\ 15^2 &\le 250 = 15^2 + 25 && = (14^2 - 1) + 15 + 15 + 25 && \le 16^2 \\ \vdots \\ 15^2 &\le 255 = 16^2 - 1 && = 15^2 + 15 + 15 && \le 16^2 \\ 16^2 &\le 256 = 16^2 && = (15^2 - 1) + 16 + 16 && \le 16^2 \\ 16^2 &\le 257 = 16^2 + 1 && = (15^2 - 1) + 16 + 16 + 1 && \le 17^2 \\ \vdots \\ 16^2 &\le 288 = 17^2 - 1 && = 16^2 + 16 + 16 && \le 17^2 \\ 17^2 &\le 289 = 17^2 && = (16^2 - 1) + 17 + 17 && \le 17^2 \\ 17^2 &\le 290 = 17^2 + 1 && = (16^2 - 1) + 17 + 17 + 1 && \le 18^2 \\ \vdots \\ \end{aligned} \)
\(\newcommand{\g}[1]{\textcolor{green}{#1}}\)
\[\begin{split}
\begin{array}{c|c|c|c|c|c||c|c}
2 & & & & & & & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 3 & & & & & & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
4 & & & & & & & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 5 & & & & & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
6 & • & & & & & & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 7 & & & & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
8 & & & & & & & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 9 & & & & & & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
10 & & • & & & & & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & 11 & & & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
12 & • & & & & & & \g{2^2} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & 13 & & 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
14 & & & • & & & & \g{2^1} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& 15 & • & & & & & 2^0 \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline\hline\hline
16 & & & & & & & \g{2^4} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 17 & \\ \hline
18 & • & & & & & & \g{2^1} \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 19 & \\ \hline
20 & & • & & & & & \g{2^2} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 21 & & • & & & & 2^0 \times \g{3^1} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
22 & & & & • & & & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & & & & & 23 & \\ \hline
24 & • & & & & & & \g{2^3} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 25 & & & & & 2^0 \times 3^0 \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
26 & & & & & • & & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& 27 & & & & & & 2^0 \times \g{3^3} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
28 & & & • & & & & \g{2^2} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 29 & \\ \hline
30 & • & • & & & & & \g{2^1} \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 31 & \\ \hline
32 & & & & & & & \g{2^5} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 33 & & & • & & & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
34 & & & & & & 17 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 35 & • & & & & 2^0 \times 3^0 \times \g{5^1} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
36 & • & & & & & & \g{2^2} \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 37 & \\ \hline
38 & & & & & & 19 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 39 & & & & • & & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
40 & & • & & & & & \g{2^3} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 41 & \\ \hline
42 & • & & • & & & & \g{2^1} \times \g{3^1} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 43 & \\ \hline
44 & & & & • & & & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& 45 & • & & & & & 2^0 \times \g{3^2} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
46 & & & & & & 23 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 47 & \\ \hline
48 & • & & & & & & \g{2^4} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 49 & & & & 2^0 \times 3^0 \times 5^0 \times \g{7^2} \times 11^0 \times 13^0 \\ \hline
50 & & • & & & & & \g{2^1} \times 3^0 \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 51 & & & & & 17 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
52 & & & & & • & & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& & & & & & 53 & \\ \hline
54 & • & & & & & 27 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 55 & & • & & & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
56 & & & • & & & & \g{2^3} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& 57 & & & & & 19 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
58 & & & & & & 29 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 59 & \\ \hline
60 & • & • & & & & & \g{2^2} \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 61 & \\ \hline
62 & & & & & & 31 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 63 & & • & & & & 2^0 \times \g{3^2} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
64 & & & & & & & \g{2^6} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 65 & & & • & & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
66 & • & & & • & & & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & & & & & 67 & \\ \hline
68 & & & & & & 17 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 69 & & & & & 23 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
70 & & • & • & & & & \g{2^1} \times 3^0 \times \g{5^1} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 71 & \\ \hline
72 & • & & & & & & \g{2^3} \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 73 & \\ \hline
74 & & & & & & 37 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 75 & • & & & & & 2^0 \times \g{3^1} \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
76 & & & & & & 19 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 77 & • & & & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times \g{11^1} \times 13^0 \\ \hline
78 & • & & & & • & & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& & & & & & 79 & \\ \hline
80 & & • & & & & & \g{2^4} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 81 & & & & & & 2^0 \times \g{3^4} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
82 & & & & & & 41 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 83 & \\ \hline
84 & • & & • & & & & \g{2^2} \times \g{3^1} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & 85 & & & & 17 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
86 & & & & & & 43 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 87 & & & & & 29 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
88 & & & & • & & & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & & & & & 89 & \\ \hline
90 & • & • & & & & & \g{2^1} \times \g{3^2} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 91 & & • & & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times \g{13^1} \\ \hline
92 & & & & & & 23 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 93 & & & & & 31 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
94 & & & & & & 47 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 95 & & & & 19 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
96 & • & & & & & & \g{2^5} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 97 & \\ \hline
98 & & & • & & & & \g{2^1} \times 3^0 \times 5^0 \times \g{7^2} \times 11^0 \times 13^0 \\ \hline
& 99 & & & • & & & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
100 & & • & & & & & \g{2^2} \times 3^0 \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 101 & \\ \hline
102 & • & & & & & 17 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 103 & \\ \hline
104 & & & & & • & & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& 105 & • & • & & & & 2^0 \times \g{3^1} \times \g{5^1} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
106 & & & & & & 53 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 107 & \\ \hline
108 & • & & & & & & \g{2^2} \times \g{3^3} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 109 & \\ \hline
110 & & • & & • & & & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& 111 & & & & & 37 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
112 & & & • & & & & \g{2^4} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 113 & \\ \hline
114 & • & & & & & 19 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 115 & & & & 23 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
116 & & & & & & 29 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 117 & & & & • & & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
118 & & & & & & 59 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 119 & & & 17 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
120 & • & • & & & & & \g{2^3} \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & 121 & & & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^2} \times 13^0 \\ \hline
122 & & & & & & 61 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 123 & & & & & 41 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
124 & & & & & & 31 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 125 & & & & & 2^0 \times 3^0 \times \g{5^3} \times 7^0 \times 11^0 \times 13^0 \\ \hline
126 & • & & • & & & & \g{2^1} \times \g{3^2} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 127 & \\ \hline
128 & & & & & & & \g{2^7} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 129 & & & & & 43 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
130 & & • & & & • & & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& & & & & & 131 & \\ \hline
132 & • & & & • & & & \g{2^2} \times \g{3^1} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & & 133 & & & 19 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
134 & & & & & & 67 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 135 & • & & & & & 2^0 \times \g{3^3} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
136 & & & & & & 17 \times & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 137 & \\ \hline
138 & • & & & & & 23 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 139 & \\ \hline
140 & & • & • & & & & \g{2^2} \times 3^0 \times \g{5^1} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& 141 & & & & & 47 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
142 & & & & & & 71 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & 143 & • & & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times \g{13^1} \\ \hline
144 & • & & & & & & \g{2^4} \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 145 & & & & 29 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
146 & & & & & & 73 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 147 & & • & & & & 2^0 \times \g{3^1} \times 5^0 \times \g{7^2} \times 11^0 \times 13^0 \\ \hline
148 & & & & & & 37 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 149 & \\ \hline
150 & • & • & & & & & \g{2^1} \times \g{3^1} \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 151 & \\ \hline
152 & & & & & & 19 \times & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 153 & & & & & 17 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
154 & & & • & • & & & \g{2^1} \times 3^0 \times 5^0 \times \g{7^1} \times \g{11^1} \times 13^0 \\ \hline
& & 155 & & & & 17 \times & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
156 & • & & & & • & & \g{2^2} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& & & & & & 157 & \\ \hline
158 & & & & & & 79 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 159 & & & & & 53 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
160 & & • & & & & & \g{2^5} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 161 & & & 23 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
162 & • & & & & & & \g{2^1} \times \g{3^4} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 163 & \\ \hline
164 & & & & & & 41 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 165 & • & & • & & & 2^0 \times \g{3^1} \times \g{5^1} \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
166 & & & & & & 83 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 167 & \\ \hline
168 & • & & • & & & & \g{2^3} \times \g{3^1} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & 169 & & 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^2} \\ \hline
170 & & • & & & & 17 \times & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 171 & & & & & 19 \times & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
172 & & & & & & 43 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 173 & \\ \hline
174 & • & & & & & 29 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 175 & • & & & & 2^0 \times 3^0 \times \g{5^2} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
176 & & & & • & & & \g{2^4} \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& 177 & & & & & 59 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
178 & & & & & & 89 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 179 & \\ \hline
180 & • & • & & & & & \g{2^2} \times \g{3^2} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 181 & \\ \hline
182 & & & • & & • & & \g{2^1} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times \g{13^1} \\ \hline
& 183 & & & & & 61 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
184 & & & & & & 23 \times & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 185 & & & & 37 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
186 & • & & & & & 31 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & 187 & & 17 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
188 & & & & & & 47 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 189 & & • & & & & 2^0 \times \g{3^3} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
190 & & • & & & & 19 \times & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 191 & \\ \hline
192 & • & & & & & & \g{2^6} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 193 & \\ \hline
194 & & & & & & 97 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 195 & • & & & • & & 2^0 \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
196 & & & • & & & & \g{2^2} \times 3^0 \times 5^0 \times \g{7^2} \times 11^0 \times 13^0 \\ \hline
& & & & & & 197 & \\ \hline
198 & • & & & • & & & \g{2^1} \times \g{3^2} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & & & & & 199 & \\ \hline
200 & & • & & & & & \g{2^3} \times 3^0 \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 201 & & & & & 67 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
202 & & & & & & 101 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 203 & & & 29 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
204 & • & & & & & 17 \times & \g{2^2} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 205 & & & & 41 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
206 & & & & & & 103 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 207 & & & & & 23 \times & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
208 & & & & & • & & \g{2^4} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& & & & 209 & & 19 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
210 & • & • & • & & & & \g{2^1} \times \g{3^1} \times \g{5^1} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 211 & \\ \hline
212 & & & & & & 53 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 213 & & & & & 71 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
214 & & & & & & 107 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 215 & & & & 43 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
216 & • & & & & & & \g{2^3} \times \g{3^3} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 217 & & & 31 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
218 & & & & & & 109 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 219 & & & & & 73 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
220 & & • & & • & & & \g{2^2} \times 3^0 \times \g{5^1} \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & & & & 221 & 17 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
222 & • & & & & & 37 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 223 & \\ \hline
224 & & & • & & & & \g{2^5} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& 225 & • & & & & & 2^0 \times \g{3^2} \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
226 & & & & & & 113 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 227 & \\ \hline
228 & • & & & & & 19 \times & \g{2^2} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 229 & \\ \hline
230 & & • & & & & 23 \times & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 231 & & • & • & & & 2^0 \times \g{3^1} \times 5^0 \times \g{7^1} \times \g{11^1} \times 13^0 \\ \hline
232 & & & & & & 29 \times & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 233 & \\ \hline
234 & • & & & & • & & \g{2^1} \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& & 235 & & & & 47 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
236 & & & & & & 59 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 237 & & & & & 79 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
238 & & & • & & & 17 \times & \g{2^1} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 239 & \\ \hline
240 & • & • & & & & & \g{2^4} \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 241 & \\ \hline
242 & & & & • & & 17 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^2} \times 13^0 \\ \hline
& 243 & & & & & & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times \g{11^2} \times 13^0 \\ \hline
244 & & & & & & 61 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 245 & • & & & & 2^0 \times 3^0 \times \g{5^1} \times \g{7^2} \times 11^0 \times 13^0 \\ \hline
246 & • & & & & & 41 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & 247 & 19 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
248 & & & & & & 31 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 249 & & & & & 83 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
250 & & • & & & & & \g{2^1} \times 3^0 \times \g{5^3} \times 7^0 \times 11^0 \times 13^0 \\ \hline\hline\hline
& & & & & & 251 & \\ \hline
252 & • & & • & & & & \g{2^2} \times \g{3^2} \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & 253 & & 23 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
254 & & & & & & 127 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 255 & • & & & & 17 \times & 2^0 \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
256 & & & & & & & \g{2^8} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 257 & \\ \hline
258 & • & & & & & 43 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & 259 & & & 37 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
260 & & • & & & • & & \g{2^2} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
& 261 & & & & & 29 \times & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
262 & & & & & & 131 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 263 & \\ \hline
264 & • & & & • & & & \g{2^3} \times \g{3^1} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
& & 265 & & & & 53 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
266 & & & • & & & 19 \times & \g{2^1} \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& 267 & & & & & 89 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
268 & & & & & & 67 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 269 & \\ \hline
270 & • & • & & & & & \g{2^1} \times \g{3^3} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 271 & \\ \hline
272 & & & & & & 17 \times & \g{2^4} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 273 & & • & & • & & 2^0 \times \g{3^1} \times 5^0 \times \g{7^1} \times 11^0 \times \g{13^1} \\ \hline
274 & & & & & & 137 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & 275 & & • & & & 2^0 \times 3^0 \times \g{5^2} \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
276 & • & & & & & 23 \times & \g{2^2} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 277 & \\ \hline
278 & & & & & & 139 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 279 & & & & & 31 \times & 2^0 \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
280 & & • & • & & & & \g{2^3} \times 3^0 \times \g{5^1} \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
& & & & & & 281 & \\ \hline
282 & • & & & & & 47 \times & \g{2^1} \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 283 & \\ \hline
284 & & & & & & 71 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 285 & • & & & & 19 \times & 2^0 \times \g{3^1} \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
286 & & & & • & • & & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times \g{11^1} \times \g{13^1} \\ \hline
& & & 287 & & & 41 \times & 2^0 \times 3^0 \times 5^0 \times \g{7^1} \times 11^0 \times 13^0 \\ \hline
288 & • & & & & & & \g{2^5} \times \g{3^2} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & \textcolor{red}{289 = 17 \times 17} & \\ \hline
290 & & • & & & & 29 \times & \g{2^1} \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 291 & & & & & 97 \times & 2^0 \times \g{3^1} \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
292 & & & & & & 73 \times & \g{2^2} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & & 293 & \\ \hline
294 & • & & • & & & & \g{2^1} \times \g{3^1} \times 5^0 \times \g{7^2} \times 11^0 \times 13^0 \\ \hline
& & 295 & & & & 59 \times & 2^0 \times 3^0 \times \g{5^1} \times 7^0 \times 11^0 \times 13^0 \\ \hline
296 & & & & & & 37 \times & \g{2^3} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& 297 & & & • & & & 2^0 \times \g{3^3} \times 5^0 \times 7^0 \times \g{11^1} \times 13^0 \\ \hline
298 & & & & & & 149 \times & \g{2^1} \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \\ \hline
& & & & & 299 & 23 \times & 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times \g{13^1} \\ \hline
300 & • & • & & & & & \g{2^2} \times \g{3^1} \times \g{5^2} \times 7^0 \times 11^0 \times 13^0 \\ \hline
\end{array}
\end{split}\]
3#
(a) Find the prime factorizations for the following integers (a calculator will be useful for the larger values): 136, 150, 255, 713, 3549, 4591. (b) Use your answers to find the greatest common divisor and least common multiple for each of the pairs: 136 and 150, 255 and 3549.
\[\begin{split}
\begin{align*}
136 &= 2^3 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \times 17^1 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
150 &= 2^1 \times 3^1 \times 5^2 \times 7^0 \times 11^0 \times 13^0 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
255 &= 2^0 \times 3^1 \times 5^1 \times 7^0 \times 11^0 \times 13^0 \times 17^1 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
713 &= 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \times 17^0 \times 19^0 \times 23^1 \times 29^0 \times 31^1 \\
3549 &= 2^0 \times 3^1 \times 5^0 \times 7^1 \times 11^0 \times 13^2 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
4591 &= 2^0 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \times \dots \times 4591^1 \\
\end{align*}
\end{split}\]
\[\begin{split}
\begin{align*}
136 &= 2^3 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \times 17^1 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
150 &= 2^1 \times 3^1 \times 5^2 \times 7^0 \times 11^0 \times 13^0 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
\hline
gcd(136, 150) &= 2^1 \times 3^0 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 = 2 \\
lcm(136, 150) &= 2^3 \times 3^1 \times 5^2 \times 7^0 \times 11^0 \times 13^0 \times 17^1 \times 19^0 \times 23^0 \times 29^0 \times 31^0 = 10,200 \\
\end{align*}
\end{split}\]
a = 136
b = 150
print(np.gcd(a, b))
print(np.lcm(a, b))
2
10200
\[\begin{split}
\begin{align*}
255 &= 2^0 \times 3^1 \times 5^1 \times 7^0 \times 11^0 \times 13^0 \times 17^1 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
3549 &= 2^0 \times 3^1 \times 5^0 \times 7^1 \times 11^0 \times 13^2 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 \\
\hline
gcd(255, 3549) &= 2^0 \times 3^1 \times 5^0 \times 7^0 \times 11^0 \times 13^0 \times 17^0 \times 19^0 \times 23^0 \times 29^0 \times 31^0 = 3 \\
lcm(255, 3549) &= 2^0 \times 3^1 \times 5^1 \times 7^1 \times 11^0 \times 13^2 \times 17^1 \times 19^0 \times 23^0 \times 29^0 \times 31^0 = 301,665 \\
\end{align*}
\end{split}\]
a = 255
b = 3549
print(np.gcd(a, b))
print(np.lcm(a, b))
3
301665
4#
Let \(p_1 = 2, p_2 = 3, \dots\) be the list of primes, in increasing order. Consider products of the form \((p_1 \times p_2 \times \dots \times p_n) + 1\). Show that this number is prime for \(n = 1, \dots, 5\). Show that when \(n = 6\) this number is not prime. [Use your answer to #1. A calculator will speed the work of checking divisibility.]
\[\begin{split}
\begin{align*}
n = 1 && & (p_1) + 1 \\
&& =& (2) + 1 \\
&& =& 3 \\
n = 2 && & (p_1 \times p_2) + 1 \\
&& =& (2 \times 3) + 1 \\
&& =& 7 \\
n = 3 && & (p_1 \times p_2 \times p_3) + 1 \\
&& =& (2 \times 3 \times 5) + 1 \\
&& =& 31 \\
n = 4 && & (p_1 \times p_2 \times p_3 \times p_4) + 1 \\
&& =& (2 \times 3 \times 5 \times 7) + 1 \\
&& =& 211 \\
n = 5 && & (p_1 \times p_2 \times p_3 \times p_4 \times p_5) + 1 \\
&& =& (2 \times 3 \times 5 \times 7 \times 11) + 1 \\
&& =& 2311 \\
n = 6 && & (p_1 \times p_2 \times p_3 \times p_4 \times p_5 \times p_6) + 1 \\
&& =& (2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 \\
&& =& 30031 \\
&& =& 59 \times 509 \\
\end{align*}
\end{split}\]
5#
By considering the prime decomposition of \(gcd(ab, n)\), show that if \(a\), \(b\), and \(n\) are integers with \(n\) relatively prime to each of \(a\) and \(b\), then \(n\) is relatively prime to \(ab\).
\[\begin{split}
\begin{align*}
a &= p_1^{s_1} \times p_2^{s_2} \times \dots \times p_r^{s_r} \\
b &= p_1^{t_1} \times p_2^{t_2} \times \dots \times p_r^{t_r} \\
ab &= p_1^{s_1 + t_1} \times p_2^{s_2 + t_2} \times \dots \times p_r^{s_r + t_r} \\
\end{align*}
\end{split}\]