C960: Supplementary Practice Unit 2
C960 Module 4: Divisibility and Arithmetic
Determine xdivy and xmody for each pair of values below.
a. x = 252, y = 7
b. x = 1398, y = 13
c. x = −21, y = 33
d. x = −457, y = 22
Solution: Using the Division Algorithm in Lesson 2.3:
a. 252 = 36 · 7 + 0 so 252div7 = 36 and 252mod7 = 0
b. 1398 = 107 · 13 + 7 so 1398div13 = 107 and 1398mod13 = 7
c. −21 = −1 · 33 + 12 so −21div33 = −1 and −21mod33 = 12
d. −457 = −21 · 22 + 5 so −457div22 = −21 and −457mod22 = 5
Determine the value for each of the following. These can be done without a calculator.
a. 9 × 3 in Z20
b. 1526 mod7
c. (352 · 407)mod50
d. (13023 + 45052)mod10
Solution: Using the rules for arithmetic operations modulo n in Lesson 2.5:
a. Arithmetic in Z20 is the same as mod20, so we get 9 × 3mod20 = 27mod20 = 7
b. 1526 mod7 = (15mod7)26 mod7 = (1)26 mod7 = 1mod7 = 1
c. (352 · 407)mod50 = [(352mod50) · (407mod50)]mod50 = (2 · 7)mod50 = 14mod50 = 14
d. (13023 + 45052)mod10 = [(13023 mod10) + (45052 mod10)]mod10
= [((1302mod10)3 mod10) + ((4505mod10)2 mod10)]mod10
= [(23 mod10) + (52 mod10)]mod10
= [(8mod10) + (25mod10)]mod10 = [8 + 5]mod10 = 13mod10 = 3
Module 5: Prime Factorization, GCD, and Euclid’s Algorithm
Determine if the following values are prime.
a. 157
b. 481
c. 1907
, C960: Supplementary Practice Unit 2
d. 2021
Solution: You can use the box labeled ”Small factors” in Lesson 2.9, to reduce the number of potential factors
to check.
1. Prime
2. Not prime: 481 = 13 · 37
3. Prime
4. Not prime: 2021 = 43 · 47
For each pair of x and y values below,
i) Determine the greatest common divisor (GCD) of x and y. ii)
Write the gcd(x, y) as a linear combination of x and y. iii)
Determine the multiplicative inverse of xmody, if it exists.
a. x = 45, y = 55
b. x = 51, y = 72
c. x = 39, y = 44
d. x = 324, y = 431
Solution: To find the GCD, use the Euclidean Algorithm in Lesson 2.10. To find the linear combination, follow
the Extended Euclidean Algorithm in Lesson 2.11. For the multiplicative inverse, see Lesson 2.12: If gcd(x,y) =
1, then the multiplicative inverse exists and can be read off of the linear combination as the coefficient for
value x. If gcd(x,y) 6= 1, then the multiplicative inverse does not exist. a. (i) gcd(45,55) = 5
(ii) 5 = 5 · 45 − 4 · 55
(iii) gcd(45,55) 6= 1, so the inverse of 45mod55 does not exist
b. (i) gcd(51,72) = 3
(ii) 3 = 5 · 72 − 7 · 51
(iii) gcd(51,72) 6= 1, so the inverse of 51mod72 does not exist
c. (i) gcd(39,44) = 1
(ii) 1 = 8 · 44 − 9 · 39
(iii) gcd(39,44) = 1, so the inverse of 39mod44 is the coefficient of 39 in the linear combination.
That is, the inverse of 39 is −9mod44 = 35.
d. (i) gcd(324,431) = 1
(ii) 1 = 145 · 324 − 109 · 431
(iii) gcd(324,431) = 1, so the inverse of 324mod431 is the coefficient of 324 in the linear combination.
That is, the inverse of 324 is 145.
Page 2 of 8
C960 Module 4: Divisibility and Arithmetic
Determine xdivy and xmody for each pair of values below.
a. x = 252, y = 7
b. x = 1398, y = 13
c. x = −21, y = 33
d. x = −457, y = 22
Solution: Using the Division Algorithm in Lesson 2.3:
a. 252 = 36 · 7 + 0 so 252div7 = 36 and 252mod7 = 0
b. 1398 = 107 · 13 + 7 so 1398div13 = 107 and 1398mod13 = 7
c. −21 = −1 · 33 + 12 so −21div33 = −1 and −21mod33 = 12
d. −457 = −21 · 22 + 5 so −457div22 = −21 and −457mod22 = 5
Determine the value for each of the following. These can be done without a calculator.
a. 9 × 3 in Z20
b. 1526 mod7
c. (352 · 407)mod50
d. (13023 + 45052)mod10
Solution: Using the rules for arithmetic operations modulo n in Lesson 2.5:
a. Arithmetic in Z20 is the same as mod20, so we get 9 × 3mod20 = 27mod20 = 7
b. 1526 mod7 = (15mod7)26 mod7 = (1)26 mod7 = 1mod7 = 1
c. (352 · 407)mod50 = [(352mod50) · (407mod50)]mod50 = (2 · 7)mod50 = 14mod50 = 14
d. (13023 + 45052)mod10 = [(13023 mod10) + (45052 mod10)]mod10
= [((1302mod10)3 mod10) + ((4505mod10)2 mod10)]mod10
= [(23 mod10) + (52 mod10)]mod10
= [(8mod10) + (25mod10)]mod10 = [8 + 5]mod10 = 13mod10 = 3
Module 5: Prime Factorization, GCD, and Euclid’s Algorithm
Determine if the following values are prime.
a. 157
b. 481
c. 1907
, C960: Supplementary Practice Unit 2
d. 2021
Solution: You can use the box labeled ”Small factors” in Lesson 2.9, to reduce the number of potential factors
to check.
1. Prime
2. Not prime: 481 = 13 · 37
3. Prime
4. Not prime: 2021 = 43 · 47
For each pair of x and y values below,
i) Determine the greatest common divisor (GCD) of x and y. ii)
Write the gcd(x, y) as a linear combination of x and y. iii)
Determine the multiplicative inverse of xmody, if it exists.
a. x = 45, y = 55
b. x = 51, y = 72
c. x = 39, y = 44
d. x = 324, y = 431
Solution: To find the GCD, use the Euclidean Algorithm in Lesson 2.10. To find the linear combination, follow
the Extended Euclidean Algorithm in Lesson 2.11. For the multiplicative inverse, see Lesson 2.12: If gcd(x,y) =
1, then the multiplicative inverse exists and can be read off of the linear combination as the coefficient for
value x. If gcd(x,y) 6= 1, then the multiplicative inverse does not exist. a. (i) gcd(45,55) = 5
(ii) 5 = 5 · 45 − 4 · 55
(iii) gcd(45,55) 6= 1, so the inverse of 45mod55 does not exist
b. (i) gcd(51,72) = 3
(ii) 3 = 5 · 72 − 7 · 51
(iii) gcd(51,72) 6= 1, so the inverse of 51mod72 does not exist
c. (i) gcd(39,44) = 1
(ii) 1 = 8 · 44 − 9 · 39
(iii) gcd(39,44) = 1, so the inverse of 39mod44 is the coefficient of 39 in the linear combination.
That is, the inverse of 39 is −9mod44 = 35.
d. (i) gcd(324,431) = 1
(ii) 1 = 145 · 324 − 109 · 431
(iii) gcd(324,431) = 1, so the inverse of 324mod431 is the coefficient of 324 in the linear combination.
That is, the inverse of 324 is 145.
Page 2 of 8
