Arkansas Tech University
MATH 2703: Discrete Mathematics
Dr. Marcel B. Finan
Solution to Section 9
Problem 9.1
(i) Find gcd(120, 500).
(ii) Show that 17 and 22 are relatively prime.
Solution.
(i) Since 120 = 23 · 3 · 5 and 500 = 22 · 30 · 53 gcd(120, 500) = 22 · 30 · 5 = 20.
(ii) Since 17 = 20 · 110 · 171 and 22 = 2 · 11 · 170 , gcd(17, 22) = 20 · 110 · 170 = 1.
Hence, 17 and 22 are relatively prime
Problem 9.2
If two integers a and b have the property that their difference a−b is divisible
by an integer n, i.e., a − b = nq for some integer q, we say that a and b are
congruent modulo n. Symbolically, we write a ≡ b mod n. Show that if
a ≡ b mod n and c ≡ d mod n then a + c ≡ b + d mod n.
Solution.
If a ≡ b mod n and c ≡ d mod n then there exist integers k1 and k2 such that
a−b = k1 n and c−d = k2 n. Adding these equations we find (a+c)−(b+d) =
kn where k = k1 + k2 ∈ Z. Hence, a + c ≡ b + d mod n
Problem 9.3
Show that if a ≡ b mod n and c ≡ d mod n then ac ≡ bd mod n.
Solution.
Using the notation of the previous problem, we he ac−bc = k1 cn and cb−bd =
k2 bn. Adding these equations we find ac − bd = kn where k = k1 c + k2 b ∈ Z.
Hence, ac ≡ bd mod n
Problem 9.4
Show that if a ≡ a mod n for all integer a.
Solution.
Since a − a = n(0), we have a ≡ a mod n
1
Problem 9.5
Show that if a ≡ b mod n then b ≡ a mod n.
Solution.
From a ≡ b mod n, we have a − b = nq for some q ∈ Z. Multiply through by
−1 to obtain b − a = n(−q) = nq 0 . That is, b ≡ a mod n
Problem 9.6
Show that if a ≡ b mod n and b ≡ c mod n then a ≡ c mod n.
Solution.
From a ≡ b mod n and b ≡ c mod n, we obtain a − b = nq1 and b − c = nq2
where q1 , q2 ∈ Z. Adding these two equations, we find a−c = n(q1 +q2 ) = nq.
Hence, a ≡ c mod n
Problem 9.7
What are the solutions of the linear congruences 3x ≡ 4(mod7)?
Solution.
By previous problem, we have 9x ≡ 12 mod 7. Since 7x ≡ 0 mod 7, using
Problem 9.2, we have 2x ≡ 12 mod 7. This, the given equation, and Problem
9.2 lead to x ≡ −8 mod 7. Hence, x = 7k − 8 where k ∈ Z
Problem 9.8
Solve 2x + 11 ≡ 7(mod3)?
Solution.
From −11 ≡ −11(mod 3) and −4 ≡ 2(mod 3) we can write 2x ≡ 2(mod 3).
Multiply by 2 to obtain 4x ≡ 4(mod 3). Thus, 4x ≡ 1(mod 3). From −3x ≡
0(mod 3) we obtain x ≡ 1(mod 3)
Problem 9.9
Use the Euclidean algorithm to find gcd(414, 662).
Solution.
Using the division algorithm we have
662
414
248
164
84
80
=
=
=
=
=
=
414 × 1 + 248
248 × 1 + 164
164 × 1 + 84
84 × 1 + 80
80 × 1 + 4
20 × 4 + 0
2
Hence, gcd(414, 662) = 20
Problem 9.10
Use the Euclidean algorithm to find gcd(287, 91).
Solution.
Using the division algorithm we have
287 = 91 × 3 + 14
91 = 14 × 6 + 7
14 = 7 × 2 + 0
Hence, gcd(287, 91) = 2
3

Bestand - Bolero

UPC 000298103858 016162190749 017149263760

MATH 215 – Number Theory I (NTI) Assumptions: For

ZR und ER Paarungen

RCCBs - Residual current circuit breakers GCD