Day 71 — Divisibility, primes, FTA

Updated

July 30, 2026

Day 71 — Divisibility, primes, and the Fundamental Theorem of Arithmetic

Stage VII · concept day
Goal: Formalize \(a\mid b\); prove standard properties; define primes; state Euclid’s lemma; state FTA with existence + uniqueness sketches; connect gcd/lcm to exponents.

Why this matters

Divisibility is the backbone of modular arithmetic, hashing buckets, cyclic structures, and every crypto-literacy story that follows. If “\(a\) divides \(b\)” is fuzzy, every later congruence proof wobbles. Today we make the language precise and prove the lemmas you will reuse constantly on Days 72–80.

Note

No labs. Theory, short proofs, worked calculations, written exercises. Calculator only to check arithmetic after you finish by hand.

Theory

Divisibility

Definition (divides). Let \(a,b\in\mathbb{Z}\). We say \(a\) divides \(b\), written \(a\mid b\), if there exists an integer \(k\) such that \[ b = a\cdot k. \] When \(a\mid b\) we also say \(a\) is a divisor (or factor) of \(b\), and \(b\) is a multiple of \(a\). If no such \(k\) exists, write \(a\nmid b\).

Examples. \(3\mid 12\) because \(12=3\cdot 4\). \(5\nmid 12\). \(7\mid 0\) because \(0=7\cdot 0\). For any \(a\neq 0\), \(a\mid a\) (\(k=1\)) and \(a\mid 0\).

Convention. Usually we care about \(a\neq 0\). The statement \(0\mid b\) holds only when \(b=0\) (because \(b=0\cdot k\) forces \(b=0\)). We rarely use \(0\) as a divisor in applications.

Immediate consequences

Proposition 1 (basic properties). For all \(a,b,c\in\mathbb{Z}\):

  1. Reflexive (nonzero): if \(a\neq 0\) then \(a\mid a\).
  2. Transitive: if \(a\mid b\) and \(b\mid c\) then \(a\mid c\).
  3. Linear combination: if \(a\mid b\) and \(a\mid c\) then \(a\mid (bx+cy)\) for all \(x,y\in\mathbb{Z}\).
  4. Units: \(1\mid n\) and \((-1)\mid n\) for every \(n\); if \(a\mid b\) and \(b\mid a\) then \(a=\pm b\).
  5. Bound for positives: if \(a,b>0\) and \(a\mid b\) then \(a\le b\).
  6. Multiplicative: if \(a\mid b\) then \(a\mid bc\) for every \(c\); if \(a\mid b\) and \(c\mid d\) then \(ac\mid bd\).

Proof of (2). \(b=ak\), \(c=b\ell=ak\ell\), so \(a\mid c\).

Proof of (3). Write \(b=ak\), \(c=a\ell\). Then \(bx+cy = a(kx+\ell y)\), so \(a\mid(bx+cy)\).

Proof of (4) second part. \(b=ak\), \(a=b\ell\) implies \(b=b(k\ell)\), so \(b(k\ell-1)=0\). If \(b\neq 0\) then \(k\ell=1\), so \(k,\ell\in\{\pm 1\}\) and \(a=\pm b\). If \(b=0\) then \(a=0\) as well from \(a=b\ell\).

Proof of (5). \(b=ak\) with \(k\ge 1\) integer (since \(b>0,a>0\)), so \(b\ge a\).

Proof of (6). First claim: \(b=ak\) ⇒ \(bc=a(kc)\). Second: \(b=ak\), \(d=c\ell\) ⇒ \(bd=ac(k\ell)\).

The division algorithm (reminder)

Theorem (division algorithm). For any \(a\in\mathbb{Z}\) and \(d\in\mathbb{Z}\) with \(d>0\), there exist unique integers \(q\) (quotient) and \(r\) (remainder) such that \[ a = dq + r \quad\text{and}\quad 0\le r < d. \] We write \(a = dq+r\) and sometimes \(r = a\bmod d\) (mathematical nonnegative remainder).

Existence sketch. Consider the set \(S=\{a-dq:q\in\mathbb{Z},\, a-dq\ge 0\}\). It is nonempty (take \(q\) large negative if needed). Let \(r\) be its least element; then \(r<d\) else \(r-d\) would be a smaller nonnegative element of \(S\).

