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 | p²-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 | a², then we also have p² | a².

Does this also hold when p is not prime? Explain.

6. For what integer numbers m do we have that m²-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} }

(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).

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    |

  |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 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 ⋅ 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?