Solutions

DMMR Tutorial sheet 5
Number theory
October 15, 2014
Some of the exercises for this tutorial are taken the book: Kenneth Rosen, Discrete Mathematics and
its Applications, 7th Edition, McGraw-Hill, 2012.
1. Analogue to the definition of gcd we define the least common multiple (lcm) in the following way:
For two numbers a and b with the prime factorisation a = pa11 · ... · pann , b = pb11 · ... · pbnn we define
max(a1 ,b1 )
lcm(a, b) := p1
· ... · pnmax(an ,bn )
Show that if a and b are positive integers, then ab = gcd(a, b) · lcm(a, b).
Solution:
Take a set of primes {p1 , p2 , . . . pn } and natural numbers {a1 , a2 , . . . an , b1 , b2 , . . . bn } such that
a = pa11 pa22 · · · pann and b = pb11 p2b2 · · · pbnn . Then,
min(a1 ,b1 ) min(a2 ,b2 )
p2
· · · pnmin(an ,bn )
max(a1 ,b1 ) max(a2 ,b2 )
p1
p2
· · · pnmax(an ,bn )
gcd(a, b) = p1
lcm(a, b) =
Thus,
min(a1 ,b1 ) max(a1 ,b1 ) min(a2 ,b2 ) max(a2 ,b2 )
n ,bn ) max(an ,bn )
p1
p2
p2
· · · pmin(a
pn
n
min(a1 ,b1 )+max(a1 ,b1 ) min(a2 ,b2 )+max(a2 ,b2 )
n ,bn )+max(an ,bn )
p1
p2
· · · pmin(a
n
gcd(a, b) · lcm(a, b) = p1
=
Moreover, for every x, y it is true that min(x, y) + max(x, y) = x + y. Therefore,
gcd(a, b) · lcm(a, b) = pa11 +b1 pa22 +b2 · · · pann +bn
= pa11 pb11 pa22 pb22 · · · pann pbnn
= ab
2. Show that if n | m, where n and m are integers greater than 1, and if a ≡ b(mod m), where a and
b are integers, then a ≡ b(mod n)
Solution:
The hypothesis a ≡ b(mod m) means that a = b + k1 · m for some k1 ∈ N. m | (a − b). Since
we are given that n | m, Lecture 12 p2 Theorem 3 implies that n | (a − b). By definition therefore
a ≡ b(mod n).
3. Use the Euclidean Algorithm to find
(a) gcd(12, 18)
1
(b) gcd(111, 201)
(c) gcd(1001, 1331)
(d) gcd(12345, 54321)
(e) gcd(1000, 5040)
(f) gcd(9888, 6060)
Solution:
(a) gcd(12, 18) = gcd(12, 6) = gcd(6, 0) = 6
(b) gcd(111, 201) = gcd(111, 90) = gcd(90, 21) = gcd(21, 6) = gcd(6, 3) = gcd(3, 0) = 3
(c) gcd(1001, 1331) = gcd(1001, 330) = gcd(330, 11) = gcd(11, 0) = 11
(d) gcd(12345, 54321) = gcd(12345, 4941) = gcd(4941, 2463) = gcd(2463, 15) = gcd(15, 3) =
gcd(3, 0) = 3
(e) gcd(1000, 5040) = gcd(1000, 40) = gcd(40, 0) = 40
(f) gcd(9888, 6060) = gcd(6060, 3828) = gcd(3828, 2232) = gcd(2232, 1596) = gcd(1596, 636) =
gcd(636, 324) = gcd(324, 312) = gcd(312, 12) = gcd(12, 0) = 12
4. Prove that the product of any three consecutive integers is divisible by 6
Solution:
We first prove the smaller version:
Every product of two consecutive integers is divisible by 2. The product can be written as a(a+1).
Consider the two following cases for a.
• If a is even, we can write a = 2k for some k ∈ Z. With this we get a(a + 1) = 2k(2k + 1) =
2(2k 2 + k). Since 2k 2 + k ∈ Z this is divisible by 2.
• If a is odd, then we can write a = 2k + 1 for some k ∈ Z. With this we get a(a + 1) =
(2k + 1)(2k + 2) = 2(2k 2 + 3k + 1). Since 2k 2 + 3k + 1 ∈ Z, this is divisible by 2.
The same proof can be carried out for “a(a + 1)(a + 2) is divisible by 3” in 3 cases.
With these two lemmas we can prove the desired statement: We showed the proof that a(a +
1)(a + 2) is divisible by 3. Since a(a + 1) | a(a + 1)(a + 2) and 2 | a(a + 1) we get that
2|a(a + 1)(a + 2). Combining these two we get 2 ∗ 3 = 6|a(a + 1)(a + 2).
n−1
Q
The general statement we used during this proof is “
a + i is divisible by n”. We extend our
i=0
proof to this statement: Consider k = a mod n. This value is per definition in {0, ..., n − 1}.
• If k = 0, then a = m · n for some m ∈ N. And we get
n−1
Y
(a + i) = n ·
i=0
with m ·
n−1
Q
(a + i)
m·
n−1
Y
!
(a + i)
i=1
∈ Z, which means the product is divisible by n.
i=1
2
• If k ∈ {1, ..., n − 1} we get that l = n − k ∈ {1, ..., n − 1}. Then we can write the product
as
l−1
n−1
Y
Y
(a + i) · (a + l) ·
(a + i)
i=0
i=l+1
Furthermore we know from the definition of mod that a = m · n + k for some m ∈ Z. This
means a + l = m · n + k + (n − k) = (m + 1) · n and we get
!
n−1
l−1
n−1
Y
Y
Y
(a + i) = n · (m + 1) · (a + i) ·
(a + i)
i=0
with
(m + 1) ·
l−1
Q
(a + i) ·
i=1
i=1
n−1
Q
i=l+1
!
(a + i)
∈ Z, which means the product is divisible by n.
i=l+1
5. This exercise is about computation of powers in modulo arithmetic. Throughout the exercise show
all your computations in detail, especially for the use of algorithms like the Euclidean algorithm.
(a) Use Fermat’s little theorem to compute 3302 mod 5, 3302 mod 7
Now we consider the modulus q = 35 and try to compute 3302 mod q.
(b) Why can we not use Fermat’s little theorem here?
(c) To compute 3302 mod q with q = 35 we write 3302 = 7 · a + 5 · b with a ∈ {0, ..., 4} and
b ∈ {0, ..., 6}. Prove that every element of Zq can be written in this way.
Hint: How many different results for 7 · a + 5 · b are there in Zq
(d) Use the result from a) and c) to compute 3302 (mod 35).
Solution:
(a) Fermat’s little theorem tells us that 34 ≡ 1 mod 5. Then, 3300 ≡ (34 )75 ≡ 175 ≡ 1 mod 5.
Thus, 3302 = 32 · 3300 ≡ 32 · 1 ≡ 4 mod 5. Therefore, 3302 mod 5 = 4.
Similarly, 36 ≡ 1 mod 7. Then, 3300 ≡ (36 )50 ≡ 150 ≡ 1 mod 7. Thus, 3302 = 32 · 3300 ≡
32 · 1 ≡ 2 mod 7. Therefore, 3302 mod 7 = 2.
(b) Fermat’s little theorem requires the modulus to be prime and here we have q = 5 ∗ 7
(c) We count how many different results there are for different a and b in the given range. There
are potentially 5 · 7 = 35 different combinations of a, b. We have to prove that they are
all different. To prove that assume two results are the same: 7a + 5b = 7a0 + 5b0 We can
transform this into 7(a − a0 ) = 5(b0 − b). We see that this number has to be divisible by 7
(due to the left hand side) and divisible by 5 (due to the right hand side). Since 5 and 7 are
co-prime, that means this number is divisible by 35: 7(a − a0 ) = 35 · k for some k ∈ Z. By
division by 7 we get (a − a0 ) = 5k. We also have 0 ≤ a, a0 < 5 and therefore a − a0 < 5 − 0
and a − a0 > 0 − 5 = −5. Thus the only valid k is k = 0 and we have a = a0 . The second
statement b = b0 is analogous.
We have proven that if two representations 7a + 5b are equal, then the arguments a, b are
already equal. Therefore we have 35 different results for 7a + 5b. As there are only 35
elements in Zq namely {0, ..., 34}, we get that every one of those elements is representable
by this notation.
3
(d) Consider the notation from c) mod 5. We get
7a + 5b ≡
3302 (mod 5)
7a ≡
3302 (mod 5)
7a ≡
4(mod 5)
a≡
7
−1
· 4(mod 5)
Equivalently with mod 7 we get b = 5−1 · 2 mod 7. Using the EEA we can calculate 5−1 =
3 mod 7 and 7−1 = 2−1 = 3(mod 5). Putting those values into 7a + 5b we get 3302 =
9(mod 35).
Solutions (to the last question on the sheet) must be handed in on paper at the ITO by
Wednesday, 22 October, 4:00pm.
4

Download Report