Day 2 — Factors, Primes & Integer Division

Day 2 — Factors, Primes & Integer Division

Day 4 — Factors, primes & FTA

Stage I · concept day
Goal: Define primes and composites; use the sieve idea; state FTA with uniqueness sketch; prove infinitely many primes; master gcd/lcm via primes and the identity \(\gcd\cdot\operatorname{lcm}=|ab|\); use coprimality.

Why this matters

Prime factorization is the structure theorem for positive integers under multiplication. GCD/LCM drive fractions, modular inverses (later), hash table sizing instincts, calendar/cycle problems, and simplifying rational expressions. Euclid’s proof is a model of pure existence argument you will reuse in logic weeks.

Theory

Divisibility

For \(a,b\in\mathbb{Z}\), we say \(a\) divides \(b\), written \(a\mid b\), if there exists \(k\in\mathbb{Z}\) with \(b=ak\).
Then \(a\) is a divisor (factor) of \(b\), and \(b\) is a multiple of \(a\).

Properties: \(a\mid a\); \(a\mid 0\) for all \(a\neq ?\) wait: actually \(a\mid 0\) for every \(a\) because \(0=a\cdot 0\). Also \(1\mid n\) for all \(n\); if \(a\mid b\) and \(b\mid c\) then \(a\mid c\) (transitivity).

Primes and composites

An integer \(n>1\) is prime if its only positive divisors are \(1\) and \(n\).
An integer \(n>1\) is composite if it is not prime (has a positive divisor \(d\) with \(1<d<n\)).
\(1\) is neither prime nor composite.
Negative integers are not called prime in the usual \(\mathbb{Z}_{>0}\) convention (sometimes one speaks of prime elements in rings later).

Small primes: \(2,3,5,7,11,13,17,19,23,\ldots\)
\(2\) is the only even prime.

Trial division and the sieve idea

To test if \(n\) is prime, it suffices to search for a divisor \(d\) with \(2\le d\le \sqrt{n}\): if \(n=ab\) with \(a,b>1\), then \(\min(a,b)\le\sqrt{n}\).

Sieve of Eratosthenes (idea): list \(2..N\); repeatedly mark multiples of each prime \(p\le\sqrt{N}\). Unmarked numbers are prime. This is a batch primality generator, not a deep algorithmic analysis today.

Fundamental theorem of arithmetic (FTA)

Theorem (FTA). Every integer \(n>1\) can be written as a product of primes \[n=p_1 p_2\cdots p_k\] (with \(k\ge 1\)), and this factorization is unique up to order of factors.

Often written with exponents: \[n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r},\qquad p_1<\cdots<p_r\text{ prime},\; e_i\ge 1.\]

Existence (sketch by strong induction / minimal counterexample). If \(n\) is prime, done. If composite, \(n=ab\) with \(1<a,b<n\); factor \(a\) and \(b\) by induction; concatenate.

Uniqueness (sketch). Suppose \(n=p_1\cdots p_k=q_1\cdots q_m\) with primes. Then \(p_1\) divides the product of \(q_j\)’s. Euclid’s lemma: if a prime \(p\) divides \(ab\), then \(p\mid a\) or \(p\mid b\) (proved via gcd / Bézout later fully; accept or sketch: if \(p\nmid a\) then \(\gcd(p,a)=1\) so \(1=px+ay\) and \(b=pbx+aby\) is multiple of \(p\)). Thus \(p_1\) equals some \(q_j\). Cancel and induct on size.

Euclid: infinitely many primes

Theorem. There are infinitely many prime numbers.

Proof (Euclid). Suppose there are only finitely many primes \(p_1,\ldots,p_k\). Let \[N=p_1 p_2\cdots p_k+1.\] Then \(N>1\), so \(N\) has a prime factor \(q\). But \(q\) cannot equal any \(p_i\), because \(N\bmod p_i=1\neq 0\). Contradiction. Hence there are infinitely many primes. \(\square\)

Note: \(N\) itself need not be prime (e.g. \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509\)); the argument only needs some new prime factor.

Greatest common divisor and least common multiple

For integers \(a,b\) not both zero, \(\gcd(a,b)\) is the largest positive integer dividing both.
\(\operatorname{lcm}(a,b)\) is the smallest positive common multiple (for \(a,b\neq 0\)).

Via prime factorizations. Write \[|a|=\prod p_i^{\alpha_i},\qquad |b|=\prod p_i^{\beta_i}\] (using the same primes, exponents \(\ge 0\) allowed). Then

\[ \begin{align*} \gcd(a,b)&=\prod p_i^{\min(\alpha_i,\beta_i)},\\ \operatorname{lcm}(a,b)&=\prod p_i^{\max(\alpha_i,\beta_i)}. \end{align*} \]

Identity \(\gcd\cdot\operatorname{lcm}=|ab|\)

Theorem. For nonzero integers \(a,b\), \[\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|.\]

Proof. For each prime, \(\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta\). Multiply over primes: product of gcd and lcm exponents matches product of \(|a|\) and \(|b|\) exponents. \(\square\)

Useful: \(\operatorname{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)}\).

Coprime (relatively prime)

