Chapter 3 builds \mathbb{Z}_n, the group U(n) of units modulo n, and Euler's phi function. All three sit on top of one repeated computation: divide, keep the remainder, divide again. That repeated computation is the Euclidean algorithm for the greatest common divisor. It is genuinely new material. Discrete Math I never covered gcd or Euclid's algorithm, so chapter 3 builds both from scratch, right where they're needed. What this section can honestly recall is just one piece Discrete Math I already gave you: the division algorithm itself. That algorithm's single step is exactly what Euclid's algorithm repeats over and over.
Picture dealing a deck of cards evenly among a fixed number of players. The quotient is how many full rounds everyone gets. The remainder is whatever's left in your hand once an even round stops being possible. It is always fewer cards than there are players, and never negative. Two hands with the same leftover are related. Deal them to the same number of players, and they land in exactly the group chapter 3 calls one residue class.
Divisibility is the relationship between two integers where one divides evenly into the other, with nothing left over. The division algorithm is the theorem that makes this precise for every pair, not just the evenly-dividing ones. Take an integer a and a positive integer b. The theorem guarantees unique integers q and r with a = bq + r and 0 \le r < b. Write b \mid a ("b divides a") exactly when r = 0. Divisibility is just the special case of the division algorithm where the remainder vanishes. The same statement runs both directions. Take a and b that leave the same remainder when divided by n. That is exactly the relation chapter 3's residue classes are built from. Euclid's algorithm, a few sections from now, repeatedly applies the division algorithm to a shrinking pair of numbers. Replace (a,b) with (b,r) and divide again. That single move, repeated, is the entire content of Euclid's algorithm for the greatest common divisor.
Theorem
The Division Algorithm
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Divisibility, parity, and remainders — first taught there.
For any integer a and any positive integer b, there exist unique integers q (the quotient) and r (the remainder) such that a = bq + r, \qquad 0 \le r < b.
Existence. Consider the set of nonnegative integers of the form a - bk for integer k: \{\ldots, a-2b,\ a-b,\ a,\ a+b,\ a+2b,\ \ldots\} \cap \{0, 1, 2, \ldots\}. This set is nonempty — for k negative enough, a-bk grows without bound in the positive direction — so by the well-ordering principle it has a least element; call it r, achieved at some k=q, so r = a-bq, i.e. a = bq+r. If r \ge b, then r-b = a-b(q+1) \ge 0 would be a smaller nonnegative element of the same set, contradicting that r was least. So 0 \le r < b.
Uniqueness. Suppose a = bq_1+r_1 = bq_2+r_2 with both remainders in [0,b). Subtracting gives b(q_1-q_2) = r_2-r_1, so b divides r_2-r_1. But -b < r_2-r_1 < b, and the only multiple of b strictly between -b and b is 0, so r_1=r_2, which forces q_1=q_2 as well.
Quotient and remainder mod 5, live
Send a chip through -- f(x)=\lfloor x/5 \rfloor computes the quotient, g(x)=x-5\lfloor x/5\rfloor computes the remainder. Confirm every remainder that comes out is between 0 and 4.
Loading interactive…
Recipe Find q and r from the division algorithm Use when: you have integers a and a positive b and need the unique q, r with a = bq + r and 0 \le r < b Goal: the exact quotient and remainder pair guaranteed by the division algorithm, even when a is negative
Quick recipe
-
1
Compute a/b as a decimal and take the whole number part as a first guess for q.
Example
For a=100, b=7: 100/7 \approx 14.28, so the whole-number part gives a first guess of q=14.
Why: q has to be an integer, and the division algorithm's q is built directly from how many whole copies of b fit into a.
-
2
Subtract bq from a using the guessed q, and check whether the result satisfies 0 \le r < b.
Example
For a=-17, b=5: -17/5=-3.4, whole-number part gives q=-3, and r=-17-5(-3)=-17+15=-2, which is negative. Lower q to -4: r=-17-5(-4)=-17+20=3, and now 0 \le 3 < 5.
- a is zero or positive — the whole-number-part guess from Step 1 already gives a valid r in range, no fix needed.
- a is negative — the whole-number-part guess can leave r negative, and q must be lowered by 1 (made more negative) to fix it.
Why: the division algorithm requires 0 \le r < b exactly, and rounding toward zero on a negative a produces a remainder outside that range.
-
3
Check the remainder actually falls between 0 (inclusive) and b (exclusive), 0 \le r < b, before treating it as final.
Example
For a=100, b=7: r=100-7(14)=100-98=2, and 0 \le 2 < 7 holds, so q=14, r=2 is the finished answer.
Why: q and r only count as the division-algorithm pair once this range holds, otherwise it's some other, non-unique split of a.
Common mistakes
- Rounding q to the nearest integer instead of taking the whole-number part (floor), which can overshoot on negative a.
- Skipping the re-check of 0 \le r < b after using a calculator's raw decimal quotient.
- Reporting a negative remainder when a is negative, instead of lowering q by one.
- Mixing up "b divides a" (r=0) with "a divides b" (b \mid a means r=0 when a is the one being divided).
Worked example
Find q and r for a = 100, b = 7
-
1
This repeats the recipe above, Steps 1 through 3, on the same numbers used in the recipe's own examples. Write 100 = 7q + r with 0 \le r < 7.
-
2
The largest multiple of 7 not exceeding 100 is 7 \times 14 = 98.
-
3
100 - 98 = 2, and 0 \le 2 < 7.
-
4\boxed{100 = 7(14) + 2, \quad q=14,\ r=2}
Loading interactive…
Worked example
Sort several integers by their remainder mod 5
-
1
This applies the recipe's Steps 1-3 to five different numbers with the same divisor. Sort 12, 22, 8, 17, and 5 into groups by their remainder when divided by 5.
-
2
Divide each by 5: 12=5(2)+2, 22=5(4)+2, 8=5(1)+3, 17=5(3)+2, 5=5(1)+0.
-
3
Group by the remainder each one leaves behind, ignoring the quotient entirely.
-
4\boxed{\{12,22,17\}\text{ (remainder }2),\ \{8\}\text{ (remainder }3),\ \{5\}\text{ (remainder }0)}
Three of the five integers land in the same group — this is exactly the grouping chapter 3 names [2] inside \mathbb{Z}_5.
Loading interactive…
Where this goes next
Chapter 3: Modular arithmetic and cyclic groups
The greatest common divisor of a and b is computed by using the division algorithm reviewed here, over and over. Replace (a,b) with (b, r), where r is the remainder from dividing a by b. Repeat until r hits 0. That process, Euclid's algorithm, is new; chapter 3 covers it in full. But every step inside it is just one more use of the division algorithm above.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Which statement is true?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
18/4 = 4.5, not a whole number -- 4 does not divide 18.
This reverses the direction -- 18 does not divide 4, since 4/18 is not an integer.
Why
18 = 6\times3 exactly, so 6\mid18 is true.
From Discrete Mathematics I — Logic, Proof, and Structure
A student computes -17=5(-3)+(-2) and calls this the Division Algorithm's answer. What is wrong?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The Division Algorithm specifically requires 0\le r<b -- a negative remainder is never valid, even though a=bq+r holds arithmetically.
From Discrete Mathematics I — Logic, Proof, and Structure
What is the remainder when 53 is divided by 6?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
53 = 6(8)+5, and 0\le5<6, so the remainder is 5.
Correct answer
Also accepted:
Why