Math 342, Spring Term 2009
February 8, 2009
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.
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)
- [calculational] Write 148 as a product of prime numbers.
- [factual] State the Theorem on unique factorization of natural
- [theoretical] Prove that every natural number can be written as a
product of irreducibles.
- Solve the following system of equations in ℤ∕5ℤ:
- Prove by induction that an = is an integer for all n ≥ 0.
- (modular arithmetic)
- State the definition of a zero-divisor modulu m.
- What are the zero-divisors in ℤ∕15ℤ?
- How many non-zero-divisors are there in ℤ∕15ℤ?
- (Unique factorization)
- 148 = 2 ⋅ 74 = 2 ⋅ 2 ⋅ 37.
- “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 = ∏
- 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 = ∏
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.
- Let (x,y,z) be a solution to the system. Adding the first two equations we see
that 5x + y = 5. Since 5 ≡ 0(5) this reads y = 5. Subtracting the first
equation from the third gives: 5x-y = [-3]5, that is 5x = y - 5 = 5.
Since 2 is invertible modulu 5, we find x = 5. Finally, from the last equation
we read z = 5. Thus, the only possible solution is x = 5, y = 5, z = 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 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.
- “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ℤ, ym, so that xy = m”.
- The zero-divisors are 15,15,15,15,15,15,15.
- There are 7 zer0-divisors hence 8 = 15 - 7 non-zero-divisors.