Number Theory and Cryptography
Math UN3020
New York, 2023/01/25
Exercise Sheet 2
Euclidean algorithm
Exercise 1 (12 points). Prove the following properties of the divisibility relation.
(a) ∀n ∈ Z, 1 | n.
(b) ∀d ∈ Z \ {0}, d | 0.
(c) If d | n and n | q, then d | q.
(d) If d | n and d | q, then ∀s, t ∈ Z, d | (sn + tq).
(e) d | 1 ⇔ d = ±1.
(f) If d | n and n | d, then d = ±n.
Definition 1. An operation on a set X is a function
∗ : X × X 3 (a, b) → a ∗ b ∈ X, .
In other words, an operation on X is a function that takes in input two elements a, b ∈ X, and
gives as output one element of X, denoted by a ∗ b.
An operation ∗ on X is said to be associative if
∀a, b, c ∈ X, (a ∗ b) ∗ c = a ∗ (b ∗ c) .
An operation ∗ on X is said to be commutative if
∀a, b ∈ X, a ∗ b = b ∗ a .
An identity for X is an element id ∈ X such that
∀a ∈ X, a ∗ id = id ∗ a = a .
If the operation ∗ has an identity id, an inverse of an element a ∈ X is an element b ∈ X such
that
a ∗ b = b ∗ a = id .
1
Exercise 2 (5 points). Let (X, ∗) be a set with an operation ∗ : X × X→X. Assume that the
operation is associative. Prove that if an identity element for ∗ exists in X, then it is unique.
(Hint: proceed by contradiction. Assume that there are two distinct identity elements for ∗, give
them names. Compute something using ∗, and find a contradiction.)
Exercise 3 (5 points). Let (X, ∗) be a set with an operation ∗ : X × X→X. Assume that the
operation is associative and admits an identity element id ∈ X. Consider an element a ∈ X.
Prove that if an inverse of a for ∗ exists in X, then it is unique.
(Hint: proceed by contradiction. Assume that there are two distinct inverse elements of a, give
them names. Compute something using ∗, and find a contradiction.)
Exercise 4 (8 points). Compute the quotient and remainder of the Euclidean division between
the following pairs of numbers:
(a) 25, 4.
(b) 28, 6.
(c) −28, 6.
(d) −14, 3.
Exercise 5 (6 points). Write all the elements of Divn , the set of divisors of n, where n is one of
the following numbers:
(a) 11.
(b) 18.
(c) 24.
2
Exercise 6 (8 points). Find gcd(a, b) and express it as a linear combination of a, b (i.e. write
gcd(a, b) = sa + tb with s, t ∈ Z) for the following pairs of numbers.
(a) a = 116, b = −84.
(b) a = 85, b = 65.
(c) a = 72, b = 26.
(d) a = 72, b = 25.
Exercise 7 (8 points). Given two numbers a, b ∈ Z. Consider the set of their linear combinations:
La,b = { n ∈ Z | ∃s, t ∈ Z s.t. n = sa + tb } = { sa + tb | s, t ∈ Z }
Prove that
La,b = { n ∈ Z | gcd(a, b) | n }
Exercise 8 (8 points).
(a) You have a 3-gallon and a 5-gallon jug that you can fill multiple times from a tap. The
problem is to measure exactly 4 gallons of water. How do you do it?
(b) You have a 9-gallon and a 12-gallon jug that you can fill multiple times from a tap. The
problem is to measure exactly 4 gallons of water. Prove that you cannot do it.
