Week 1 - Day 2: The Well-Ordering Axiom and Division Algorithm

In this session, we explored two important concepts in abstract algebra: the Well-Ordering Axiom and the Division Algorithm. Both are fundamental for understanding number theory and modular arithmetic, which are essential areas in abstract algebra.

The Well-Ordering Axiom

The Well-Ordering Axiom (WOA) states that every nonempty set of nonnegative integers contains a smallest element. This is a foundational property of the set of integers, which allows for many proofs by induction and similar techniques.

For example, consider the set:

\[ \{ 3, 2, 4 \} \]

In this case, the smallest element is \(2\).

When the Well-Ordering Axiom Does Not Hold

The Well-Ordering Axiom does not apply to other sets of numbers, such as the set of real numbers or rational numbers:

  • Real numbers: Consider the set \( (0,1] \). This set does not have a smallest element because for every number you choose, there is always a smaller number that is still positive.
  • Rational numbers: Consider the set \( \{ 0.1, 0.01, 0.001, \dots \} \). Again, this set lacks a smallest element because we can always find a smaller positive rational number.

The Division Algorithm

The Division Algorithm is a critical tool in number theory. It states that for any integers \(a\) and \(b\) where \(b > 0\), there exist unique integers \(q\) (the quotient) and \(r\) (the remainder) such that:

\[ a = bq + r \]

with \( 0 \leq r < b \). This allows us to express any integer as a combination of a multiple of another integer and a remainder.

Example: Division of 13 by 3

To understand the Division Algorithm in practice, consider the division of 13 by 3:

\[ 13 = 3(4) + 1 \]

The quotient is 4, and the remainder is 1. This confirms the relationship \( a = bq + r \), with \(0 \leq r < 3\).

Sketch of the Proof

To prove the Division Algorithm, we define the set of possible remainders:

\[ R = \{ a - bK : K \in \mathbb{Z} \} \]

This set contains all possible values of \(a - bK\). Using the Well-Ordering Axiom, we argue that this set contains a smallest nonnegative element, which we call \(r\). We then show that \(0 \leq r < b\) and that the quotient \(q\) and remainder \(r\) are unique.

Real-Life Example: Days of the Week

One common use of the Division Algorithm is in calculating the day of the week after a certain number of days. For example, what day will it be in 7001 days from now?

\[ 7001 = 7(1000) + 1 \]

This tells us that after 7000 days (1000 weeks), we’ll be back on the same day, and the extra day means it will be the next day of the week. If today is Wednesday, then 7001 days from now will be Thursday.

Modular Arithmetic with Complex Numbers

Modular arithmetic doesn’t just apply to integers. It can be used with complex numbers, too. Consider the powers of the imaginary unit \(i\):

  • \(i^0 = 1\)
  • \(i^1 = i\)
  • \(i^2 = -1\)
  • \(i^3 = -i\)
  • \(i^4 = 1\)

Notice that every fourth power of \(i\) repeats the cycle. This allows us to compute large powers of \(i\) easily by reducing them modulo 4:

  • \(i^{400} = (i^4)^{100} = 1\)
  • \(i^{401} = i^{400 + 1} = i\)

Theorem (HW \#1.1.10)

This theorem explores the relationship between division and remainders. If two integers leave the same remainder when divided by \(n\), then their difference is a multiple of \(n\):

\[ a \equiv b \ (\text{mod} \ n) \quad \Leftrightarrow \quad a - b = kn \quad (k \in \mathbb{Z}) \]

For example, \(a + 1\) and \(a + 19\) leave the same remainder when divided by 9 because:

\[ (a + 19) - (a + 1) = 18 = 2 \cdot 9 \]

Another Perspective

Another way to understand this theorem is that adding the divisor does not change the remainder. For example, in modular arithmetic, adding 9 repeatedly does not affect the remainder when dividing by 9.

Proof of the Theorem

Let’s prove that if two integers leave the same remainder when divided by \(n\), their difference is a multiple of \(n\):

Suppose \(a\) and \(c\) are integers that leave the same remainder when divided by \(n\), and call that remainder \(r\). By the Division Algorithm, we can write:

\[ a = nq_a + r \quad \text{and} \quad c = nq_c + r \]

Then:

\[ a - c = (nq_a + r) - (nq_c + r) = n(q_a - q_c) \]

This shows that \(a - c\) is a multiple of \(n\), completing the proof. \( \blacksquare \)