Pre-Midterm Sheet

February 8, 2009

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 𝔽
_{2}(the field with two elements); vectors and linear equations over 𝔽_{2}. 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.

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.

- (Unique factorization)
- Solve the following system of equations in ℤ∕5ℤ:
- Prove by induction that a
_{n}= is an integer for all n ≥ 0. - (modular arithmetic)

- (Unique factorization)
- 148 = 2 ⋅ 74 = 2 ⋅ 2 ⋅ 37.
- “Every natural number n ≥ 1 can be written as a (possibly empty)
product n = ∏
_{i=1}^{d}p_{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 = ∏_{p}p^{ep}”. - 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}^{d}p_{i}and b = ∏_{j=1}^{e}q_{j}. In that case, n = ∏_{i=1}^{d}p_{i}⋅∏_{j=1}^{e}q_{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.

- Let (x,y,z) be a solution to the system. Adding the first two equations we see
that [5]
_{5}x + y = [3]_{5}. Since 5 ≡ 0(5) this reads y = [3]_{5}. Subtracting the first equation from the third gives: [2]_{5}x-y = [-3]_{5}, that is [2]_{5}x = y - [3]_{5}= [0]_{5}. Since 2 is invertible modulu 5, we find x = [0]_{5}. Finally, from the last equation we read z = [1]_{5}. Thus, the only possible solution is x = [0]_{5}, y = [3]_{5}, z = [1]_{5}. 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. - 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. - (zero-divisors)
- “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}”. - The zero-divisors are [0]
_{15},[3]_{15},[5]_{15},[6]_{15},[9]_{15},[10]_{15},[12]_{15}. - There are 7 zer0-divisors hence 8 = 15 - 7 non-zero-divisors.

- “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]