\(a\) and \(b\) are coprime if \(\gcd(a,b)=1\).
Then \(\operatorname{lcm}(a,b)=|ab|\).

If \(\gcd(a,b)=1\) and \(a\mid bc\), then \(a\mid c\) (Euclid’s lemma generalization / Gauss’s lemma form)—used often later.

Euclidean algorithm (preview operational)

\(\gcd(a,b)=\gcd(b,a\bmod b)\) with \(\gcd(a,0)=|a|\). Full division algorithm is Day 5; use Euclidean algorithm as a computational tool today.

Worked examples

Example 1 — Prime check

Is \(91\) prime? \(\sqrt{91}\approx 9.5\). Check divisors \(\le 9\): \(7\mid 91\) since \(91=7\cdot 13\). Composite.

Example 2 — Factorization

\(360=36\cdot 10=2^2 3^2\cdot 2\cdot 5=2^3\cdot 3^2\cdot 5\).

Example 3 — Sieve fragment

Primes \(\le 30\): strike multiples of \(2,3,5\) (since \(\sqrt{30}<6\)). Remaining: \(2,3,5,7,11,13,17,19,23,29\).

Example 4 — FTA uniqueness illustration

\(12=2\cdot 2\cdot 3=2\cdot 3\cdot 2=3\cdot 2\cdot 2\); same multiset of primes. Not \(12=4\cdot 3\) as a prime factorization (\(4\) not prime).

Example 5 — Euclid construction

From primes \(2,3,5\): \(N=31\), which is prime. From \(2,3,5,7,11,13\): \(N=30031\) composite but introduces new primes \(59,509\).

Example 6 — gcd via primes

\(a=84=2^2\cdot 3\cdot 7\), \(b=90=2\cdot 3^2\cdot 5\).
\(\gcd=2^{\min(2,1)}3^{\min(1,2)}5^{0}7^{0}=2\cdot 3=6\).
\(\operatorname{lcm}=2^2\cdot 3^2\cdot 5\cdot 7=1260\).
Check \(6\cdot 1260=7560=84\cdot 90\).

Example 7 — lcm via formula

\(\gcd(48,180)\): \(48=2^4\cdot 3\), \(180=2^2\cdot 3^2\cdot 5\), \(\gcd=2^2\cdot 3=12\).
\(\operatorname{lcm}=\frac{48\cdot 180}{12}=720\).

Example 8 — Euclidean algorithm

\(\gcd(252,90)\): \(252=2\cdot 90+72\), \(90=1\cdot 72+18\), \(72=4\cdot 18+0\) → \(\gcd=18\).

Example 9 — Coprime

\(\gcd(35,12)=1\) → coprime → \(\operatorname{lcm}(35,12)=420\).

Example 10 — Fractions connection

\(\frac{84}{90}=\frac{84\div 6}{90\div 6}=\frac{14}{15}\) using \(\gcd=6\).

Example 11 — Divisibility chain

\(3\mid 12\) and \(12\mid 60\) \(\Rightarrow\) \(3\mid 60\). Indeed \(60=3\cdot 20\).

Example 12 — Counting factors

If \(n=p_1^{e_1}\cdots p_r^{e_r}\), number of positive divisors is \((e_1+1)\cdots(e_r+1)\).
\(360=2^3 3^2 5\) has \((3+1)(2+1)(1+1)=24\) positive divisors.

Example 13 — Common multiple application

Buses every \(12\) and \(18\) minutes; simultaneous departure every \(\operatorname{lcm}(12,18)=36\) minutes.

Example 14 — Prove using FTA style

Show \(\sqrt{12}\) is irrational? Better: standard \(\sqrt{2}\) — if \(\sqrt{2}=p/q\) reduced, \(p^2=2q^2\), then \(2\mid p^2\Rightarrow 2\mid p\), so \(p=2k\), \(4k^2=2q^2\Rightarrow 2\mid q^2\Rightarrow 2\mid q\), contradicting \(\gcd(p,q)=1\). (Uses Euclid lemma / prime divides square.)

Exercises

Easy

1. List all positive divisors of \(48\).
2. Classify \(1,2,15,17,21,27\) as prime / composite / neither.
3. Factor \(196\) completely into primes.
4. Compute \(\gcd(54,24)\) and \(\operatorname{lcm}(54,24)\); verify product identity.
5. Is \(2\mid 0\)? Is \(0\mid 2\)? Explain.

Medium

6. Use Euclidean algorithm for \(\gcd(1071,462)\).
7. Factor \(1001\) and \(2310\); find gcd and lcm via primes.
8. How many positive divisors does \(720\) have?
9. Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid (bx+cy)\) for all integers \(x,y\).
10. Show that there is no largest prime using Euclid’s construction (rewrite the proof in your words).
11. Are \(35\) and \(64\) coprime? Compute \(\operatorname{lcm}(35,64)\).
12. Reduce \(\frac{360}{504}\) using gcd.
13. Find all primes \(p\) such that \(p+2\) is also prime for \(p\le 20\) (twin prime samples).

Hard / proof

