CS1231(S) Tutorial 7: Number Theory II
Solutions
National University of Singapore
2019/20 Semester 1
1. Compute gcd(a, b) for the following pairs of a and b, and express gcd(a, b) in the form
ax + by where x, y ∈ Z.
(a) a = 17, b = 5;
(b) a = 275, b = 407.
Solution. Using the Euclidean algorithm, you should get:
(a) gcd(17, 5) = 1 = 17(−2) + 5(7);
(b) gcd(407, 275) = 11 = 407(−2) + 275(3).
2. Prove the following statement:
∀a, b, c ∈ Z (a | c) ∧ (b | c) ∧ (gcd(a, b) = 1) → (ab | c)
Solution.
1. Let a, b, c ∈ Z such that a | c, b | c and gcd(a, b) = 1.
2. Since a | c, there exists k ∈ Z such that c = ka.
3. Since b | c, there exists l ∈ Z such that c = lb.
4. Since gcd(a, b) = 1, there exist x, y ∈ Z such that ax + by = 1.
5. Thus c = c(ax + by) (by (4)) = cax + cby = lb(ax) + ka(by) (by (3) and (2))
= ab(lx + ky).
6. Since l, x, k, y ∈ Z, we have lx + ky ∈ Z, and so ab | c.
This can also be proved by considering the prime factorisations of a, b, and c.
3. Let a, b ∈ Z. Prove that if x, y ∈ Z such that ax + by = gcd(a, b), then (gcd(x, y) exists
and) gcd(x, y) = 1.
Solution. Let a0 = gcd(a,b)
a
and b0 = b
gcd(a,b) . Then a0 , b0 ∈ Z, and a0 x + b0 y = 1.
Therefore gcd(x, y) = 1.
4. Let a, b ∈ Z, not both zero. Show that for all n ∈ Z, n is an integer linear combination
of a and b (i.e. there exist x, y ∈ Z such that ax + by = n) if and only if gcd(a, b) | n.
(Hint: use Bézout’s Identity for the ‘if’ direction).
1
Solutions
National University of Singapore
2019/20 Semester 1
1. Compute gcd(a, b) for the following pairs of a and b, and express gcd(a, b) in the form
ax + by where x, y ∈ Z.
(a) a = 17, b = 5;
(b) a = 275, b = 407.
Solution. Using the Euclidean algorithm, you should get:
(a) gcd(17, 5) = 1 = 17(−2) + 5(7);
(b) gcd(407, 275) = 11 = 407(−2) + 275(3).
2. Prove the following statement:
∀a, b, c ∈ Z (a | c) ∧ (b | c) ∧ (gcd(a, b) = 1) → (ab | c)
Solution.
1. Let a, b, c ∈ Z such that a | c, b | c and gcd(a, b) = 1.
2. Since a | c, there exists k ∈ Z such that c = ka.
3. Since b | c, there exists l ∈ Z such that c = lb.
4. Since gcd(a, b) = 1, there exist x, y ∈ Z such that ax + by = 1.
5. Thus c = c(ax + by) (by (4)) = cax + cby = lb(ax) + ka(by) (by (3) and (2))
= ab(lx + ky).
6. Since l, x, k, y ∈ Z, we have lx + ky ∈ Z, and so ab | c.
This can also be proved by considering the prime factorisations of a, b, and c.
3. Let a, b ∈ Z. Prove that if x, y ∈ Z such that ax + by = gcd(a, b), then (gcd(x, y) exists
and) gcd(x, y) = 1.
Solution. Let a0 = gcd(a,b)
a
and b0 = b
gcd(a,b) . Then a0 , b0 ∈ Z, and a0 x + b0 y = 1.
Therefore gcd(x, y) = 1.
4. Let a, b ∈ Z, not both zero. Show that for all n ∈ Z, n is an integer linear combination
of a and b (i.e. there exist x, y ∈ Z such that ax + by = n) if and only if gcd(a, b) | n.
(Hint: use Bézout’s Identity for the ‘if’ direction).
1
