Discrete Mathematics for Computer Scientists -- Exercises Week 5 - ArithmeticDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
Exercises Week 5 - Arithmetic

Book: Chapter 5.1-5.4, Chapter 3.6-3.7. Lectures: Thursday+Friday, week 3; Monday, week 5.

Some answers are available.

The idea is that you should prepare these exercises at home, by yourself or with your group. If you have any questions, you can come to the exercise session and ask them to the assistants. (If you do not prepare in advance, there is little point in coming!)

Basic Exercises from the Book

Make sure you are comfortable with the following before you start the next exercises:

Chapter 5: 5.1-5.9. 5.16, 5.17. 5.19, 5.23, 5.24, 5.33.

Please do exercises 5.1-5.9 by using Euclid's method for computing the gcd explicitly (where applicable). And also use the method explained in the lectures to compute Bezout's identity explicity (where applicable).

More Exercises

Now, please think about these.

1. (a) Please compute the gcd of some numbers, using Euclid's algorithm. Use the exercises 5.1-5.9 from the book (see above) as inspiration.

(b) Please compute Bezout's identity for some numbers, using Euclid's algorithm. Again, use the exercises 5.1-5.9 from the book as inspiration.

(c) Please compute the solutions for a couple of instances of the Chinese Remainder Theorem. Use the exercises from the book as inspiration.

(If you have done the exercises from the book above, you don't have to do this exercise of course.)

2. (Mini-tentan uppgift 5) For the following two equiations, investigate whether or not they have any solutions. If the equation has solutions, give three different ones.

(a) 14x + 21y = 30     (for x,y ∈ ℤ)

(b) 9x + 15y = 21     (for x,y ∈ ℤ)

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. (Exercise 5.13 from the book) 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. (Exercise 5.14 from the book) 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. (Exercise 5.15 from the book) For what 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.

    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.

    (See also exercise 5.22 from the book.)

    9. (Exercise 5.21 from the book) Show that if we have a ≡ b (mod mn) then we also have a ≡ b (mod n) and also a ≡ b (mod m).

    Starred Exercises

    These exercises are for students who are looking for a challenge.

    1*. 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 polyrythm for (n,m) is a rythm 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 polyrythm for (n,m)? In other words, how many beats does it take to repeat?

    Examples: A polyrythm for (2,3) takes 6 beats to repat: 

      |1 2 3 4 5 6|
2:|X   X   X  |
3:|X     X    |
    A polyrythm 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         |

    2*. There exists a direct proof using proof by contradiction of the uniqueness of prime factorization, without using gcd or Bezout's identity. 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 ⋅ A

    N = 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?