1.1#
Exercises from Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.
Programming Environment#
import numpy as np
import sys
sys.setrecursionlimit(1_000)
sys.getrecursionlimit()
1000
def extended (b : int,
a : int,
print_flag : bool = False) -> tuple[int]:
if print_flag : pad = max(len(str(a)), len(str(b)))
x, y = b, a
r = b % a
if r == 0:
gcd, s, t = a, 0, 1
if print_flag : print(f'{gcd:>{pad}} = {s:>{pad}} x {x:>{pad}} + {t:>{pad}} x {y:>{pad}}')
return gcd, s, t
s1, t1, s2, t2 = 1, 0, 0, 1
while r:
q = b // a
r, s, t = (b - q*a,
s1 - q*s2,
t1 - q*t2)
b, a, s1, t1, s2, t2 = a, r, s2, t2, s, t
gcd, s, t = b, s1, t1
if print_flag : print(f'{gcd:>{pad}} = {s:>{pad}} x {x:>{pad}} + {t:>{pad}} x {y:>{pad}}')
return gcd, s, t
1.1#
1. For each of the following pairs \(a, b\) of integers, find the greatest common divisor \(d\) of \(a\) and \(b\) and express \(d\) in the form \(ar + bs\).#
[ 1.i ]
Let \(a = 7\) and \(b = 11\).
\(gcd(7, 11) = 1 = 7 \cdot (-3) + 11 \cdot 2\)
a, b = 7, 11
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
11 = 0 x 7 + 1 x 11
7 = 1 x 7 + 0 x 11
4 = -1 x 7 + 1 x 11
3 = 2 x 7 + -1 x 11
1 = -3 x 7 + 2 x 11
[ 1.ii ]
Let \(a = -28\) and \(b = -63\).
\(gcd(-28, -63) = 7 = (-28) \cdot 2 + (-63) \cdot (-1)\)
a, b = 28, 63
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
63 = 0 x 28 + 1 x 63
28 = 1 x 28 + 0 x 63
7 = -2 x 28 + 1 x 63
[ 1.iii ]
Let \(a = 91\) and \(b = 126\).
\(gcd(91, 126) = 7 = 91 \cdot 7 + 126 \cdot (-5)\)
a, b = 91, 126
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
126 = 0 x 91 + 1 x 126
91 = 1 x 91 + 0 x 126
35 = -1 x 91 + 1 x 126
21 = 3 x 91 + -2 x 126
14 = -4 x 91 + 3 x 126
7 = 7 x 91 + -5 x 126
[ 1.iv ]
Let \(a = 630\) and \(b = 132\).
\(gcd(630, 132) = 6 = 630 \cdot (-9) + 132 \cdot 43\)
a, b = 630, 132
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
132 = 0 x 630 + 1 x 132
102 = 1 x 630 + -4 x 132
30 = -1 x 630 + 5 x 132
12 = 4 x 630 + -19 x 132
6 = -9 x 630 + 43 x 132
[ 1.v ]
Let \(a = 7245\) and \(b = 4784\).
\(gcd(7245, 4784) = 23 = 7245 \cdot 35 + 4784 \cdot (-53)\)
a, b = 7245, 4784
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
4784 = 0 x 7245 + 1 x 4784
2461 = 1 x 7245 + -1 x 4784
2323 = -1 x 7245 + 2 x 4784
138 = 2 x 7245 + -3 x 4784
115 = -33 x 7245 + 50 x 4784
23 = 35 x 7245 + -53 x 4784
[ 1.vi ]
Let \(a = 6499\) and \(b = 4288\).
\(gcd(6499, 4288) = 67 = 6499 \cdot (-31) + 4288 \cdot 47\)
a, b = 6499, 4288
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
4288 = 0 x 6499 + 1 x 4288
2211 = 1 x 6499 + -1 x 4288
2077 = -1 x 6499 + 2 x 4288
134 = 2 x 6499 + -3 x 4288
67 = -31 x 6499 + 47 x 4288
2. Find the \(gcd\) of \(6\), \(14\), and \(21\) and express it in the form \(6r + 14s + 21t\) for some integers \(r\), \(s\), and \(t\).#
[ 2 ]
Find the \(gcd\) of \(6\), \(14\), and \(21\) and express it in the form \(6r + 14s + 21t\) for some integers \(r\), \(s\), and \(t\). [Hint: compute the \(gcd\) of two numbers at a time.]
\(gcd(6, 14, 21) = gcd(gcd(6, 14), 21)\)
\(gcd(6, 14, 21) = gcd(gcd(6, 14), 21) = gcd(2, 21)\)
\(gcd(6, 14) = 2 = 6 \cdot (-2) + 14 \cdot 1\)
a, b = 6, 14
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
14 = 0 x 6 + 1 x 14
6 = 1 x 6 + 0 x 14
2 = -2 x 6 + 1 x 14
\(gcd(6, 14, 21) = gcd(gcd(6, 14), 21) = gcd(2, 21) = 1\)
\(gcd(2, 21) = 1 = 2 \cdot (-10) + 21 \cdot 1\)
a, b = 2, 21
gcd, x, y = extended(a, b, True)
assert a*x + b*y == np.gcd(a, b)
21 = 0 x 2 + 1 x 21
2 = 1 x 2 + 0 x 21
1 = -10 x 2 + 1 x 21
a, b, c = 6, 14, 21
assert a*20 + b*(-10) + c*1 == np.gcd.reduce(array = [a, b, c])
\(Claim\)
If \(gcd(a, b) = g\) so that there are integers \(s\) and \(t\) s.t. \(a = gs\) and \(b = gt\) then \(gcd(s, t) = 1\).
\(Proof\)
Let \(gcd(a, b) = g\) so that there are integers \(s\) and \(t\) s.t. \(a = gs\) and \(b = gt\) since \(g \mid a\) and \(g \mid b\).
Let \(gcd(s, t) = d\) so that there are integers \(m\) and \(n\) s.t. \(s = dm\) and \(t = dn\) since \(d \mid s\) and \(d \mid t\).
\(a = gs = g(dm) = gd(m)\) and \(b = gt = g(dn) = gd(n)\).
So \(gd \mid a\), \(gd \mid b\), and so \(gd \mid g\) since \(gd\) is a common divisor of \(a\) and \(b\).
\(gd \mid g\) implies that \(d = 1\).
\(\therefore gcd(s, t) = 1\)
\(Proof \,\, by \,\, contraposition\)
To show that \(gcd(s, t) \ne 1\) is to show that \(gcd(a, b) \ne g\).
\(\blacksquare\)
3. Let \(a\) and \(b\) be relatively prime integers and let \(k\) be any integer. Show that \(b\) and \(a + bk\) are relatively prime.#
[ 3 ]
\(Claim\)
Let \(a\) and \(b\) be relatively prime integers and let \(k\) be any integer. Show that \(b\) and \(a + bk\) are relatively prime.
\(Proof\)
Let \(gcd(a + bk, b) = g\).
There are integers \(s\) and \(t\) s.t. \(gs = a + bk\) and \(gt = b\) since \(g \mid a + bk\) and \(g \mid b\).
\(gt = b \iff gtk = bk \iff a + gtk = a + bk = gs \iff a = g(s - tk)\) which implies that \(g \mid a\).
\(g \mid a\) and \(g \mid b\) implies that \(g = 1\).
\(\therefore gcd(a + bk, b) = 1\).
\(\blacksquare\)
4. Give an example of integers \(a\), \(b\), and \(c\) s.t. \(a\) divides \(bc\) but \(a\) divides neither \(b\) nor \(c\).#
\(a = mn\) not a prime.
\(b = mk\) where \(n \nmid k\) and \(c = nj\) where \(m \nmid j\).
\(\frac{b}{a} = \frac{mk}{mn} = \frac{k}{n} \not\in \mathbb{Z}\) and \(\frac{c}{a} = \frac{nj}{mn} = \frac{j}{m} \not\in \mathbb{Z}\) but \(\frac{bc}{a} = \frac{mnjk}{mn} = jk \in \mathbb{Z}\).
\(2n \mid n \times 2(nk + 1) = 2n^2k + 2n\) for \(n \in \{ 2, 3, \dots \}\) and \(k \in \mathbb{N}\)
\(4 \mid 2 \times 2(2k + 1)\) with \(k \in \mathbb{N}\)
\(a = 4, b = 2, c = 2(2k + 1)\)
\(\frac{b}{a} = \frac{1}{2} \not\in \mathbb{Z}\) and \(\frac{c}{a} = \frac{2k + 1}{2} \not\in \mathbb{Z}\)
\( 4 \mid 2 \times 2 = 2 \times (4 \cdot 0 + 2)\)
\( 4 \mid 2 \times 6 = 2 \times (4 \cdot 1 + 2)\)
\( 4 \mid 2 \times 10 = 2 \times (4 \cdot 2 + 2)\)
\( 4 \mid 2 \times 14 = 2 \times (4 \cdot 3 + 2)\)
\( 4 \mid 2 \times 18 = 2 \times (4 \cdot 4 + 2)\)
\(\vdots\)\(6 \mid 2 \times 2(3k + 1)\) with \(k \in \mathbb{N}\)
\(a = 6, b = 2, c = 2(3k + 1)\)
\(\frac{b}{a} = \frac{1}{3} \not\in \mathbb{Z}\) and \(\frac{c}{a} = \frac{3k + 1}{3} \not\in \mathbb{Z}\)
\( 6 \mid 3 \times 2 = 3 \times (6 \cdot 0 + 2)\)
\( 6 \mid 3 \times 8 = 3 \times (6 \cdot 1 + 2)\)
\( 6 \mid 3 \times 14 = 3 \times (6 \cdot 2 + 2)\)
\( 6 \mid 3 \times 20 = 3 \times (6 \cdot 3 + 2)\)
\( 6 \mid 3 \times 26 = 3 \times (6 \cdot 4 + 2)\)
\(\vdots\)\(8 \mid 4 \times 2(4k + 1)\) with \(k \in \mathbb{N}\)
\(a = 8, b = 2, c = 2(4k + 1)\)
\(\frac{b}{a} = \frac{1}{4} \not\in \mathbb{Z}\) and \(\frac{c}{a} = \frac{4k + 1}{4} \not\in \mathbb{Z}\)
\( 8 \mid 4 \times 2 = 4 \times (8 \cdot 0 + 2)\)
\( 8 \mid 4 \times 10 = 4 \times (8 \cdot 1 + 2)\)
\( 8 \mid 4 \times 18 = 4 \times (8 \cdot 2 + 2)\)
\( 8 \mid 4 \times 26 = 4 \times (8 \cdot 3 + 2)\)
\( 8 \mid 4 \times 34 = 4 \times (8 \cdot 4 + 2)\)
\(\vdots\)\(10 \mid 2 \times 2(5k + 1)\)
\(12 \mid 2 \times 2(6k + 1)\)
\(20 \mid 10 \times 12\)
\(30 \mid 10 \times 12\)
\(40 \mid 10 \times 12\)