14. Prove existence half of FTA by induction on \(n\).
15. Prove: if \(p\) is prime and \(p\mid ab\), then \(p\mid a\) or \(p\mid b\) assuming Bézout: \(\gcd(p,a)=1\Rightarrow 1=px+ay\) (write the details).
16. Prove \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\) from min/max exponent identity.
17. Prove: if \(\gcd(a,b)=1\) and \(\gcd(a,c)=1\), then \(\gcd(a,bc)=1\).
18. Show that if \(n\) is composite, then \(n\) has a prime factor \(\le\sqrt{n}\).
19. Prove that \(n\) and \(n+1\) are always coprime.
20. Why is \(1\) not prime? Give two reasons used in number theory conventions (FTA uniqueness; unit definition).

Challenge / CS-flavored

21. Hash table size often chosen prime. Give an informal reason related to \(\mathrm{mod}\,m\) distributing sequential keys (no formal proof required).
22. Two loops with periods \(12\) and \(20\) instructions; when do they realign? (\(\operatorname{lcm}\))
23. Bitlength: if \(n\) has prime factorization, \(\log_2 n=\sum e_i\log_2 p_i\). Estimate \(\log_2(360)\).
24. Show \(4\mid n^2\) or \(4\nmid n\)? Actually prove: if \(n\) odd then \(n^2\equiv 1\pmod 4\); if even \(n^2\equiv 0\pmod 4\).
25. Construct \(N=p_1\cdots p_k+1\) for the first four primes; factor \(N\) if composite.

Euclid’s lemma and consequences (bridge)

Euclid’s lemma (standard form). If prime \(p\) divides \(ab\), then \(p\mid a\) or \(p\mid b\).

Corollary. If \(p\) is prime and \(p\mid a_1 a_2\cdots a_k\), then \(p\) divides some \(a_i\).

Application to uniqueness of FTA. Matching primes on both sides of two factorizations uses this repeatedly after canceling.

Bézout preview. \(\gcd(a,b)=1\) iff there exist integers \(x,y\) with \(ax+by=1\). Used to prove Euclid’s lemma: if \(p\nmid a\) then \(\gcd(p,a)=1\), so \(1=px+ay\), multiply by \(b\).

GCD properties (catalog)

1. \(\gcd(a,b)=\gcd(b,a)=\gcd(|a|,|b|)\)
   
2. \(\gcd(a,0)=|a|\)
   
3. \(\gcd(a,b)=\gcd(a,b-a)\) and more generally \(\gcd(a,b)=\gcd(a,b+ka)\) for any integer \(k\)
   
4. If \(d=\gcd(a,b)\), then \(\gcd(a/d,b/d)=1\)
   
5. \(\gcd(ca,cb)=|c|\gcd(a,b)\)

LCM properties

1. \(\operatorname{lcm}(a,b)=\operatorname{lcm}(b,a)\)
   
2. If \(a\mid m\) and \(b\mid m\) then \(\operatorname{lcm}(a,b)\mid m\)
   
3. \(\operatorname{lcm}(a,b,c)=\operatorname{lcm}(\operatorname{lcm}(a,b),c)\)

Worked sieve narrative

List \(2..30\). Strike multiples of \(2\) from \(4\); of \(3\) from \(9\); of \(5\) from \(25\). Unstruck \(>1\) are primes. Complexity culture: simple sieve is fine for small \(N\); not analyzed formally today.

Extra exercises

26. Prove \(\gcd(a,b)=\gcd(a,b-a)\) from definition of common divisors.
    
27. Factor \(10!\) into primes using the primes \(\le 10\).
    
28. Show that if \(p\) and \(p+2\) are both prime (twins), then \(p=3\) or \(p\bmod 6\in\{5\}\) for \(p>3\) (mod \(6\) filter).
    
29. Compute \(\gcd(2^n-1,2^m-1)\) pattern for small \(n,m\) (optional discovery: \(\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1\)).
    
30. How many trailing zeros in \(100!\) in decimal? (Count factors of \(5\) in \(100!\).)

CS connection

Primality and factoring sit under cryptography (hard factoring for large semiprimes—context only). GCD appears in reducing fractions, in the Euclidean algorithm for modular inverses, and in calendar/scheduler cycle problems (lcm of periods). Unique factorization explains why canceling prime factors is safe. Sieve patterns appear in “mark multiples” array exercises and in generating small primes for tests.

Common pitfalls

Pitfall	What to do instead
Calling \(1\) prime	\(1\) is a unit; neither prime nor composite
Stopping Euclid at “\(N\) is prime”	\(N\) has a new prime factor, may be composite
\(\gcd(a,b)\) for negatives	Use positive gcd; \(\gcd(-a,b)=\gcd(a,b)\)
Adding exponents for gcd	gcd uses min exponents; lcm uses max
Forgetting \(|ab|\) in identity	Signs: identity uses absolute value
Trial division past \(\sqrt{n}\)	Only need \(d\le\sqrt{n}\)
Unique factorization ignoring order	Unique as multiset / sorted exponents

End-of-day synthesis problems

S1. Factor \(1260\) completely; find \(\gcd(1260,924)\) and \(\operatorname{lcm}(1260,924)\) two ways (primes + identity).

