Homework 1
Division notation, mod arithmetic, inverses
Division notation
1 Use the Division Algorithm to show that 13 6 | 135.
2 Use the Division Algorithm to determine if 13 | −179. If not then find the remainder as well.
3 Show that if n = pqr with integers p, q, r > 1 then then it has a factor ≤
√3 n.
E.g. n = 847 = 7 · 112
is the product of 3 or more primes. The cube root √3
847 = 9.5 and
indeed 847 has a factor ≤ 9.5.
4 Show that if a | b and 4b | c then
2a | (6b + 7c)
You must work with basic definitions, not a theorem.
5 Methodically determine if 221 is prime or composite. You must use the following approach:
Find the minimum set of potential factors that need to be checked.
Check all of them using the Division Algorithm.
Reach a conclusion. If composite then find also find the prime factorization.
6 Approximately how many primes are less than 1, 000, 000? Less than 1, 001, 000?
Your answer should be based on the Prime Number Theorem.
7 Use your previous two answers to fill in the blank: “Approximately one out of every
odd numbers near 1, 000, 000 are prime.”
8 If you want to check if a 20 digit number is prime then how many potential factors do you
need to test?
Hints: A 20 digit number will be less than 1020. You will use the Prime Number Theorem at
some point. Your answer will be in the ballpark of 500 million.
Continue to next page for questions on Modular Arithmetic.
Copyright ©2021 Ravi Montenegro
1
Modular Arithmetic
9 Find (135 mod 13) using the Division Algorithm.
10 Is 75 ≡ −8 mod 17? Do this in two ways:
(a) Compare 75 mod 17 and −8 mod 17.
(b) Determine if 17 | (75 − (−8)).
11 Find (129 · 173) mod 7 without taking the product 129 × 173.
Your answer must use properties of modular arithmetic. If you write 129 × 173 = 22317 at
any point in the work then you’re just repeating methods of question 9 and will get no credit.
12 Show that if 2a ≡ 2b (mod n), and 10 | n, then a ≡ b (mod 5).
E.g. 102 ≡ 312 (mod 30), and 10 | 30, so 51 ≡ 156 (mod 5).
13 Properties of ordinary arithmetic carry over to the mod-arithmetic setting, except when
division is involved. In this problem you will look at one such situation:
(a) In ordinary arithmetic, if x = y then 2x = 2y.
Show that if a ≡ b (mod n) then 2a ≡ 2b (mod n).
(b) In ordinary arithmetic, if 2x = 2y then x = y.
Why? If 2x = 2y then 2x
2 =
2y
2
and so x = y.
However, in mod-arithmetic the following statement is false:
If 2a ≡ 2b (mod n) then a ≡ b (mod n)
i. Give an example where n is even and 2a ≡ 2b (mod n) but a 6≡ b (mod n).
ii. Give an example where n is even and 2a ≡ 2b (mod n) and yet a ≡ b (mod n).
Hint: Pick any value of a, and then pick any b with a ≡ b (mod n).
iii. What if n is odd? Show that if n is odd and 2a ≡ 2b (mod n) then a ≡ b (mod n).
iv. Use properties of mod-inverses to explain why “mod-division by 2” always works
when n is odd but often fails when n is even.
(c) Do you see a pattern? For what type of integers n will it be true that
If 3a ≡ 3b (mod n) then a ≡ b (mod n)
14 Use brute force to find (27−1 mod 47), i.e. check x ≡ 1 mod 47, x ≡ 2 mod 47 until the
inverse is found.
15 Use your inverse to solve the equation
27x + 5 ≡ 2 mod 47
Copyright ©2021 Ravi Montenegro
2
Sample Solution