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:

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:
    (
|{x + y+ z     = [4]5
 [2]5x + y- z  = [2]5
|(
 [3]5x + z     = [1]5

  3. Prove by induction that an = n(n+1)
   2 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 n⁄=0 there exist unique natural numbers {ep}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,b∈∕S (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 = (n+1)(n+2)
    2 -n(n+1)-
  2 = (n+1)-
  2 ((n + 2)- n) = n+1
 2 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.