• This repository contains solutions -and related work- for some of the exercises presented in From Mathematics to Generic Programming. So far,

Chapter 3: Ancient Greek Number Theory

• Exercise 3.6: Prove that if n and m are coprime, then sigma(nm) = sigma(n) sigma(m).
• Exercise 3.7: Prove that every even perfect number is a triangular number.
• Exercise 3.8: Prove that the sum of the reciprocals of the divisors of a perfect number is always 2.

Chapter 4: Euclid's Algorithm

• Exercise 4.3: Prove that sqrt_3(16) + sqrt_3(54) = sqrt_3(250).
• Exercise 4.4: Prove that, for any odd square number x there is an even square number y such that x+y is a square number.
• Exercise 4.5: Prove that, if x and y are both sums of two squares, then so is their product xy.

Chapter 5: The Emergence of Modern Number Theory

• Exercise 5.1: Prove that if n > 4 is composite, then (n-1)! is a multiple of n.

Chapter 6: Abstraction in Mathematics

• Exercise 6.3: Prove that any group has at least one element.
• Exercise 6.4: What is the order of e? Prove that e is the only element of such order.
• Exercise 6.5: Prove that if a is an element of order n, then a^{-1} = a^{n-1}.
• Exercise 6.7: Prove that any subgroup of a cyclic group is cyclic.
• Exercise 6.8: Prove that any cyclic group is abelian.
• Exercise 6.10: Prove that every group of prime order is cyclic.

Chapter 7: Deriving a Generic Algorithm

• Exercise 7.1: How many additions are needed to compute fib0(n)?
• Exercise 7.2: Implement Fibonacci numbers using power (code for solving arbitrary linear recurrences also provided).

Chapter 8: More Algebraic Structures

• Exercise 8.7: Compute the transitive closure of a graph using matrix multiplication on boolean semirings.
• Exercise 8.8: Compute shortest paths on a graph using matrix multiplication on tropical semirings.

Chapter 11: Permutation Algorithms

• Exercise 11.1: Prove Cayley's theorem.
• Exercise 11.2: What is the order of Sn?
• Exercise 11.3: Prove that if n > 2, Sn is not abelian.
• Exercise 11.5: Design an in-place reverse algorithm for forward iterators.
• Exercise 11.9: Prove that if a rotation of n elements has a trivial cycle, then it has n trivial cycles.
• Exercise 11.11: How many assignments does 3-reverse rotate perform?

Chapter 12: Extensions of GCD

• Exercise 12.2: * Prove that an ideal I is closed under subtraction. * Prove that I contains 0.
• Exercise 12.3: Prove that all the elements of a linear combination ideal are divisible by any of the common divisors of a and b.
• Exercise 12.4: Prove that any element in a principal ideal is divisible by the principal element.
• Exercise 12.5: Using Bézout's identity, prove that if p is prime, then any 0 < a < p has multiplicative inverse modulo p.
• Exercise 12.7: Develop a version of the extended GCD algorithm based on Stein's algorithm.

Chapter 13: A Real-World Application

• Exercise 13.1: Implement the function bool is_carmichael(n).
• Exercise 13.2: Find the first seven Carmichael numbers using your function.