Uniqueness sketch. If \(a=dq+r=dq'+r'\) with \(0\le r,r'<d\), then \(d(q-q')=r'-r\), so \(d\) divides a difference strictly between \(-d\) and \(d\), forcing \(r=r'\) and \(q=q'\).

This is the formal home of “integer division.” Programming languages may return negative remainders for negative dividends; always state the mathematical convention when proving.

Primes and composites

Definition (prime). An integer \(p>1\) is prime if its only positive divisors are \(1\) and \(p\). Equivalently: if \(p=ab\) with \(a,b\in\mathbb{Z}_{>0}\), then one of \(a,b\) is \(1\) and the other is \(p\).

Definition (composite). An integer \(n>1\) that is not prime is composite: it factors as \(n=ab\) with integers \(a,b\) both \(>1\).

Definition (unit). \(\pm 1\) are units in \(\mathbb{Z}\); they are neither prime nor composite. \(0\) is neither.

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

Lemma (every \(n>1\) has a prime divisor). Let \(n>1\). Among all divisors of \(n\) that are \(>1\), let \(p\) be a minimal one. Then \(p\) is prime: if \(p=ab\) with \(1<a,b\), then \(a\) would be a smaller divisor \(>1\) of \(n\).

Euclid’s lemma

Lemma (Euclid’s lemma). If \(p\) is prime and \(p\mid ab\), then \(p\mid a\) or \(p\mid b\).

Proof (via Bézout — full proof after Day 72). If \(p\nmid a\) then \(\gcd(p,a)=1\) (the only positive divisors of \(p\) are \(1,p\)). By Bézout there exist \(x,y\) with \(px+ay=1\). Multiply by \(b\): \(pxb + ayb = b\). Now \(p\mid ab\) so \(p\mid ayb\), and \(p\mid pxb\), hence \(p\mid b\) by linear combinations.

Corollary (to products). If \(p\) is prime and \(p\mid a_1 a_2\cdots a_k\), then \(p\mid a_i\) for some \(i\). (Induction on \(k\).)

Warning. The conclusion fails if \(p\) is replaced by a composite: e.g. \(4\mid 6\cdot 6\) but \(4\nmid 6\).

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\), each \(p_i\) prime), and this factorization is unique up to order: if also \(n=q_1\cdots q_\ell\) with primes \(q_j\), then \(k=\ell\) and the lists \(\{p_i\}\) and \(\{q_j\}\) are rearrangements of each other.

Canonical form. We often group equals: \[ n = p_1^{e_1} p_2^{e_2}\cdots p_r^{e_r},\qquad p_1<p_2<\cdots<p_r,\quad e_i\ge 1. \] This representation is unique.

Existence (strong induction). Base: smallest \(n=2\) is prime. Assume every integer in \(\{2,\ldots,n-1\}\) factors into primes. If \(n\) is prime, done. If composite, \(n=ab\) with \(1<a,b<n\); by IH each of \(a,b\) is a prime product, hence so is \(n\).

Uniqueness sketch. Suppose \[ p_1\cdots p_k = q_1\cdots q_\ell \] with primes. By Euclid’s lemma, \(p_1\) divides some \(q_j\), hence \(p_1=q_j\) (both prime). Cancel \(p_1\) and induct on the number of factors (or on \(n\)).

Consequences used constantly

Fact How FTA gives it
\(\gcd\) via min exponents If \(a=\prod p_i^{\alpha_i}\), \(b=\prod p_i^{\beta_i}\), then \(\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}\)
\(\mathrm{lcm}\) via max \(\mathrm{lcm}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}\)
Identity \(\gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab\) for \(a,b>0\)
Squares \(n\) is a perfect square iff all \(e_i\) even
Squarefree \(n\) squarefree iff all \(e_i=1\)

gcd properties (preview of Day 72)

Definition. For integers \(a,b\) not both zero, \(\gcd(a,b)\) is the largest positive integer \(d\) with \(d\mid a\) and \(d\mid b\). Convention: \(\gcd(a,b)=\gcd(|a|,|b|)\).

Proposition 2 (gcd facts).

  1. \(\gcd(a,0)=|a|\) for \(a\neq 0\).
  2. If \(d=\gcd(a,b)\) then \(\gcd(a/d,b/d)=1\).
  3. Common divisors of \(a,b\) are exactly the divisors of \(\gcd(a,b)\) (once Bézout is known: every common divisor divides every integer combination, hence divides the gcd).
  4. \(\gcd(a,b)=\gcd(b,a-qb)\) for any integer \(q\) (sets of common divisors match).

Item (4) is the engine of the Euclidean algorithm tomorrow.

Coprimality

