Day 4 — Factors, primes & FTA

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.