Discrete Mathematics
Homework № 5 - Solution
November 19, 2022
Problem 1.
If p is prime, then ϕ(pk ) = pk − pk−1 . Prove this is the case.
Solution:
How many positive integers less than pk ? There are pk − 1. How many positive integers are
co-prime with pk ? Any number divisible by p is co-prime: if gcd(pk , a) = m > 1 then m|pk , then
p|m then p|a. Thus p, 2p, 3p, ...pk − p are the co-prime numbers. There are pk−1 − 1 of them.
Thus ϕ(pk ) = (pk − 1) − (pk−1 − 1) = pk − pk−1
Problem 2.
Proof that for any n ∈ N (n ≥ 1), there always exists n consecutive numbers that none of them
is prime.
Solution:
We will prove this by giving an example. For any n ∈ N (n ≥ 1), consider n consecutive numbers
(n + 1)! + 2, (n + 1)! + 3, ..., (n + 1)! + n and (n + 1)! + (n + 1). We know that for all i from 2
to n + 1, (n + 1)! + i is divisible by i since both (n + 1)! and i are divisible by i. In addition,
(n + 1)! + i > i. Therefore i is a divisor of(n + 1)! + i apart from 1 and (n + 1)! + i itself. This
implies that the above n numbers satisfy the condition given in the problem.
Problem 3.
Prove that ab = gcd(a, b) · lcm(a, b).
Solution:
Denote g = gcd(a, b) and l = lcm(a, b). Thus a = ga′ and b = gb′ where gcd(a′ , b′ ) = 1 for some
integers a′ , b′ . Thus ab = g 2 a′ b′ . If we can prove l = ga′ b′ we are done. First, clearly a|ga′ b′ and
b|ga′ b′ so l is a common multiple.
Any common multiple l satisfies l = ala = blb for some integers la and lb .
Suppose gcd(la , lb ) = gl > 1, then la = gl la′ and lb = gl lb′ for some integers la′ , lb′ . Then
l = agl la′ = bgl lb′ and so gl |l and l/gl < l is also a common multiple, and l cannot be least.
MATH2020 - Homework № 5 Page 1
Thus gcd(l/a, l/b) = gcd(la , lb ) = 1 for the least common multiple l. Since l = ga′ b′ satifies this
condition, it is also least.
Problem 4.
Compute (4399534567 + 155558585555 ) 4016665 mod (mod 36). Make sure you justify each step
(that is not normal integer arithmetic) with a relevant theorem or corollary.
Solution:
First step, take modulo 36 of all numbers that are not exponents.
(4399534567 + 155558585555 ) 4016665 (mod 36) = (334567 + 65555 ) 56665 (mod 36)
65555 contains the factor 62 = 36 so its mod is 0. 5 is co-prime with 36 so 5ϕ(36) = 1, and
ϕ(36) = ϕ(22 32 ) = (4 − 2)(9 − 3) = 12. Since 6665 (mod 12) = 5, 56665 = 55 = 3125 which is
29 modulo 36. Let us explore what happens with 3: 3, 32 = 9, 33 = 27, 34 = 81 = 9, ... thus
32n = 9 and 32n+1 = 3. Continuing, using these simplifications,
= (334567 + 65555 ) 56665 (mod 36) = (3 + 0) · 29 (mod 36) = 15
Note you can always check you working using
[Link]
but to show your working you needed to show the steps.
Problem 5.
Prove that if a ≡ b (mod m), then for all natural numbers n that n | a and n | b, we have
a b m
≡ mod
n n gcd(m, n)
Solution:
Let lcm(m, n) be the lowest common multiple of m and n. We first prove that:
mn = gcd(m, n) lcm(m, n)
Let d = gcd(m, n) and m = dm′ , n = dn′ where gcd(m′ , n′ ) = 1, we have:
mn d2 m′ n′
= = dm′ n′ = m′ n = mn′
d d
Therefore, m|dm′ n′ and n|dm′ n′ , which implies that lcm(m, n)|dm′ n′ (1).
We also have
m| lcm(m, n) ⇒ lcm(m, n) = mk = dm′ k
⇒ dn′ = n| lcm(m, n) = dm′ k
⇒ n′ |m′ k ⇒ n′ |k( since gcd(m′ , n′ ) = 1)
MATH2020 - Homework № 5 Page 2
Therefore, dm′ n′ |dm′ l = lcm(m, n) (2)
mn
From (1) and (2), lcm(m, n) = dm′ n′ = ⇒ mn = d lcm(m, n) = gcd(m, n) lcm(m, n)
d
Back to the problem, we have m|(a − b) and n|(a− b). This implies
n)|(a − b).
that lcm(m,
mn m a b a b m
Therefore, |(a − b) ⇒ | − ⇒ ≡ mod
gcd(m, n) gcd(m, n) n n n n gcd(m, n)
Problem 6. Programming
Follow the Slide#16 (Primality Test) of Lecture 10, and write a program in Python or Java (pre-
ferred) to input a large big number (the input is a random large number), and implement a
primality test algorithm to test if this is a (probable) prime number. If not, find the smallest
(probable) prime number larger than this number (e.g., checking one by one), and print out this
number.
Note 1. A primality test using Euler theorem with checking 100 value of a is sufficient. You can
implement Miller-Rabin primality test if you like.
Note 2. You have to implement an algorithm yourself, including fast computing ak mod n for
large a, k, n if necessary, rather than using built-in functions.
MATH2020 - Homework № 5 Page 3