Definition. Integers \(a,b\) are coprime (or relatively prime) if \(\gcd(a,b)=1\).

Lemma (Gauss). If \(a\mid bc\) and \(\gcd(a,b)=1\), then \(a\mid c\). (Proof after Day 72 via Bézout, or via FTA: every prime of \(a\) cannot divide \(b\), so all divide \(c\).)

Infinitely many primes (Euclid)

Theorem. There are infinitely many primes.

Proof. Suppose only finitely many primes \(p_1,\ldots,p_m\). Let \(N=p_1\cdots p_m + 1\). Then \(N>1\), so \(N\) has a prime factor \(q\). But \(q\) cannot equal any \(p_i\) (else \(p_i\mid N\) and \(p_i\mid p_1\cdots p_m\) imply \(p_i\mid 1\)). Contradiction. ∎

This proves existence of more primes, not an efficient way to find large primes.

Counting positive divisors

If \(n=\prod p_i^{e_i}\), every positive divisor has the form \(\prod p_i^{a_i}\) with \(0\le a_i\le e_i\). Number of positive divisors: \[ \tau(n)=(e_1+1)(e_2+1)\cdots(e_r+1). \] The sum of positive divisors is \(\sigma(n)=\prod_i (1+p_i+\cdots+p_i^{e_i})=\prod_i\frac{p_i^{e_i+1}-1}{p_i-1}\).

Worked examples

Example 1 — Linear combinations.
Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(b+c)\) and \(a\mid(b-c)\).
Write \(b=ak\), \(c=a\ell\). Then \(b+c=a(k+\ell)\) and \(b-c=a(k-\ell)\).

Example 2 — Extract a summand.
Prove: if \(3\mid n\) and \(3\mid(n+m)\) then \(3\mid m\).
\(3\mid n\) and \(3\mid(n+m)\) imply \(3\mid\bigl((n+m)-n\bigr)\), so \(3\mid m\).

Example 3 — Factorization.
\(360=36\cdot 10=(2^2 3^2)\cdot(2\cdot 5)=2^3\cdot 3^2\cdot 5\). Any other prime factorization is a reordering of three \(2\)s, two \(3\)s, and one \(5\).

Example 4 — gcd/lcm via FTA.
\(a=84=2^2\cdot 3\cdot 7\), \(b=90=2\cdot 3^2\cdot 5\). Then \[ \gcd(84,90)=2\cdot 3=6,\qquad \mathrm{lcm}(84,90)=2^2\cdot 3^2\cdot 5\cdot 7=1260, \] and \(6\cdot 1260=7560=84\cdot 90\).

Example 5 — Euclid’s lemma needs primality.
If \(p\) is prime and \(p\mid n^2\) then \(p\mid n\cdot n\) ⇒ \(p\mid n\). Contrast: \(4\mid 6^2\) but \(4\nmid 6\).

Example 6 — Squares and exponents.
If \(n=m^2\) and \(m=\prod p_i^{f_i}\), then \(n=\prod p_i^{2f_i}\) — all exponents even. Conversely if all \(e_i=2f_i\), set \(m=\prod p_i^{f_i}\).

Example 7 — Divisor count.
For \(360=2^3 3^2 5\): \(\tau(360)=(3+1)(2+1)(1+1)=24\).

Example 8 — Prove \(2\mid n\) and \(3\mid n\) ⇒ \(6\mid n\).
\(n=2k\) and \(3\mid 2k\). Since \(\gcd(3,2)=1\), Gauss’s lemma ⇒ \(3\mid k\), so \(k=3\ell\), \(n=6\ell\). (Alternatively use FTA: \(2\) and \(3\) both appear in \(n\).)

Example 9 — Irrationality of \(\sqrt{2}\) (FTA style).
Suppose \(\sqrt{2}=a/b\) in lowest terms, \(a,b>0\). Then \(a^2=2b^2\). The exponent of \(2\) in \(a^2\) is even; in \(2b^2\) it is odd — contradiction to uniqueness of exponents.

Example 10 — Division algorithm.
\(a=-17\), \(d=5\): \(-17=5\cdot(-4)+3\) because \(-20+3=-17\) and \(0\le 3<5\). Not “remainder \(-2\).”

Exercises

Solve by hand. Show definitions and reasons.

