Material

The material for the exam consists of the material covered in the lectures up to and including Friday, Feb 6^th, as well as Problem Sets 1 through 5. Here are some headings for the topics we covered:

• Arithmetic in 𝔽₂ (the field with two elements); vectors and linear equations over 𝔽₂. Application: the one-time pad.
• Proof by induction.
• Foundations of the natural numbers: Peano’s axioms; proving the laws of arithmetic, order, and divisibility; well-ordering.
• Foundations of the integers: divisibility and division with remainder, ideals, principal ideals.
• The integers: GCD and LCM, Euclid’s Algorithm and Bezout’s Theorem, Unique factorization. Application: irrational numbers.
• Congruences and modular arithemtic: definition of congruence and congruence classes; arithmetic modulu m; invertibility and inverses using Euclid’s algorithm; solving congruences. Application: tests for divisibility by 3, 9 and 11. Application: Luhn’s algorithm.
• ℤ∕mℤ: the set of congruence classes; systems of representatives; the laws of arithmetic in ℤ∕mℤ; invertibility; zero-divisors.

Structure

The exam will consist of several problems. Problems can be calculational (only the steps of the calculation are required), theoretical (prove that something holds) or factual (state a Definition, Theorem, etc). The intention is to check that the basic tools are at your fingertips.

Sample paper

1. (Unique factorization)
   1. [calculational] Write 148 as a product of prime numbers.
   2. [factual] State the Theorem on unique factorization of natural numbers.
   3. [theoretical] Prove that every natural number can be written as a product of irreducibles.
2. Solve the following system of equations in ℤ∕5ℤ:

3. Prove by induction that a_n = is an integer for all n ≥ 0.
4. (modular arithmetic)
   1. State the definition of a zero-divisor modulu m.
   2. What are the zero-divisors in ℤ∕15ℤ?
   3. How many non-zero-divisors are there in ℤ∕15ℤ?

Solutions

1. (Unique factorization)
   1. 148 = 2 ⋅ 74 = 2 ⋅ 2 ⋅ 37.
   2. “Every natural number n ≥ 1 can be written as a (possibly empty) product n = ∏ _i=1^dp_i of prime numbers, uniquely up to the order of the factors.” or “For every natural number n0 there exist unique natural numbers _{p prime}, all but finitely many of which are zero, such that n = ∏ _pp^e_p”.
   3. Let S be the set of natural numbers which are non-zero and which cannot be written as a (possibly empty) product of irrreducible numbers. If S is non-empty then by the well-ordering principle it has a least element n S. If n were irreducible, it would be equal to a product of irreducibles of length 1 (itself), so n must be reducible, that is of the form n = ab with 1 < a,b < n. But then a,bS (since n was minimal). It follows that both a and b are products of irreducibles, say a = ∏ _i=1^dp_i and b = ∏ _j=1^eq_j. In that case, n = ∏ _i=1^dp_i ⋅∏ _j=1^eq_j displays n as a product of irreducibles, a contradiction. It follows that S is empty, that is that every non-zero integer is a product of irreducibles.
2. Let (x,y,z) be a solution to the system. Adding the first two equations we see that [5]₅x + y = [3]₅. Since 5 ≡ 0(5) this reads y = [3]₅. Subtracting the first equation from the third gives: [2]₅x-y = [-3]₅, that is [2]₅x = y - [3]₅ = [0]₅. Since 2 is invertible modulu 5, we find x = [0]₅. Finally, from the last equation we read z = [1]₅. Thus, the only possible solution is x = [0]₅, y = [3]₅, z = [1]₅. We now check that this is, indeed a solution: 0 + 3 + 1 = 4 ≡ 4(5), 2 ⋅ 0 + 3 - 1 = 2 ≡ 2(5) and 3 ⋅ 0 + 1 = 1 ≡ 1(5) as required.
3. When n = 0 we have a_n = 0 which is an integer. Continuing by induction, we note that a_n+1 -a_n = - = ⋅ = ⋅ 2 = n + 1. Assuming, by induction, that a_n is an integer then shows that a_n+1 = a_n + (n + 1) is an integer as well.
4. (zero-divisors)
   1. “A number a is a zero-divisor modulu m if there exists b, b ⁄≡ 0(m), so that ab ≡ 0(m)” or “a residue class x ℤ∕mℤ is a zero-divisor if there exists y ℤ∕mℤ, y[0]_m, so that xy = [0]_m”.
   2. The zero-divisors are [0]₁₅,[3]₁₅,[5]₁₅,[6]₁₅,[9]₁₅,[10]₁₅,[12]₁₅.
   3. There are 7 zer0-divisors hence 8 = 15 - 7 non-zero-divisors.