1.3 1.3 #

Exercises from Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.

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$ .

$C l a i m$

Each composite up to $n$ has a prime factor less than or equal to $\sqrt{n}$ .

\forall n \in P [C o m p o s i t e (n) ⟹ \exists p \in {2, 3, 5, \dots, \sqrt{n}} (p ∣ n)]

$P r o o f$

Let $n$ be composite.
Then $n$ has a factor $1 < a < n$ .
$a ∣ n ⟺ a b = n$ for some positive integer $b$ .
$1 < a < n ⟺ b < (a b = n) < n b$
$b < a b ⟹ b < n$
$n < n b ⟹ 1 < b$
$∴ 1 < b < n$

Let $a > \sqrt{n}$ and $b > \sqrt{n}$ .
Then $a b > \sqrt{n} \sqrt{n} = n$ . $C o n t r a d i c t i o n!$
So either $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$ or both.
ALTERNATIVELY
So either $a \leq \sqrt{n}$ or $a \geq \sqrt{n}$ or both.

Let $a \leq \sqrt{n}$ .
$a \leq \sqrt{n} ⟺ \frac{1}{a} \geq \frac{1}{\sqrt{n}} ⟺ \frac{n}{a} = b \geq \sqrt{n} = \frac{n}{\sqrt{n}}$ .
$∴ a \leq \sqrt{n} ⟺ b \geq \sqrt{n}$ .

Let $a \geq \sqrt{n}$ .
$a \geq \sqrt{n} ⟺ \frac{1}{a} \leq \frac{1}{\sqrt{n}} ⟺ \frac{n}{a} = b \leq \sqrt{n} = \frac{n}{\sqrt{n}}$ .
$∴ a \geq \sqrt{n} ⟺ b \leq \sqrt{n}$ .

Therefore either $a \leq \sqrt{n}$ or $b \leq \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}$ .

$◼$

$\begin{aligned} ⌊ \sqrt{n} ⌋^{2} & \leq n & \leq ⌈ \sqrt{n} ⌉^{2} \\ 1^{2} & \leq 1 = 1^{2} & \leq 1^{2} \\ 1^{2} & \leq 2 = 1^{2} + 1 & \leq 2^{2} \\ 1^{2} & \leq 3 = 2^{2} - 1 & = 1^{2} + 1 + 1 & \leq 2^{2} \\ 2^{2} & \leq 4 = 2^{2} & = (1^{2} - 1) + 2 + 2 & \leq 2^{2} \\ 2^{2} & \leq 5 = 2^{2} + 1 & = (1^{2} - 1) + 2 + 2 + 1 & \leq 3^{2} \\ 2^{2} & \leq 6 = 2^{2} + 2 & \leq 3^{2} \\ 2^{2} & \leq 7 = 2^{2} + 3 & \leq 3^{2} \\ 2^{2} & \leq 8 = 3^{2} - 1 & = 2^{2} + 2 + 2 & \leq 3^{2} \\ 3^{2} & \leq 9 = 3^{2} & = (2^{2} - 1) + 3 + 3 & \leq 3^{2} \\ 3^{2} & \leq 10 = 3^{2} + 1 & = (2^{2} - 1) + 3 + 3 + 1 & \leq 4^{2} \\ ⋮ \\ 14^{2} & \leq 224 = 15^{2} - 1 & = 14^{2} + 14 + 14 & \leq 15^{2} \\ 15^{2} & \leq 225 = 15^{2} & = (14^{2} - 1) + 15 + 15 & \leq 15^{2} \\ 15^{2} & \leq 226 = 15^{2} + 1 & = (14^{2} - 1) + 15 + 15 + 1 & \leq 16^{2} \\ ⋮ \\ 15^{2} & \leq 250 = 15^{2} + 25 & = (14^{2} - 1) + 15 + 15 + 25 & \leq 16^{2} \\ ⋮ \\ 15^{2} & \leq 255 = 16^{2} - 1 & = 15^{2} + 15 + 15 & \leq 16^{2} \\ 16^{2} & \leq 256 = 16^{2} & = (15^{2} - 1) + 16 + 16 & \leq 16^{2} \\ 16^{2} & \leq 257 = 16^{2} + 1 & = (15^{2} - 1) + 16 + 16 + 1 & \leq 17^{2} \\ ⋮ \\ 16^{2} & \leq 288 = 17^{2} - 1 & = 16^{2} + 16 + 16 & \leq 17^{2} \\ 17^{2} & \leq 289 = 17^{2} & = (16^{2} - 1) + 17 + 17 & \leq 17^{2} \\ 17^{2} & \leq 290 = 17^{2} + 1 & = (16^{2} - 1) + 17 + 17 + 1 & \leq 18^{2} \\ ⋮ \end{aligned}$

MathJax internal buffer size exceeded; is there a recursive macro call?

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{array}{r} \begin{aligned} 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{aligned} \end{array}

\begin{array}{r} \begin{aligned} 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} \\ g c d (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 \\ l c m (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{aligned} \end{array}

a = 136
b = 150
print(np.gcd(a, b))
print(np.lcm(a, b))

2
10200

\begin{array}{r} \begin{aligned} 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} \\ g c d (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 \\ l c m (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{aligned} \end{array}

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{array}{r} \begin{aligned} 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{aligned} \end{array}

5 #

By considering the prime decomposition of $g c d (a b, 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 $a b$ .

\begin{array}{r} \begin{aligned} 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}} \\ a b & = p_{1}^{s_{1} + t_{1}} \times p_{2}^{s_{2} + t_{2}} \times \dots \times p_{r}^{s_{r} + t_{r}} \end{aligned} \end{array}

1.3

Contents

1.3 #

Table of Contents #

Programming Environment #

1 #

2 #

3 #

4 #

5 #