A. Definitions and quick facts

  1. Write the definition of \(a\mid b\) without looking. Give three examples and two non-examples.
  2. True or false? Justify: (a) \(0\mid 0\); (b) \(0\mid 5\); (c) \(5\mid 0\); (d) \((-3)\mid 12\); (e) \(4\mid 2\).
  3. Prove: if \(a\mid b\) then \(a\mid bc\) for every integer \(c\).
  4. Prove: if \(a\mid b\) and \(c\mid d\) then \(ac\mid bd\).
  5. Find all integers \(d\) with \(d\mid 12\). Separate positive and negative.
  6. Apply the division algorithm to \(a=100\), \(d=7\) and to \(a=-100\), \(d=7\).

B. Proofs with linear combinations

  1. Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(3b-5c)\).
  2. Prove: if \(6\mid n\) then \(2\mid n\) and \(3\mid n\). Is the converse true? Prove or counterexample.
  3. Prove: if \(2\mid n\) and \(3\mid n\) then \(6\mid n\).
  4. Prove: if \(a\mid b\) and \(b\mid c\) and \(c\mid a\) then \(|a|=|b|=|c|\).
  5. Show that the set of common divisors of \(a\) and \(b\) equals the set of divisors of \(\gcd(a,b)\) assuming the FTA formula for gcd.

C. Primes and FTA

  1. Prove that every integer \(n>1\) has a prime divisor.
  2. List the complete prime factorization of \(504\) and of \(1001\).
  3. Using FTA, compute \(\gcd(504,1001)\) and \(\mathrm{lcm}(504,1001)\); verify the product identity.
  4. Prove: if \(p\) is prime and \(p\nmid a\), then \(\gcd(p,a)=1\).
  5. Give a counterexample showing Euclid’s lemma fails if \(p\) is replaced by a composite \(m>1\).
  6. Prove using FTA: if \(a^2\mid b^2\) then \(a\mid b\) (for \(a,b>0\)).
  7. Prove the corollary: if \(p\) prime and \(p\mid a_1\cdots a_k\) then \(p\mid a_i\) for some \(i\).
  8. Factor \(2^{10}-1=1023\) and \(2^{10}+1=1025\) completely (or as far as small primes allow by hand).

D. Divisor counting and structure

  1. How many positive divisors does \(2^4\cdot 3^2\cdot 5\) have? Justify without listing if you prefer, then list to check.
  2. For which \(n\) is \(\tau(n)\) odd? Prove your characterization. (Hint: perfect squares.)
  3. Prove there are infinitely many composite numbers.
  4. Euclid’s construction: with primes \(2,3,5\) only (imagine), form \(N=2\cdot3\cdot5+1\). Factor \(N\) in the real integers — what new prime appears?
  5. Compute \(\sigma(12)\) and \(\sigma(28)\). (Note \(28\) is perfect: \(\sigma(28)-28=28\).)
  6. CS literacy (no code): explain in 3–5 sentences why unique factorization makes “cancel primes” valid when reasoning about buffer sizes that are powers of two, reducing fractions in exact rational arithmetic, or periods of modular counters.

E. Stretch

  1. Prove: among any \(n+1\) integers, two differ by a multiple of \(n\). (Pigeonhole on residues — modular preview.)
  2. Prove that \(\sqrt{3}\) is irrational using FTA (or Euclid’s classic argument).
  3. If \(n=\prod p_i^{e_i}\), count ordered pairs \((a,b)\) of positive integers with \(ab=n\). Then count unordered pairs \(\{a,b\}\).
  4. Prove: if \(a\mid b\) and \(a\mid c\) and \(\gcd(b/a,c/a)=1\), then \(\mathrm{lcm}(b,c)=bc/a\).
  5. Show that the product of any \(k\) consecutive integers is divisible by \(k!\).

Deep dive — gcd properties catalogue

Collect these for constant reuse (some proved today via FTA; others finished with Bézout on Day 72):

Property Statement
Symmetry \(\gcd(a,b)=\gcd(b,a)=\gcd(|a|,|b|)\)
Zero \(\gcd(a,0)=|a|\) (\(a\neq 0\))
Idempotent \(\gcd(a,a)=|a|\)
Scaling \(\gcd(ca,cb)=|c|\gcd(a,b)\)
Coprime reduction \(\gcd(a/d,b/d)=1\) if \(d=\gcd(a,b)\)
Product identity \(\gcd(a,b)\cdot\mathrm{lcm}(a,b)=|ab|\)
Coprime factors if \(\gcd(a,b)=1\) and \(a\mid bc\) then \(a\mid c\)
Pairwise if \(\gcd(a,b)=\gcd(a,c)=1\) then \(\gcd(a,bc)=1\)