S2. Write Euclid’s proof that there are infinitely many primes, then apply the construction to \(\{2,3,5,7\}\) and factor the resulting \(N\) if composite.

S3. Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid (b+c)\) and \(a\mid (b-c)\).

S4. How many positive divisors does \(2^{4}\cdot 3^{2}\cdot 5\) have? List the prime-exponent pattern reason.

S5. Reduce \(\frac{252}{336}\) using \(\gcd\).

S6. Show \(n^{2}\) even \(\Rightarrow\) \(n\) even using FTA or Euclid lemma style (prime \(2\)).

S7. Prove \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\) from min/max exponents for a worked pair \(a=48\), \(b=180\), then general.

S8. Are \(91\) and \(85\) coprime? Justify by factoring or Euclid.

Checkpoint

• Define prime, composite, divides
  
• Factor integers and apply FTA
  
• Sketch Euclid’s infinite primes proof
  
• Compute gcd/lcm by primes and by Euclidean algorithm
  
• Use \(\gcd\cdot\operatorname{lcm}=|ab|\)
  
• Define coprime and use it to simplify
  
• Count divisors from exponents
  
• Finish S1–S3 closed book

Write two takeaways in your own words.

Deep dive — FTA, Euclid, gcd/lcm fluency

D1 — Full Euclidean algorithm narrative.
\(\gcd(1071,462)\):
\(1071=2\cdot 462+147\),
\(462=3\cdot 147+21\),
\(147=7\cdot 21+0\).
So \(\gcd=21\). Then \(\operatorname{lcm}(1071,462)=\frac{1071\cdot 462}{21}\). Compute \(1071/21=51\), so \(\operatorname{lcm}=51\cdot 462=23562\).

D2 — FTA uniqueness used to cancel safely.
If \(2^3\cdot 3\cdot 5\) divides \(2^5\cdot 3^2\cdot 7\cdot m\) and we cancel common primes, remaining cofactor analysis is legitimate precisely because prime factorizations are unique (multiset of primes).

D3 — Euclid construction that is composite.
Primes \(2,3,5,7\): \(N=2\cdot 3\cdot 5\cdot 7+1=211\), which happens to be prime.
Primes \(2,3,5,7,11,13\): \(N=30031=59\cdot 509\) — new primes appear as factors, not necessarily as \(N\) itself.

D4 — Counting divisors and listing pattern.
\(720=2^4\cdot 3^2\cdot 5\). Number of positive divisors \((4+1)(2+1)(1+1)=30\).
Any divisor looks like \(2^{a}3^{b}5^{c}\) with \(0\le a\le 4\), \(0\le b\le 2\), \(0\le c\le 1\).

D5 — Coprimality and products.
If \(\gcd(a,b)=1\) and \(\gcd(a,c)=1\), then \(\gcd(a,bc)=1\): no prime dividing \(a\) can divide \(b\) or \(c\), hence none divide \(bc\).

D6 — Trailing zeros of \(100!\) (decimal).
Number of times \(10=2\cdot 5\) divides \(100!\) is limited by fives: \(\lfloor 100/5\rfloor+\lfloor 100/25\rfloor+\lfloor 100/125\rfloor=20+4+0=24\) trailing zeros.

Extra practice set

31. Factor \(2310\) completely; compute \(\gcd(2310,1001)\) via primes.
    
32. Prove \(n\) and \(n+1\) are coprime from \(\gcd(n,n+1)=\gcd(n,1)\).
    
33. How many positive divisors does \(2^5\cdot 3\cdot 11^2\) have?
    
34. Write Euclid’s infinite-primes proof; apply to the first five primes and discuss whether \(N\) is prime.
    
35. Prove \(\gcd(ca,cb)=|c|\gcd(a,b)\) using prime exponents (or Euclidean idea).

Synthesis checklist (primes day)

Syn-A. Factor one integer completely; count its positive divisors from exponents.
Syn-B. Compute \(\gcd\) and \(\operatorname{lcm}\) two ways (primes + product identity).
Syn-C. Write Euclid’s infinite-primes argument in your own words (new factor, not “\(N\) prime”).
Syn-D. Run Euclidean algorithm on a pair near three digits.
Syn-E. State when \(a,b\) are coprime and what that does to \(\operatorname{lcm}(a,b)\).

Tomorrow

Day 5 — Division algorithm, mod, floor & ceiling. Existence/uniqueness of \(q,r\); language of % vs math mod for negatives; residue classes; floor/ceiling identities.

---

Day 5 — Division algorithm, mod, floor & ceiling

Stage I · concept day
Goal: State and use the division algorithm with unique \(q,r\); define floor and ceiling with identities; document % vs mathematical mod for negatives; introduce residue classes and congruence.

Why this matters

Integer division with remainder is how clocks, hash tables, circular buffers, pagination, and calendar arithmetic work. Floor and ceiling appear in complexity, block counts, and “how many pages for \(n\) items.” Negative operands are the #1 source of language-dependent bugs.

Theory

Division algorithm

Theorem (division algorithm). Let \(a\in\mathbb{Z}\) (dividend) and \(d\in\mathbb{Z}\) with \(d\neq 0\) (divisor). There exist unique integers \(q\) (quotient) and \(r\) (remainder) such that

