Exercise 1: Modify the pow method to compute \(x^n\ \mathrm{mod}\ m\).
Exercise 2: Write a function in OCaml that given an integer \(n\), it returns the divisors of \(n\). (Can you make your function return a lazy list?)
Exercise 3: Write a function in OCaml that given two integers \(n\) and \(m\), returns the common divisors of \(n\) and \(m\). (Can you make your function return a lazy list?)
Exercise 4: Write a function in OCaml that computes the \(\mathrm{gcd}\).
Exercise 5: A Carmichael number is a composite number \(n\), which satisfies \(b^{(n-1)} \equiv 1\ (\mathrm{mod}\ n)\) for all \(b\) relatively prime to \(n\). Write a function in OCaml that given an integer \(k\), it returns a Carmichael number greater than \(k\).
These questions should aid your revision. Send me your answers if you want me to verify.
R1: State the definition of \(\vert\).
R2: Collect and prove the properties of \(\vert\).
R3: State the definition of \(\mathrm{mod}\).
R4: Collect and prove the properties of \(\mathrm{mod}\).
R5: State the division theorem. What is the quotient and what is the remainder?
R6: How is \(\mathrm{rem}\) defined?
R7: State the definition of \(+_m\) for \(m \in\mathbb{N}\).
R8: Collect and prove the properties of \(+_m\).
Exercise 1: Show that \(\sqrt{\sqrt{2}}\) is irrational.
Exercise 2: Show that \(2^{1/n}\) is irrational for $n \in \mathbb{N}$ and \(n > 1\).
Exercise 3: Find \(x\) such that \(\sum_{k=1}^{1000} k! \equiv x \ (\mathrm{mod\ } 30)\).
Exercise 4: For $n \in \mathbb{N}$ and $n \geq 1$, show that
Exercise 5: For what values of \(n \in \mathbb{N}\) is \(\sum_{k = 1}^{n} k!\) a square?
Exercise 6 [Fibonacci’s Algorithm]: Egyptian mathematicians represented rational numbers between \(0\) and \(1\) as sums of unit fractions \(1/x_1 + \ldots + 1/x_k\), where \(x\)’s are distinct positive integers. For example, they wrote \(1/3 + 1/15\) instead of \(2/5\). Prove that it is always possible to do this in a systematic way: If \(0 < m/n < 1\), then
\[\frac{m}{n} = \frac{1}{q} + \left\lbrace \text{representation of } \frac{m}{n} - \frac{1}{q} \right\rbrace\]where \(q = \lceil \frac{n}{m} \rceil\). (Note: You need to show that all summands will be \(1/x_i\) for some \(x_i\) and the procedure produces a finite number of summands).
[Source: Exercise 3.9 in “Concrete Mathematics”]
Exercise 7:
R1: State and prove divisibility rules for \(3\), \(9\) and \(11\).
R2: What are the divisibility rules for \(4\), \(5\), \(6\) and \(8\)?
Exercise 1: (Assumes knowledge of \(\mathrm{gcd}\))
R1: State Fermat’s little theorem.
R2: Prove Fermat’s little theorem.
Exercise 1: Using Fermat’s Little theorem, solve \(5x \equiv 3 \ (\mathrm{mod\ } 11)\).
Exercise 2: Deduce that:
Exercise 3: Show that for \(p\) an odd prime:
R1: State the definition for the greatest common divisor.
R2: Collect and prove the properties of the gcd function.
R3: Show that the gcd algorithm computes a common divisor of the inputs.
R4: Show that the gcd algorithm computes the greatest common divisor of the inputs.
R5: Let \(a, n \in \mathbb{Z}^+\) with \(\mathrm{gcd}(a, n) = 1\). Show how to compute an element \(x \in \mathbb{Z}\) such that \(ax \equiv 1 \ (\mathrm{mod\ } n)\). Show how to compute all \(x \in \mathbb{Z}\) such that \(ax \equiv 1 \ (\mathrm{mod\ } n)\).
R6: Show that for \(a, b \in \mathbb{Z}^+\) and \(x, y \in \mathbb{Z}\) if \(ax + by = d\), then \(\mathrm{gcd}(a, b) \vert d\). This makes \(\mathrm{gcd}(a, b)\) the smallest possible linear combination of \(a\) and \(b\).
R7: Show that if \(ax + by = d'\) for \(a, b \in \mathbb{Z}^+\), \(d' \in \mathbb{Z}\) and \(\mathrm{gcd}(a, b) \nmid d'\), then it has no solutions.
R7: Show how the extended gcd algorithm computes a linear combination of \(\mathrm{gcd}(a, b)\) in terms of \(a, b \in \mathbb{Z}^+\).
R8: Let \(a, b \in \mathbb{Z}^+\) and \(x, y \in \mathbb{Z}\). Let \(g = \mathrm{gcd}(a, b)\). Show that if \(x_0, y_0 \in \mathbb{Z}\) is a solution to \(ax + by = g\), then
R9: State and prove Euclid’s theorem.
R10: State and prove the fundamental theorem of arithmetic.
Example: Solve the linear equation \(54 x + 21 y = 906\).
(solution) Run the gcd algorithm, keeping on the RHS the current remainder as a linear combination of the input terms \(54\) and \(21\).
| \(54 = 21 \cdot 2 + 12\) | \(12 = 54 + (-2) \cdot 21\) |
| \(21 = 12 \cdot 1 + 9\) | \(9 = 21 + (-1) \cdot 12 = 21 + (-1) \cdot (54 + (-2) \cdot 21) = (-1) \cdot 54 + 3 \cdot 21\) |
| \(12 = 9 \cdot 1 + 3\) | \(3 = 12 + (-1)\cdot 9 = (54 + (-2) \cdot 21) + (-1)\cdot ((-1) \cdot 54 + 3 \cdot 21) = 2\cdot 54 + (-5) \cdot 21\) |
| \(9 = 3\cdot 3\) |
Therefore, the \(gcd\) is \(3\) and the RHS gives us the coefficients for a linear combination of the gcd \(3 = 2\cdot 54 + (-5) \cdot 21\). Note that \(3 \vert 906\), since \(906 = 3\cdot 302\).
We have a solution for \(54x + 21y = 3\), but we need a solution for \(54x' + 21y' = 906\). Note that by multiplying the initial solution by \(302\) we get
\[302 \cdot (54 x_0 + 21 y_0) = 302 \cdot 3 \Leftrightarrow 54 (302 \cdot x_0) + 21 (302 \cdot y_0) = 906\]So, \(x_0' = 302 \cdot (2) = 604\) and \(y_0' = 302 \cdot (-5) = -1510\). Therefore, the general solution has the form (for \(k \in \mathbb{Z}\)):
\[x = x_0' + \left( \frac{21}{3} \right) \cdot k = 604 + 7 k\] \[y = y_0' - \left( \frac{54}{3} \right) \cdot k = -1510 - 18k\ \ \ \ \blacksquare\]Exercise 1: Determine whether the following equations have solutions for \(x, y \in \mathbb{Z}\). If they do find an initial solution and state the general form for all solutions.
Note: Check your solutions using this tool.
Exercise 2: Use the fundamental theorem of arithmetic to compute the gcd and lcm of the following pairs of natural numbers (Hint: write the answers in factored form):
Exercise 3: Find the prime factorisations for:
Exercise 4: Prove that if \(p \vert a^n\), then \(p^n \vert a^n\).
Exercise 5: Show that for all \(k\in \mathbb{Z}\):
Exercise 6: Show that \(5k + 3\) and \(11k + 7\) are relatively prime.
Exercise 7: Given \(a, b \in \mathbb{Z}\) and \(\mathrm{gcd}(a, b) = 1\), show that \(\mathrm{gcd}(a - b, a + b) = 1\) or \(2\).
Exercise 8: Given \(a, b \in \mathbb{Z}\) such that \(\mathrm{gcd}(a, b) = 1\). Prove that \(\mathrm{gcd}(a^2, b^2) = 1\).
Exercise 9:
Exercise 10 [Chicken McNugget theorem]: In this exercise, we are trying to find for \(a, b \in \mathbb{Z}^+\) with \(\mathrm{gcd}(a, b)\), the largest \(m \in \mathbb{Z}\) that is not representable by \(ax + by = m\) for \(x, y \in \mathbb{N}\) (i.e. \(x \geq 0, y \geq 0\)).
R1: State the definition for a monoid.
R2: State the definition for a group.
Exercise 1 [Identity is unique]: Show that the identity element in a group is unique.
Exercise 2 [Inverses are unique]: Show that the inverse for each element in a group are unique.
Exercise 3: Let \((G, \cdot)\) be a group. Show that if for every \(a \in G\), \(a^2 = e\) (where \(e\) is the identity), then the group operator is commutative.
Exercise 4 [Subgroup]: A subset \(H \subseteq G\) of a group \((G, \cdot)\) is a subgroup iff \((H, \cdot)\) is a subgroup. Show that \((H, \cdot)\) being a subgroup of \((G, \cdot)\) is equivalent to \(e_G \in H\) and \(\forall a, b\in H a \cdot b^{-1} \in H\).
Note: Strictly speaking \(\cdot\) is the operator constrained on \(H\) when refered to the group \((H, \cdot)\).
Exercise 5 [Exponents in groups]: Let \((G, \cdot)\) be a group and \(a\in G\). For convenience,
Prove that:
Exercise 6 [Cyclic groups]: A group is cyclic if \(\exists a . \forall b .\exists n \in \mathbb{Z} . b = a^n\). The element \(a\) is called a generator of \(G\).