Proof of pairwise coprimality via FTA. Primes of \(a\) appear in neither \(b\) nor \(c\), hence not in \(bc\).

Proof of product identity via FTA. With \(a=\prod p^{\alpha}\), \(b=\prod p^{\beta}\), \[ \min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta, \] so multiplying gcd and lcm multiplies to \(ab\).

Deep dive — why Euclid’s lemma is the “prime atom” law

Compare three statements:

  1. Prime definition: only positive divisors \(1,p\).
  2. Euclid’s lemma: \(p\mid ab\Rightarrow p\mid a\) or \(p\mid b\).
  3. FTA uniqueness: prime factorizations unique up to order.

In \(\mathbb{Z}\), (1) implies (2) once Bézout is available, and (2) implies (3). In more exotic rings, “irreducible” (cannot factor nontrivially) and “prime” (satisfies Euclid’s lemma) can diverge — awareness that \(\mathbb{Z}\) is special. For CS, the moral is: cancellation of primes in integer equations is licensed by Euclid’s lemma / FTA, not by wishful thinking.

Worked contrast. From \(2a=2b\) we cancel \(2\) to get \(a=b\) in \(\mathbb{Z}\). From \(4a=4b\) we may also cancel, but from \(4\mid ab\) we cannot conclude \(4\mid a\) or \(4\mid b\) (\(a=b=2\)).

Additional worked examples

Example 11 — Prove: if \(a\mid b\) and \(b\neq 0\) then \(|a|\le|b|\).
\(b=ak\) with \(k\neq 0\), so \(|b|=|a||k|\ge|a|\).

Example 12 — Common multiple structure.
Every common multiple of \(a,b>0\) is a multiple of \(\mathrm{lcm}(a,b)\). Via FTA: exponents in a common multiple are \(\ge\max(\alpha,\beta)\), so divisible by the lcm’s exponents.

Example 13 — Squarefree kernel.
If \(n=\prod p_i^{e_i}\), the radical \(\mathrm{rad}(n)=\prod p_i\) is the largest squarefree divisor. Example: \(\mathrm{rad}(360)=2\cdot 3\cdot 5=30\).

Example 14 — Prove \(n\) and \(n+1\) are always coprime.
Any common divisor divides \((n+1)-n=1\).

Example 15 — Division algorithm for \(a=-100\), \(d=7\).
\(-100=7\cdot(-15)+5\) because \(-105+5=-100\) and \(0\le 5<7\). Check: languages that return remainder \(-2\) for \(-100\%7\) are using a different convention.

Selected mini-solutions (check after attempting)

  1. \(b=ak\) ⇒ \(bc=a(kc)\).
  2. \(b=ak\), \(c=a\ell\) ⇒ \(3b-5c=a(3k-5\ell)\).
  3. Minimal \(d>1\) dividing \(n\) is prime (else smaller divisor \(>1\)).
  4. \(504=2^3\cdot 3^2\cdot 7\), \(1001=7\cdot 11\cdot 13\), \(\gcd=7\), \(\mathrm{lcm}=2^3\cdot 3^2\cdot 7\cdot 11\cdot 13\).
  5. Even exponents in \(a^2\) ≤ even exponents in \(b^2\) ⇒ half-exponents give \(a\mid b\).
  6. \(\tau(n)\) odd iff \(n\) is a square (divisors pair \(d\leftrightarrow n/d\) except when \(d=\sqrt{n}\)).

Common pitfalls

Pitfall Fix
Treating \(1\) as prime Primes are \(>1\) with exactly two positive divisors
“Unique factorization” including order or units Uniqueness is up to order; units \(\pm 1\) are not primes
Applying Euclid’s lemma to composites Needs primality (or coprimality variants)
Forgetting negative divisors when asked for “all divisors” \(\pm\) pairs unless positivity is specified
Confusing \(a\mid b\) with \(a/b\) as a rational Divisibility is an integer statement
Negative remainders Use \(0\le r<d\) mathematical convention
Cancelling composites as if primes Use Gauss only when coprime

Checkpoint

  • Can write \(a\mid b\) formally and prove the linear-combination property
  • Can state FTA in canonical exponent form and compute gcd/lcm from it
  • Can state Euclid’s lemma and give a composite counterexample to the naive version
  • Can prove infinitude of primes (Euclid) from memory
  • Can count \(\tau(n)\) from prime factorization
  • Exercises A–D essentially done; E optional stretch

Two personal takeaways:

  1. …
  2. …

Tomorrow

Day 72 — Euclidean algorithm and extended Euclid (Bézout).