\[a = dq + r\qquad\text{and}\qquad 0\le r < |d|.\]

(Common statement takes \(d>0\) and \(0\le r<d\).)

Existence idea (\(d>0\)). Consider the set of all integers of the form \(a-dq\) for \(q\in\mathbb{Z}\). Choose \(q\) so that \(r=a-dq\) is nonnegative and minimal among nonnegative candidates (or: take \(q=\lfloor a/d\rfloor\)). Then \(0\le r<d\): if \(r\ge d\), then \(a-d(q+1)=r-d\ge 0\) is a smaller nonnegative remainder, contradiction.

Uniqueness. Suppose \(a=dq_1+r_1=dq_2+r_2\) with \(0\le r_i<d\) (assume \(d>0\)). Then \(d(q_1-q_2)=r_2-r_1\), so \(d\) divides \(r_2-r_1\). But \(|r_2-r_1|<d\), so \(r_2-r_1=0\), hence \(r_1=r_2\) and \(q_1=q_2\). \(\square\)

Notation: mod and congruence

We write \[a\bmod d = r\] for the remainder in the division algorithm (with the convention \(0\le r<|d|\) when we fix mathematical remainder).

Congruence: \(a\equiv b\pmod{d}\) means \(d\mid (a-b)\), equivalently \(a\) and \(b\) leave the same remainder on division by \(d\) (for \(d>0\)).

Floor and ceiling

For real \(x\):

• \(\lfloor x\rfloor\) = greatest integer \(\le x\) (floor)
  
• \(\lceil x\rceil\) = least integer \(\ge x\) (ceiling)

Examples: \(\lfloor 3.2\rfloor=3\), \(\lceil 3.2\rceil=4\), \(\lfloor -3.2\rfloor=-4\), \(\lceil -3.2\rceil=-3\).

Identities (selected):

1. \(\lfloor x\rfloor \le x < \lfloor x\rfloor+1\)
   
2. \(\lceil x\rceil-1 < x \le \lceil x\rceil\)
   
3. \(\lfloor x\rfloor = n \Leftrightarrow n\le x<n+1\) for \(n\in\mathbb{Z}\)
   
4. For \(n\in\mathbb{Z}\), \(\lfloor n\rfloor=n=\lceil n\rceil\)
   
5. \(\lceil x\rceil = -\lfloor -x\rfloor\)
   
6. For integer \(n\) and real \(x\): \(\lfloor n+x\rfloor=n+\lfloor x\rfloor\)
   
7. For positive integer \(m\) and integer \(a\):
   \(\bigl\lfloor\frac{a}{m}\bigr\rfloor\) is the quotient when \(a\ge 0\) in \(a=mq+r\) with \(0\le r<m\)

Block counts: number of groups of size \(m\) needed for \(n\) items is \(\lceil n/m\rceil\) (for \(m>0\)).

Language % vs mathematical mod (negatives)

Critical: programming languages disagree on the sign of a % d when \(a\) or \(d\) is negative.

