## Math 342, Spring Term 2009 Pre-Midterm Sheet

February 8, 2009

### Material

The material for the exam consists of the material covered in the lectures up to and including Friday, Feb 6th, 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.

### 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 an = 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=1dpi 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 = ppep”.
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=1dpi and b = j=1eqj. In that case, n = i=1dpi j=1eqj 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]5x + y = [3]5. Since 5 0(5) this reads y = [3]5. Subtracting the first equation from the third gives: [2]5x-y = [-3]5, that is [2]5x = 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.
3. When n = 0 we have an = 0 which is an integer. Continuing by induction, we note that an+1 -an = - = = 2 = n + 1. Assuming, by induction, that an is an integer then shows that an+1 = an + (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 ∕mis a zero-divisor if there exists y ∕m, y[0]m, so that xy = [0]m”.
2. The zero-divisors are [0]15,[3]15,[5]15,[6]15,[9]15,[10]15,[12]15.
3. There are 7 zer0-divisors hence 8 = 15 - 7 non-zero-divisors.