Preparation
Lectures: Thursday+Friday, week 3; Monday, week 4.
Read: Lehman, Leighton, and Meyer: Chapter 9.
Exercises from the Book
Make sure you are comfortable with the following before you start the next exercises:
Chapter 9: Problems 9.3 (gcd), 9.4 (gcd/lcm), 9.8 (pulveriser), 9.9 (numbers-84-108), 9.10 (true/false), 9.28(a,b), 9.30 (equivalent statements).
Exercises
(1.) (a) Please compute gcd(117,17), gcd(52,56), and gcd(123,126), using Euclid's method.
(b) Please compute x and y such that 117x + 17y = gcd(117,17), 52x + 56y = gcd(52,56), and 123x + 126y = gcd(123,126).
(c) Please compute one x such that x ≡ 3 (mod 5), x ≡ 4 (mod 7), and x ≡ 5 (mod 11).
(2.) For the following two equations, investigate whether or not they have any solutions. If the equation has solutions, give three different ones.
(a) 14x + 21y = 30 (for x,y ∈ \(\mathbb {Z}\))
(b) 9x + 15y = 21 (for x,y ∈ \(\mathbb {Z}\))
(3.) Look at the following relations:
R1(x,y) = x | y (divisability)
R2(x,y) = gcd(x,y)=1 (having no divisors in common)
R3(x,y) = true (the universal relation that relates everything to everything)
R4(x,y) = false (the empty relation that relates nothing)
And answer, for each relation, the following questions:
(a) Is it reflexive?
(b) Is it symmetric?
(c) Is it transitive?
(d) Is it an equivalence relation?
(4.) Show that if p is a prime number > 3, then 24 | p2-1.
Hint: Use a case split on what the remainder (rest) of p can be when dividing it by 6.
(5.) Show the following: If we have a prime number p such that p | a2, then we also have p2 | a2.
Does this also hold when p is not prime? Explain.
(6.) For what integer numbers m do we have that m2-1 is a prime number?
(7.) We have a natural number n > 1 that is not a prime number. Show that there must be a natural number b, such that 1 < b ≤ √n and b | n.
Suppose someone gives you a number N less than 100, and you have to check if it is a prime number or not. You investigate divisibility of N with different numbers. What divisors do you have to check in order to be sure if N is prime or not?
(8.) Let a and b be two positive natural numbers such that gcd(a,b) = 1.
Consider the following set:
S = { (k ⋅ a) `rest` b | k ∈ {0..b-1} }
Here, we write (p rest q) for the remainder (rest) of integer division of p with q. For example, 9 rest 3 = 0, and 9 rest 7 = 2.
(a) How many different elements does S have? Explain.
(b) What happens when gcd(a,b) is something else than 1? Try it for two specific numbers a and b.
(9.) Show that if we have a ≡ b (mod mn) then we also have a ≡ b (mod n) and also a ≡ b (mod m).
(10.) The least common multiple of two integer numbers a and b (also written as lcm(a,b)) is the least positive number m such that a | m and b | m.
For example, lcm(2,5) = 10, because 2 | 10 and 5 | 10, and this does not hold for any smaller number.
For example, lcm(6,8) = 24, because 6 | 24 and 8 | 24, and this does not hold for any smaller number.
(a) Can you invent a way of computing the lcm? Hint: use the gcd.
(b) A polyrhythm for (n,m) is a rhythm where we have one heavy beat every n beats, and also one heavy beat every m beats, played at the same time. How long time does it take to loop a polyrhythm for (n,m)? In other words, how many beats does it take to repeat?
Examples: A polyrhythm for (2,3) takes 6 beats to repat:
|1 2 3 4 5 6| 2:|X X X | 3:|X X |
A polyrhythm for (3,5) takes 15 beats to repat:
|1 2 3 4 5 6 7 8 9 101112131415| 3:|X X X X X | 5:|X X X |
Starred Exercises
These exercises are for students who are looking for a challenge.
(1*.) Given a natural number n, we look at the following six consecutive numbers:
n, n+1, n+2, n+3, n+4, n+5
We would like to divide these numbers into two separate groups, such that multiplying all numbers in one group has the same result as multiplying all numbers in the other group.
Show that this is impossible, for all natural numbers n!
Hint: This can be done in multiple ways. Here, we do the following. Show that it is always the case that one of the six numbers must have a prime factor that the other numbers do not have.
(a.) Why does this mean it is impossible?
(b.) How do you show this?
(2*.) There exists a direct proof (by contradiction) of the uniqueness of prime factorization, without using gcd or the Pulveriser. In this exercise, I want you to reconstruct that proof.
It goes roughly as follows: Suppose we have a number that can be prime factorized in two different ways. Then there must be a least such number, let's call it N.
Since N has two different prime factorizations, there is one in which the smallest prime is p, and another one in which the smallest prime is q. We also know p /= q. So:
N = p ⋅ AN = q ⋅ B
We also know that not(p | B) and that not(q | A). (Why?).
One of p and q must be the smallest, let us assume it is q, so q < p. We now look at the number M, defined as follows:
M = N - q ⋅ A
It turns out that this number is (1) smaller than N, (2) still positive, and (3) also has two different prime factorizations.
This contradicts our assumption that N was the smallest number that has two different prime factorizations. So this can't happen!
(a) Can you show (1), (2), and (3)?
(b) Can you write down the complete proof?