Convention	Rule of thumb	Example \(-7\) div \(3\)
Mathematical / Euclidean	Remainder \(r\) with \(0\le r<|d|\)	\(-7=3\cdot(-3)+2\), \(r=2\)
Truncated toward zero (C/C++/Java for /)	Quotient truncates toward \(0\); remainder has sign of dividend	\(-7/3\to -2\), remainder \(-7-3(-2)=-1\)
Floored division (Python //)	Quotient \(=\lfloor a/d\rfloor\); remainder \(a-d q\)	\(-7//3=-3\), -7%3=2

Document both. In this book, mathematical \(\mathrm{mod}\) means the division-algorithm remainder \(0\le r<|d|\) (or \(0\le r<d\) if \(d>0\)). When discussing code, name the language convention.

Python: (-7) % 3 == 2 (floored).
C99 / Java: (-7) % 3 == -1 with toward-zero /.

Residue classes

For modulus \(m>0\), the residue class of \(a\) is \[[a]_m = \{ a+km : k\in\mathbb{Z}\}=\{\ldots,a-2m,a-m,a,a+m,a+2m,\ldots\}.\]

There are exactly \(m\) distinct classes: \([0],[1],\ldots,[m-1]\).
\(\mathbb{Z}/m\mathbb{Z}\) is the set of these classes (modular arithmetic system).
\(a\equiv b\pmod m\) iff \([a]_m=[b]_m\).

Arithmetic on residues (preview): \([a]+[b]=[a+b]\), \([a][b]=[ab]\) is well-defined.

Relating gcd and linear combinations (preview)

Remainders in the Euclidean algorithm are integer linear combinations of \(a\) and \(b\); eventually \(\gcd(a,b)=ax+by\) (Bézout). Full use later in modular inverses.

Worked examples

Example 1 — Positive division

\(a=100\), \(d=7\): \(100=7\cdot 14+2\), so \(q=14\), \(r=2\). \(100\bmod 7=2\). \(100\equiv 2\pmod 7\).

Example 2 — Negative dividend (math)

\(a=-100\), \(d=7\): find \(q\) so \(0\le r<7\). \(-100=7q+r\Rightarrow\) try \(q=-15\): \(7(-15)=-105\), \(r=5\). Check \(-100=-105+5\). So \(-100\bmod 7=5\), and \(-100\equiv 5\pmod 7\).

Example 3 — Truncated vs floored

\(-100/7\) toward zero: quotient \(-14\), remainder \(-100-7(-14)=-100+98=-2\).
Floored: quotient \(\lfloor -100/7\rfloor=\lfloor -14.285\ldots\rfloor=-15\), remainder \(5\) as above.

Example 4 — Floor/ceiling negatives

\(\lfloor -7/3\rfloor=\lfloor -2.333\rfloor=-3\).
\(\lceil -7/3\rceil=\lceil -2.333\rceil=-2\).
\(\lceil 7/3\rceil=3\), \(\lfloor 7/3\rfloor=2\).

Example 5 — Identity \(\lceil x\rceil=-\lfloor -x\rfloor\)

\(x=2.3\): \(\lceil 2.3\rceil=3\), \(-\lfloor -2.3\rfloor=-( -3)=3\).
\(x=-2.3\): \(\lceil -2.3\rceil=-2\), \(-\lfloor 2.3\rfloor=-2\).

Example 6 — Pages / blocks

\(n=50\) items, page size \(m=8\): \(\lceil 50/8\rceil=\lceil 6.25\rceil=7\) pages. Last page has \(50-6\cdot 8=2\) items.

Example 7 — Congruence arithmetic

\(17\equiv 5\pmod{12}\), \(20\equiv 8\pmod{12}\), sum \(37\equiv 1\pmod{12}\), and \(5+8=13\equiv 1\pmod{12}\).

Example 8 — Residue class

\([3]_5=\{\ldots,-7,-2,3,8,13,\ldots\}\). Same as \([-2]_5\).

Example 9 — Clock

Hours: \(15\bmod 12=3\) o’clock form. \(15\equiv 3\pmod{12}\).

Example 10 — Even/odd via mod

\(n\) even \(\Leftrightarrow n\equiv 0\pmod 2\); odd \(\Leftrightarrow n\equiv 1\pmod 2\).

Example 11 — Floor of sum

\(\lfloor 3+2.7\rfloor=5=\lfloor 3\rfloor+\lfloor 2.7\rfloor\).
But \(\lfloor 2.7+2.7\rfloor=\lfloor 5.4\rfloor=5\neq 2+2=4\): floor does not always distribute over addition of non-integers.

Example 12 — Quotient formula

For \(a=20\), \(m=6\): \(\lfloor 20/6\rfloor=3\), remainder \(2\), \(20=6\cdot 3+2\).

Example 13 — Negative divisor (careful)

\(a=20\), \(d=-6\). Require \(0\le r<6\) (\(|d|=6\)). \(20=(-6)q+r\). Try \(q=-3\): \((-6)(-3)=18\), \(r=2\). So \(20=(-6)(-3)+2\).

Example 14 — Python vs C mental model

Predict (-7)%3: Python \(2\); C toward-zero remainder \(-1\). Always check language docs for signed %.

Exercises

Easy

1. Divide \(85\) by \(9\): find \(q,r\) with \(0\le r<9\).
2. Compute \(85\bmod 9\) and \(9\bmod 85\).
3. Evaluate \(\lfloor 9.99\rfloor\), \(\lceil 9.01\rceil\), \(\lfloor -9.01\rfloor\), \(\lceil -9.99\rceil\).
4. How many boxes of capacity \(12\) are needed for \(100\) items?
5. Write \([7]_{5}\) as equal to \([r]_5\) with \(0\le r<5\).

Medium

6. Find math-mod remainders: \((-85)\bmod 9\) and \((-85)\bmod 10\).
7. Prove uniqueness in the division algorithm for \(d>0\).
8. Show \(a\equiv b\pmod m\) iff \(a\) and \(b\) have the same remainder on division by \(m\) (\(m>0\)).
9. Verify \(\lceil x\rceil=-\lfloor -x\rfloor\) for \(x=4\), \(x=-4\), \(x=4.2\), \(x=-4.2\).
10. Compute \(\lfloor n/2\rfloor\) for \(n=0,1,2,3,10,11\) (integer half).
11. If today is day index \(2\) (Wednesday) and \(m=7\), what day index is \(100\) days later?
12. Express \(a=dq+r\) for \(a=-17\), \(d=5\) (math remainder).
13. Give a counterexample: \(\lfloor x+y\rfloor\neq\lfloor x\rfloor+\lfloor y\rfloor\).

Hard / proof

14. Prove existence of \(q,r\) for \(a\in\mathbb{Z}\), \(d>0\) using \(q=\lfloor a/d\rfloor\).
15. Prove: for integer \(n\) and real \(x\), \(\lfloor n+x\rfloor=n+\lfloor x\rfloor\).
16. Prove: number of multiples of \(m>0\) in \(\{1,2,\ldots,N\}\) is \(\lfloor N/m\rfloor\).
17. Show there are exactly \(m\) distinct residue classes mod \(m\).
18. Relate Euclidean algorithm step \(a=bq+r\) to \(\gcd(a,b)=\gcd(b,r)\).
19. For \(m>0\), prove \(a\equiv b\pmod m\) and \(c\equiv d\pmod m\) imply \(a+c\equiv b+d\) and \(ac\equiv bd\pmod m\).
20. Explain with one table: truncated vs floored division for all sign combinations of \(\pm 7\) and \(\pm 3\) (quotient and remainder).

Challenge / CS-flavored

21. Circular buffer length \(m=8\), head index \(h=6\), advance \(k=5\) steps: new index \((h+k)\bmod m\).
22. Pagination: items \(0..n-1\), page size \(p\). Which page is index \(i\)? How many items on the last page?
23. Hash: \(h(k)=k\bmod m\) with \(m=10\). Collisions among keys \(17,27,37\)?
24. Why might if (n % 2 == 1) miss negative odds in C? What test is safer for “odd”?
25. Prove \(\lfloor x\rfloor \le\lceil x\rceil\) always, and equality iff \(x\in\mathbb{Z}\).

Congruence arithmetic laws (full)

For fixed \(m>0\):

1. \(a\equiv a\pmod m\)
   
2. \(a\equiv b\Rightarrow b\equiv a\)
   
3. \(a\equiv b\) and \(b\equiv c\Rightarrow a\equiv c\)
   
4. \(a\equiv b\) and \(c\equiv d\Rightarrow a+c\equiv b+d\) and \(ac\equiv bd\pmod m\)
   
5. \(a\equiv b\Rightarrow ka\equiv kb\pmod m\) for any integer \(k\)
   
6. Cancellation caution: \(ka\equiv kb\pmod m\) and \(\gcd(k,m)=1\) \(\Rightarrow\) \(a\equiv b\pmod m\). If \(\gcd(k,m)>1\), cancellation may fail (e.g. \(2\cdot 1\equiv 2\cdot 4\pmod 6\) but \(1\not\equiv 4\pmod 6\)).

Floor identities (catalog)

For real \(x,y\) and integer \(n\):

• \(\lfloor x\rfloor+\lfloor y\rfloor \le \lfloor x+y\rfloor \le \lfloor x\rfloor+\lfloor y\rfloor+1\)
  
• \(\bigl\lfloor\frac{\lfloor x\rfloor}{n}\bigr\rfloor=\bigl\lfloor\frac{x}{n}\bigr\rfloor\) for integer \(n>0\)
  
• \(\lceil n/m\rceil=\bigl\lfloor\frac{n+m-1}{m}\bigr\rfloor\) for integers \(n\ge 0\), \(m>0\) (useful packing identity)

Division algorithm for negative divisors

Require \(0\le r<|d|\) always. Then \(q\) is uniquely determined. Example: \(a=17\), \(d=-5\): \(17=(-5)(-3)+2\) because \(15+2=17\) and \(0\le 2<5\).

Modular “wrap” pictures

Clock: hours mod \(12\). Array ring buffer: indices mod capacity. Hash table: key % m with nonnegative keys first—signed keys need normalization to \([0,m)\).

Extra exercises

26. Prove \(\lceil n/m\rceil=\bigl\lfloor(n+m-1)/m\bigr\rfloor\) for integers \(n\ge 0\), \(m>0\).
    
27. Show \(a\equiv b\pmod m\Rightarrow a^k\equiv b^k\pmod m\) by induction on \(k\).
    
28. Find all \(x\) with \(0\le x<15\) and \(x\equiv 7\pmod 5\).
    
29. Compute \(\lfloor\sqrt{50}\rfloor\) and \(\lceil\sqrt{50}\rceil\) without a decimal approx beyond bounds \(7^2=49\), \(8^2=64\).
    
30. Language table: for \(a=-20\), \(d=6\), write math remainder, Python-style floored remainder, and toward-zero remainder.

CS connection

• Array strides and tiles: \(\lceil n/B\rceil\) blocks.
  
• Hashing: \(k\bmod m\) buckets.
  
• Time: Unix time mod \(86400\) for time-of-day (careful with time zones).
  
• Signed remainder bugs: security and correctness issues when assuming \(r\ge 0\).
  
• Complexity: loops with \(\lfloor n/2\rfloor\) iterations; master theorem floors later.

Common pitfalls

Pitfall	What to do instead
Assuming % always \(\ge 0\)	Check language; prefer math remainder for proofs
\(\lfloor -3.2\rfloor=-3\)	Floor goes down: \(-4\)
Confusing \(\mathrm{mod}\) with “modulo operation on reals”	Integer remainder / congruence
Forgetting uniqueness needs range of \(r\)	\(0\le r<|d|\) is essential
\(\lfloor x+y\rfloor=\lfloor x\rfloor+\lfloor y\rfloor\) always	False for non-integers
Residue class equals one number	Class is an infinite set; pick canonical \(0..m-1\)

Fully worked extra examples

E15 — Congruence chain.
\(17\equiv 2\pmod{5}\), \(23\equiv 3\pmod{5}\), so \(17\cdot 23\equiv 2\cdot 3=6\equiv 1\pmod{5}\). Check \(391/5\): \(5\cdot 78=390\), remainder \(1\).

E16 — Floor identity use.
Number of pages for \(n=250\), \(m=40\): \(\lceil 250/40\rceil=\lceil 6.25\rceil=7=\bigl\lfloor(250+39)/40\bigr\rfloor=\lfloor 289/40\rfloor=7\).

E17 — Negative divisor.
\(a=-30\), \(d=-7\), require \(0\le r<7\). Try \(q=5\): \((-7)(5)=-35\), \(r=5\), and \(-30=-35+5\). Yes.

E18 — Residue class equality.
\([7]_{5}=[2]_{5}=[-3]_{5}\) because differences multiples of \(5\).

End-of-day synthesis problems

S1. For \(a=-100\) and \(d=9\), find math \(q,r\) with \(0\le r<9\). Compare to toward-zero quotient/remainder.

S2. Prove uniqueness of \(q,r\) in the division algorithm for \(d>0\).

S3. Evaluate \(\lfloor -20/3\rfloor\), \(\lceil -20/3\rceil\), and show \(\lceil x\rceil=-\lfloor -x\rfloor\) for \(x=-20/3\).

S4. How many multiples of \(7\) lie in \(\{1,2,\ldots,100\}\)? Use floor.

S5. Prove \(a\equiv b\pmod m\Rightarrow a+c\equiv b+c\pmod m\).

S6. Circular buffer length \(16\), index \(14\), advance \(5\): new index.

S7. List canonical residues of \(-3,-2,\ldots,6\) mod \(5\).

S8. Identity: verify \(\lceil 100/12\rceil=\bigl\lfloor(100+12-1)/12\bigr\rfloor\).

Checkpoint

• State division algorithm with uniqueness
  
• Compute \(q,r\) for positive and negative dividends (math convention)
  
• Define floor/ceiling; evaluate on negatives
  
• Use \(\lceil n/m\rceil\) for packing counts
  
• Explain at least two signed-division conventions
  
• Define \(a\equiv b\pmod m\) and residue class \([a]_m\)
  
• Complete S1–S2 as exam-style writeups

Write two takeaways in your own words.

Deep dive — division algorithm, floor, congruence

D1 — Existence via floor (positive divisor).
For \(a\in\mathbb{Z}\), \(d>0\), set \(q=\lfloor a/d\rfloor\) and \(r=a-dq\). By definition of floor, \(q\le a/d<q+1\), so \(0\le a-dq<d\), i.e. \(0\le r<d\). Uniqueness was already proved by difference bound.

D2 — Full sign table (mental model).
For \(a=\pm 17\), \(d=\pm 5\), insist on mathematical remainder \(0\le r<|d|=5\).
\(17=5\cdot 3+2\); \(17=(-5)\cdot(-3)+2\);
\(-17=5\cdot(-4)+3\) because \(5(-4)=-20\), \(r=3\);
\(-17=(-5)\cdot 4+3\) because \((-5)(4)=-20\), \(r=3\).
Same \(r\) depends on \(|d|\) range, not the sign of \(d\) alone, under this convention.

D3 — Congruence product and failed cancellation.
\(14\equiv 8\pmod 6\) (both rem \(2\)). Also \(2\cdot 4\equiv 2\cdot 1\pmod 6\) but \(4\not\equiv 1\pmod 6\) because \(\gcd(2,6)=2\neq 1\).

D4 — Packing identity practice.
Items \(n=250\), page size \(m=12\): \(\lceil 250/12\rceil=\lceil 20.833\rceil=21\).
Check \(\bigl\lfloor(250+12-1)/12\bigr\rfloor=\lfloor 261/12\rfloor=\lfloor 21.75\rfloor=21\).
Last page size: \(250-20\cdot 12=10\).

D5 — Residue arithmetic clock.
Day index \(0\)=Sun,…, \(6\)=Sat. If today is \(4\) (Thu) and we add \(100\) days: \((4+100)\bmod 7=104\bmod 7=6\) (Sat), since \(104=14\cdot 7+6\).

D6 — Floor inequality sandwich.
Always \(\lfloor x\rfloor+\lfloor y\rfloor\le\lfloor x+y\rfloor\le\lfloor x\rfloor+\lfloor y\rfloor+1\).
Example: \(x=y=1.6\): left \(1+1=2\), middle \(\lfloor 3.2\rfloor=3\), right \(3\). Equality can hit either side depending on fractional parts.

Extra practice set

31. Find math \(q,r\) for \(a=-200\), \(d=13\).
    
32. Prove: number of multiples of \(m>0\) among \(1..N\) is \(\lfloor N/m\rfloor\).
    
33. Show \(a\equiv b\pmod m\) and \(c\equiv d\pmod m\) \(\Rightarrow\) \(ac\equiv bd\pmod m\).
    
34. Circular buffer capacity \(32\), index \(29\), step \(+7\): new index.
    
35. Verify \(\lceil x\rceil=-\lfloor -x\rfloor\) for \(x=\pm 7.1\) and \(x=\pm 7\).

Tomorrow

Day 6 — Positional bases. Place-value polynomials, convert among bases \(2\)–\(16\), hex↔︎binary via nibbles, digit validity, Horner’s method.