Day 80 — Gate VII
Day 80 — Gate VII (Number theory for CS)
Stage VII · gate day
Goal: Demonstrate integrated literacy: Euclid + extended Euclid, modular inverses, Fermat/Euler reduction, small CRT, RSA parameter identification, hash collision estimates, and one divisibility proof — without labs.
Why this matters
Stage VII tools reappear in the capstone (modular computation + inverse) and in every later systems discussion of hashing, modular reduction, and public-key stories. This gate certifies calculation fluency and short proof control under mild time pressure.
No labs. Written mathematics only. Calculator only after a hand solution exists, and only for arithmetic check.
How to take this gate
- Timebox 100–140 minutes optional but recommended.
- Closed notes first pass; open notes only for remediation.
- Show all Euclid tables / inverse checks.
- Score with the rubric; remediate any section below \(50\%\) of its points.
- Log errors in a personal error file (congruence mistakes, inverse signs, CRT verification).
Rubric
| Section | Points | Pass bar |
|---|---|---|
| A Divisibility & Euclid | 20 | ≥ 14 |
| B Inverses & linear congruences | 20 | ≥ 14 |
| C Fermat / Euler reduction | 15 | ≥ 10 |
| D CRT | 15 | ≥ 10 |
| E Hashing + crypto literacy | 15 | ≥ 10 |
| F Proof + mixed | 15 | ≥ 10 |
| Total | 100 | ≥ 75, no section \(<50\%\) |
Section A — Divisibility & Euclid (20)
- (3) Write the definition of \(a\mid b\). Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(bx+cy)\) for all integers \(x,y\).
- (3) Compute \(\gcd(1230,348)\) by Euclid; show every step.
- (4) Find integers \(x,y\) with \(1230x+348y=\gcd(1230,348)\).
- (3) State Euclid’s lemma. Prove it using Bézout (short).
- (3) Factor \(360\) completely; compute \(\gcd(360,252)\) and \(\mathrm{lcm}(360,252)\) via FTA or Euclid+identity.
- (4) Solve \(348x+1230y=18\) or show impossible. If possible, give the general solution.
Section B — Inverses & linear congruences (20)
- (3) For which \(a\in\{0,1,\ldots,14\}\) does \(a^{-1}\bmod 15\) exist? List them.
- (4) Compute \(11^{-1}\bmod 26\) by extended Euclid; verify.
- (4) Solve \(11x\equiv 15\pmod{26}\).
- (4) Solve \(6x\equiv 9\pmod{15}\); list all incongruent solutions.
- (3) Prove: if \(ax\equiv 1\pmod n\) then \(\gcd(a,n)=1\).
- (2) State Wilson’s theorem. Verify for \(p=7\).
Section C — Fermat / Euler (15)
- (3) Compute \(\varphi(36)\) and \(\varphi(100)\).
- (4) Compute \(3^{100}\bmod 7\) using Fermat.
- (4) Compute \(7^{123}\bmod 10\) using Euler.
- (4) Find \(\mathrm{ord}_7(3)\) (smallest \(k>0\) with \(3^k\equiv 1\pmod 7\)). Confirm it divides \(\varphi(7)\).
Section D — CRT (15)
- (5) Solve \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\). Give all solutions.
- (5) Solve \(x\equiv 1\pmod 4\), \(x\equiv 2\pmod 5\), \(x\equiv 3\pmod 7\).
- (5) Does \(x\equiv 5\pmod{12}\), \(x\equiv 11\pmod{18}\) have a solution? Justify with the consistency criterion; if yes, find the general solution.
Section E — Hashing + crypto literacy (15)
- (3) Under uniform independent hashing of \(n=30\) keys into \(m=200\) buckets, compute expected number of colliding pairs \(\binom{n}{2}/m\).
- (3) Birthday literacy: about how large must \(n\) be for collisions to become likely when \(m=10^4\)? (Order \(\sqrt{m}\) with a numerical estimate.)
- (3) RSA toy: \(p=5\), \(q=13\), \(n=65\), \(\varphi=48\). Is \(e=5\) a valid public exponent? If yes, find \(d\) with \(ed\equiv 1\pmod{48}\).
- (3) DH: with public \(p,g\), Alice sends \(g^a\bmod p\), Bob \(g^b\bmod p\). What do they compute as shared secret? What problem should an eavesdropper not solve easily?
- (3) Name two reasons textbook RSA (\(c=m^e\bmod n\) with no padding) is not production encryption (literacy bullets).
Section F — Proof + mixed (15)
- (5) Prove one of the following carefully (full sentences):
- If \(p\) is prime and \(p\mid n^2\) then \(p\mid n\).
- If \(p\) is prime and \(p\mid n^2\) then \(p\mid n\).
- There are infinitely many primes (Euclid).
- There are infinitely many primes (Euclid).
- If \(\gcd(a,n)=1\) then \(a\) has an inverse mod \(n\) (existence via Bézout).
- If \(\gcd(a,n)=1\) then \(a\) has an inverse mod \(n\) (existence via Bézout).
- (5) LCG literacy: state Hull–Dobell’s three conditions. For \(m=8\), \(a=5\), \(c=3\), does full period hold? (Yes/no + which conditions.)
- (5) Mixed computation: find \(17^{-1}\bmod 100\), then solve the CRT system \(x\equiv 17^{-1}\pmod{4}\) wait — simpler: compute \(y=17^{-1}\bmod 100\), then find \(z\) with \(z\equiv y\pmod{100}\) and \(z\equiv 3\pmod 7\) (optional if time: at least compute \(y\) and set up the second congruence).
Alternate 27 (cleaner): Compute \(5^{30}\bmod 13\) and \(x\) solving \(x\equiv 4\pmod 7\), \(x\equiv 3\pmod{13}\).
Capstone bridge (required reflection, unscored but mandatory)
Write 5–10 lines:
- Which Stage VII skill is strongest / weakest?
- Which modular computation will you use in the Day 88–90 dossier? (State a concrete problem idea: inverse, CRT, or Fermat reduction.)
- One proof from this stage worth reusing as a capstone proof candidate?
Remediation map
| Weak section | Return to |
|---|---|
| A | Days 71–72 |
| B | Days 73–74 |
| C | Day 75 |
| D | Day 78 |
| E | Days 76–77, 79 |
| F | Days 71, 74, 79 |
Re-test only weak sections after targeted practice; full gate retake if total \(<75\).
Self-score sheet
| Section | Score | Notes / errors |
|---|---|---|
| A /20 | ||
| B /20 | ||
| C /15 | ||
| D /15 | ||
| E /15 | ||
| F /15 | ||
| Total /100 |
Pass? Y/N. Retake plan: …
Selected answer sketches (check only after attempting)
Use as verification, not as a first look.
- \(\gcd(1230,348)\): \(1230=3\cdot 348+186\); \(348=1\cdot 186+162\); \(186=1\cdot 162+24\); \(162=6\cdot 24+18\); \(24=1\cdot 18+6\); \(18=3\cdot 6+0\) ⇒ \(\gcd=6\).
- Extended Euclid on \((11,26)\) should yield inverse \(19\) because \(11\cdot 19=209=8\cdot 26+1\).
- \(\gcd(6,15)=3\mid 9\); solutions \(x\equiv 4,9,14\pmod{15}\) (verify).
- \(3^6\equiv 1\pmod 7\), \(100\equiv 4\pmod 6\) ⇒ \(3^{100}\equiv 3^4\equiv 81\equiv 4\pmod 7\).
- \(x\equiv 8\pmod{15}\).
- \(\gcd(5,48)=1\); find \(d\) with \(5d\equiv 1\pmod{48}\) (e.g. \(d=29\) since \(145=3\cdot 48+1\)).
If your answers differ, recompute before assuming the sketch is wrong — then compare carefully.
Common gate failures
| Failure | Fix |
|---|---|
| Inverse with wrong sign | Always verify \(ax\equiv 1\) |
| Euler without coprimality | Check \(\gcd(a,n)=1\) |
| CRT no verification | Plug \(x\) into each congruence |
| RSA \(d\) mod \(n\) | \(ed\equiv 1\pmod{\varphi(n)}\) |
| Birthday \(n=m\) | Use \(\sqrt{m}\) scale |
| Proof by example | General \(k\) in \(b=ak\) |
| Diophantine without \(d\mid c\) check | Always test divisibility first |
Extended answer sketches (second pass only)
3. From gcd steps for \((1230,348)\) ending at \(6\), back-substitute to \(1230x+348y=6\).
6. Scale the Bézout identity for \(6\) by \(3\) to reach \(18\); general solution uses \(\pm 348/6\) and \(\mp 1230/6\).
9. \(x\equiv 15\cdot 19\equiv 285\equiv 25\pmod{26}\) if inv is \(19\); verify \(11\cdot 25=275=10\cdot 26+15\).
15. \(7^4\equiv 1\pmod{10}\) cycle; \(123\bmod 4=3\) ⇒ \(7^{123}\equiv 7^3\equiv 3\pmod{10}\).
18. Use \(M=140\), compute \(M_i,y_i\) carefully; verify three ways.
20. \(\binom{30}{2}/200=435/200=2.175\).
21. \(\sqrt{10^4}=100\) order; refined \(\approx 1.2\cdot 100\approx 120\).
27 alt. \(5^{12}\equiv 1\pmod{13}\), \(30=2\cdot 12+6\), reduce; CRT: \(x=7k+4\equiv 3\pmod{13}\) ⇒ solve for \(k\).
Timing and strategy notes
| Time left | Priority |
|---|---|
| First 20 min | A+B calculation accuracy |
| Next 25 min | C+D (reduction + CRT) |
| Next 20 min | E literacy full sentences |
| Next 25 min | F proof quality |
| Last 10–15 | Checks: multiply inverses, plug CRT |
Partial credit maxims: write gcd steps even if stuck on coefficients; state Wilson even if pairing incomplete; give \(\sqrt{m}\) even if constant fuzzy.
Error log template (copy)
Item #:
Wrong step:
Correct step:
Root cause (cancel / sign / φ / gcd / other):
Drill: 3 similar problems from Day __Capstone modular item bank (choose one tonight)
- Inverse of \(23\) mod \(100\) + solve \(23x\equiv 7\pmod{100}\).
- CRT: \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\), \(x\equiv 2\pmod 5\).
- Compute \(3^{100}\bmod 7\) and \(3^{100}\bmod 13\), combine via CRT for mod \(91\).
- Full Euclid+Bézout on \((252,198)\) and interpret as inverse prep.
Record choice: ________
Optional oral mini-defense (5 min)
- State Euclid’s lemma + one-line Bézout proof idea.
- Why \(\varphi(15)=8\)? List units.
- What is wrong with “RSA is \(m^e\bmod n\) in production”?
- Birthday: why \(\sqrt{m}\) not \(m\)?
Stage VII formula sheet (memory side)
| Topic | Key fact |
|---|---|
| Divisibility | \(a\mid b\Leftrightarrow \exists k,\ b=ak\); linear combinations |
| Euclid | \(\gcd(a,b)=\gcd(b,a\bmod b)\); \(O(\log n)\) steps |
| Bézout | \(\exists x,y:\ ax+by=\gcd\) |
| Inverse | exists iff \(\gcd(a,n)=1\) |
| Fermat | \(a^{p-1}\equiv 1\pmod p\) (\(p\nmid a\)) |
| Euler | \(a^{\varphi(n)}\equiv 1\pmod n\) (\(\gcd=1\)) |
| CRT | coprime moduli ⇒ unique mod product |
| Birthday | collisions at \(\Theta(\sqrt{m})\) |
| RSA | \(ed\equiv 1\pmod{\varphi(n)}\); \(m^{ed}\equiv m\pmod n\) |
| Wilson | \((p-1)!\equiv -1\pmod p\) iff \(p\) prime (\(p>1\)) |
| LCG full period | Hull–Dobell three conditions on \((m,a,c)\) |
| Order | \(\mathrm{ord}_n(a)\mid\varphi(n)\) when \(\gcd(a,n)=1\) |
Gate motto: every inverse is checked by multiplication; every CRT answer is plugged back.
Mixed practice set (if gate finished early / remediation)
M1. Euclid + inverse: \(\gcd(97,20)\), then \(20^{-1}\bmod 97\) if exists.
M2. \(5^{30}\bmod 11\) by Fermat.
M3. CRT: \(x\equiv 4\pmod 7\), \(x\equiv 3\pmod{11}\).
M4. Expected colliding pairs \(n=25\), \(m=200\).
M5. RSA: \(n=35\), \(\varphi=24\), \(e=5\) — find \(d\); encrypt \(m=4\).
M6. Prove: if \(a\mid bc\) and \(\gcd(a,b)=1\) then \(a\mid c\) (Gauss).
M7. Hull–Dobell: does \((m,a,c)=(12,5,1)\) have full period?
M8. Wilson verify \(p=11\) by pairing, not by expanding \(10!\).
M9. Order of \(5\) mod \(12\) if defined; if not, explain.
M10. Write one paragraph linking Bézout → inverse → RSA \(d\).
Checkpoint
- Section A attempted closed-book
- Section B inverses verified by multiplication
- Section C exponent reductions shown with mod \(\varphi\) or \(p-1\)
- Section D CRT solutions checked
- Section E literacy answers written in full sentences
- Section F proof in full sentences
- Capstone modular item idea recorded
- Error log updated; remediation scheduled if needed
- Score ≥ 75 or retake plan dated
- Mixed practice M1–M5 attempted if remediating
Two personal takeaways from Stage VII:
- …
- …
Full worked gate rehearsal (timed practice set)
Do this set closed-book in \(45\) minutes before the formal gate, then score.
R1. Euclid: \(\gcd(252,198)\); Bézout coefficients for the gcd.
R2. Inverse: \(23^{-1}\bmod 100\); solve \(23x\equiv 15\pmod{100}\).
R3. Fermat: \(2^{40}\bmod 13\).
R4. Euler: last digit of \(9^{123}\) (i.e. mod \(10\)).
R5. CRT: \(x\equiv 3\pmod 5\), \(x\equiv 4\pmod 7\).
R6. Hash: \(\mathbb{E}[\text{colliding pairs}]\) for \(n=40\), \(m=800\).
R7. RSA: \(p=5,q=17,e=3\) — is \(e\) valid? Find \(d\).
R8. Hull–Dobell: \((m,a,c)=(16,5,3)\) full period?
R9. Wilson: verify \(p=5\) and explain why \(n=9\) fails.
R10. Proof: if \(\gcd(a,n)=1\) then \(a\) has an inverse mod \(n\).
Rehearsal answer keys (second pass)
R1. \(252=1\cdot 198+54\); \(198=3\cdot 54+36\); \(54=1\cdot 36+18\); \(36=2\cdot 18+0\) ⇒ \(\gcd=18\). Back-sub for \(18=252x+198y\).
R2. Extended Euclid on \((23,100)\) → inverse \(87\) because \(23\cdot 87=2001=20\cdot 100+1\); \(x\equiv 15\cdot 87=1305\equiv 5\pmod{100}\).
R3. \(2^{12}\equiv 1\pmod{13}\), \(40=3\cdot 12+4\) ⇒ \(2^{40}\equiv 2^4=16\equiv 3\).
R4. \(9^1\equiv 9\), \(9^2\equiv 1\pmod{10}\) cycle \(2\); \(123\) odd ⇒ last digit \(9\).
R5. \(x=5k+3\equiv 4\pmod 7\) ⇒ \(5k\equiv 1\pmod 7\); inv of \(5\) is \(3\); \(k\equiv 3\); \(x\equiv 18\pmod{35}\).
R6. \(\binom{40}{2}/800=780/800=0.975\).
R7. \(n=85\), \(\varphi=64\), \(\gcd(3,64)=1\); \(3d\equiv 1\pmod{64}\) ⇒ \(d=43\) (\(129=2\cdot 64+1\)).
R8. \(\gcd(3,16)=1\); \(5\equiv 1\pmod 2\); \(5\equiv 1\pmod 4\) — yes.
R9. \(4!=24\equiv -1\pmod 5\); \(8!\equiv 0\pmod 9\).
R10. Bézout \(ax+ny=1\) ⇒ \(ax\equiv 1\pmod n\).
Proof quality rubric (Section F)
| Level | Description |
|---|---|
| 0 | Example only; no general argument |
| 1 | States theorem; major gap |
| 2 | Correct idea; missing quantifiers or case |
| 3 | Full sentences; cites Bézout/Euclid/Wilson correctly |
| 4 | Clean, reusable write-up (capstone quality) |
Target level \(\ge 3\) on the chosen proof. Rewrite once if you score \(2\).
Stage VII integration map (capstone prep)
| Capstone need | Stage VII source day |
|---|---|
| Modular inverse | 74 |
| Exponent reduction | 75 |
| CRT recombination | 78 |
| Collision estimate | 76 |
| RSA parameter story | 77 |
| Randomness caveat | 79 |
| Divisibility lemmas | 71–72 |
Pick one computational item and one short proof for the Day 88 outline tonight.
Final pre-gate checklist (10 minutes)
- One Euclid table written from scratch
- One inverse verified by multiplication
- One CRT solution plugged back
- One Fermat reduction with exponent mod \(p-1\)
- One literacy paragraph (RSA or birthday) without notes
- Error log has at least two historical mistakes recorded
If any box is unchecked, spend \(15\) minutes on that skill before scoring the formal gate.
Tomorrow
Day 81 — Big-O formally (Stage VIII begins).