Files
skills/public/number-theory.html
zeekayandHanzo Dev 9e10c1c10e Each llms index points at the other two
hanzoskills.com/llms.txt now opens with the install line, the API
reference index and the company index, so an agent that lands on any
one of the three can find the rest.

robots.txt claimed 537 documents while llms.txt counts 920. The number
is gone from robots.txt; llms.txt derives it.

public/ is regenerated from scripts/site.py, which it had fallen
behind: the copy-prompt menu and agent bar were in the generator and
not in the committed pages. tests/site.mjs passes against the result.

Co-authored-by: Hanzo Dev <[email protected]>
2026-09-11 00:27:59 -07:00

669 lines
28 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>number-theory</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="alternate" type="text/markdown" href="/number-theory.md">
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/number-theory">
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/number-theory.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>number-theory</h1><p class="lede">Number theory including primes, modular arithmetic, Diophantine equations, and cryptographic applications</p><h1>Number Theory</h1>
<p><strong>Scope</strong>: Primes, divisibility, modular arithmetic, Diophantine equations, quadratic residues, cryptography <strong>Lines</strong>: ~400 <strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Working with prime numbers and factorization</li><li>Implementing modular arithmetic for cryptography</li><li>Solving Diophantine equations</li><li>Understanding RSA, Diffie-Hellman, elliptic curve crypto</li><li>Analyzing divisibility and congruences</li><li>Computing number-theoretic functions (φ, τ, σ)</li></ul>
<h2>Core Concepts</h2>
<h3>Divisibility and Primes</h3>
<p><strong>Division algorithm</strong>: For a, b ∈ ℤ with b &gt; 0, ∃! q, r: a = bq + r with 0 ≤ r &lt; b</p>
<p><strong>GCD and LCM</strong>:</p>
<pre><code class="lang-python">import math
from typing import Tuple
def gcd(a: int, b: int) -&gt; int:
&quot;&quot;&quot;Euclidean algorithm for GCD&quot;&quot;&quot;
while b:
a, b = b, a % b
return abs(a)
def extended_gcd(a: int, b: int) -&gt; Tuple[int, int, int]:
&quot;&quot;&quot;
Extended Euclidean algorithm
Returns (gcd, x, y) where gcd = ax + by
&quot;&quot;&quot;
if b == 0:
return abs(a), 1 if a &gt;= 0 else -1, 0
gcd_val, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd_val, x, y
def lcm(a: int, b: int) -&gt; int:
&quot;&quot;&quot;LCM via gcd: lcm(a,b) = |ab|/gcd(a,b)&quot;&quot;&quot;
return abs(a * b) // gcd(a, b)
# Example
a, b = 48, 18
g = gcd(a, b)
print(f&quot;gcd({a}, {b}) = {g}&quot;) # 6
g, x, y = extended_gcd(a, b)
print(f&quot;{g} = {a}·{x} + {b}·{y}&quot;) # 6 = 48·(-1) + 18·3
print(f&quot;Verify: {a*x + b*y}&quot;) # 6</code></pre>
<p><strong>Prime testing</strong>:</p>
<pre><code class="lang-python">def is_prime(n: int) -&gt; bool:
&quot;&quot;&quot;Trial division primality test&quot;&quot;&quot;
if n &lt; 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
# Check odd divisors up to √n
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
def miller_rabin(n: int, k: int = 5) -&gt; bool:
&quot;&quot;&quot;
Miller-Rabin primality test (probabilistic)
k: number of rounds (higher = more accurate)
Error probability: 4^(-k)
&quot;&quot;&quot;
if n &lt; 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# Write n-1 = 2^r · d
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# Miller-Rabin test
import random
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n) # a^d mod n
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False # Composite
return True # Probably prime
# Example
print(f&quot;Is 97 prime? {is_prime(97)}&quot;) # True
print(f&quot;Is 1009 prime (Miller-Rabin)? {miller_rabin(1009)}&quot;) # True</code></pre>
<p><strong>Sieve of Eratosthenes</strong>:</p>
<pre><code class="lang-python">def sieve_of_eratosthenes(limit: int) -&gt; list[int]:
&quot;&quot;&quot;Generate all primes up to limit&quot;&quot;&quot;
if limit &lt; 2:
return []
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
# Mark multiples as composite
for j in range(i*i, limit + 1, i):
is_prime[j] = False
return [i for i in range(limit + 1) if is_prime[i]]
# Example
primes = sieve_of_eratosthenes(100)
print(f&quot;Primes up to 100: {primes[:10]}...&quot;) # [2, 3, 5, 7, 11, 13, ...]</code></pre>
<h3>Modular Arithmetic</h3>
<p><strong>Congruences</strong>: a ≡ b (mod n) iff n | (a - b)</p>
<p><strong>Modular inverse</strong>:</p>
<pre><code class="lang-python">def mod_inverse(a: int, n: int) -&gt; int:
&quot;&quot;&quot;
Compute a^(-1) mod n (multiplicative inverse)
Exists iff gcd(a, n) = 1
&quot;&quot;&quot;
gcd_val, x, _ = extended_gcd(a, n)
if gcd_val != 1:
raise ValueError(f&quot;No inverse: gcd({a}, {n}) = {gcd_val} ≠ 1&quot;)
return x % n
def chinese_remainder_theorem(moduli: list[int], remainders: list[int]) -&gt; int:
&quot;&quot;&quot;
Solve system: x ≡ a_i (mod n_i)
Requires moduli pairwise coprime
&quot;&quot;&quot;
if len(moduli) != len(remainders):
raise ValueError(&quot;Moduli and remainders must have same length&quot;)
# Check coprimality
for i in range(len(moduli)):
for j in range(i + 1, len(moduli)):
if gcd(moduli[i], moduli[j]) != 1:
raise ValueError(f&quot;Moduli not coprime: gcd({moduli[i]}, {moduli[j]}) ≠ 1&quot;)
# Compute solution
N = 1
for n in moduli:
N *= n
x = 0
for n_i, a_i in zip(moduli, remainders):
N_i = N // n_i
M_i = mod_inverse(N_i, n_i)
x += a_i * N_i * M_i
return x % N
# Example
moduli = [3, 5, 7]
remainders = [2, 3, 2]
solution = chinese_remainder_theorem(moduli, remainders)
print(f&quot;Solution to CRT system: x ≡ {solution} (mod {3*5*7})&quot;) # x = 23
# Verify
for n, a in zip(moduli, remainders):
print(f&quot;{solution} ≡ {solution % n} (mod {n}), expected {a}&quot;)</code></pre>
<p><strong>Euler&#x27;s totient function</strong>:</p>
<pre><code class="lang-python">def euler_phi(n: int) -&gt; int:
&quot;&quot;&quot;
φ(n) = |{k : 1 ≤ k ≤ n, gcd(k,n) = 1}|
Number of integers coprime to n
&quot;&quot;&quot;
result = n
p = 2
# Factor n and apply φ(p^k) = p^(k-1)(p-1)
while p * p &lt;= n:
if n % p == 0:
# Remove factor p
while n % p == 0:
n //= p
# Multiply by (1 - 1/p)
result -= result // p
p += 1
if n &gt; 1:
# n is prime
result -= result // n
return result
# Examples
print(f&quot;φ(9) = {euler_phi(9)}&quot;) # 6 (1,2,4,5,7,8 coprime to 9)
print(f&quot;φ(12) = {euler_phi(12)}&quot;) # 4 (1,5,7,11)
# Euler&#x27;s theorem: a^φ(n) ≡ 1 (mod n) if gcd(a,n)=1
n = 10
a = 3
assert pow(a, euler_phi(n), n) == 1
print(f&quot;{a}^φ({n}) ≡ {pow(a, euler_phi(n), n)} (mod {n})&quot;)</code></pre>
<h3>Quadratic Residues</h3>
<p><strong>Legendre symbol</strong>: (a/p) = 1 if a is quadratic residue mod p, -1 otherwise</p>
<pre><code class="lang-python">def legendre_symbol(a: int, p: int) -&gt; int:
&quot;&quot;&quot;
Compute (a/p) using Euler&#x27;s criterion:
(a/p) ≡ a^((p-1)/2) (mod p)
&quot;&quot;&quot;
if not is_prime(p) or p == 2:
raise ValueError(&quot;p must be odd prime&quot;)
a = a % p
if a == 0:
return 0
result = pow(a, (p - 1) // 2, p)
return -1 if result == p - 1 else result
def tonelli_shanks(n: int, p: int) -&gt; int:
&quot;&quot;&quot;
Find r such that r² ≡ n (mod p)
Tonelli-Shanks algorithm for modular square root
&quot;&quot;&quot;
if legendre_symbol(n, p) != 1:
raise ValueError(f&quot;{n} is not a quadratic residue mod {p}&quot;)
# Factor p-1 = Q · 2^S
Q, S = p - 1, 0
while Q % 2 == 0:
Q //= 2
S += 1
# Find quadratic non-residue
z = 2
while legendre_symbol(z, p) != -1:
z += 1
# Initialize
M = S
c = pow(z, Q, p)
t = pow(n, Q, p)
R = pow(n, (Q + 1) // 2, p)
while True:
if t == 0:
return 0
if t == 1:
return R
# Find least i: t^(2^i) = 1
i = 1
temp = (t * t) % p
while temp != 1:
temp = (temp * temp) % p
i += 1
# Update
b = pow(c, 1 &lt;&lt; (M - i - 1), p)
M = i
c = (b * b) % p
t = (t * c) % p
R = (R * b) % p
# Example: Solve x² ≡ 10 (mod 13)
p = 13
n = 10
print(f&quot;Legendre({n}/{p}) = {legendre_symbol(n, p)}&quot;) # 1 (is quadratic residue)
sqrt_mod = tonelli_shanks(n, p)
print(f&quot;√{n} ≡ {sqrt_mod} (mod {p})&quot;) # 6
print(f&quot;Verify: {sqrt_mod}² ≡ {(sqrt_mod**2) % p} (mod {p})&quot;) # 10</code></pre>
<h3>Diophantine Equations</h3>
<p><strong>Linear Diophantine</strong>: ax + by = c</p>
<pre><code class="lang-python">def linear_diophantine(a: int, b: int, c: int) -&gt; Tuple[int, int]:
&quot;&quot;&quot;
Solve ax + by = c
Solution exists iff gcd(a, b) | c
Returns one particular solution (x0, y0)
General solution: x = x0 + (b/d)t, y = y0 - (a/d)t
&quot;&quot;&quot;
g = gcd(a, b)
if c % g != 0:
raise ValueError(f&quot;No solution: gcd({a},{b})={g} does not divide {c}&quot;)
# Solve ax&#x27; + by&#x27; = g
_, x0, y0 = extended_gcd(a, b)
# Scale to ax + by = c
x = x0 * (c // g)
y = y0 * (c // g)
return x, y
# Example: 12x + 18y = 6
x, y = linear_diophantine(12, 18, 6)
print(f&quot;Solution to 12x + 18y = 6: x={x}, y={y}&quot;)
print(f&quot;Verify: 12·{x} + 18·{y} = {12*x + 18*y}&quot;)</code></pre>
<p><strong>Pell&#x27;s equation</strong>: x² - Dy² = 1</p>
<pre><code class="lang-python">def solve_pell(D: int, limit: int = 100) -&gt; Tuple[int, int]:
&quot;&quot;&quot;
Find smallest solution to x² - Dy² = 1
Using continued fraction of √D
&quot;&quot;&quot;
if int(D**0.5)**2 == D:
raise ValueError(&quot;D must not be a perfect square&quot;)
# Continued fraction expansion of √D
m, d, a0 = 0, 1, int(D**0.5)
# Convergents
p_prev, p = 0, 1
q_prev, q = 1, 0
a = a0
for _ in range(limit):
p, p_prev = a * p + p_prev, p
q, q_prev = a * q + q_prev, q
# Check if (p, q) is solution
if p*p - D*q*q == 1:
return p, q
# Next continued fraction term
m = d * a - m
d = (D - m*m) // d
a = (a0 + m) // d
raise ValueError(&quot;No solution found within limit&quot;)
# Example: x² - 2y² = 1
x, y = solve_pell(2)
print(f&quot;Smallest solution to x² - 2y² = 1: ({x}, {y})&quot;) # (3, 2)
print(f&quot;Verify: {x}² - 2·{y}² = {x*x - 2*y*y}&quot;) # 1</code></pre>
<h3>Cryptographic Applications</h3>
<p><strong>RSA encryption</strong>:</p>
<pre><code class="lang-python">def generate_rsa_keys(p: int, q: int, e: int = 65537):
&quot;&quot;&quot;
Generate RSA key pair
p, q: distinct primes
e: public exponent (commonly 65537)
&quot;&quot;&quot;
if not (is_prime(p) and is_prime(q)):
raise ValueError(&quot;p and q must be prime&quot;)
n = p * q
phi_n = (p - 1) * (q - 1)
if gcd(e, phi_n) != 1:
raise ValueError(f&quot;e={e} not coprime to φ(n)={phi_n}&quot;)
d = mod_inverse(e, phi_n)
return {
&#x27;public_key&#x27;: (n, e),
&#x27;private_key&#x27;: (n, d),
&#x27;p&#x27;: p,
&#x27;q&#x27;: q,
&#x27;phi_n&#x27;: phi_n
}
def rsa_encrypt(message: int, public_key: Tuple[int, int]) -&gt; int:
&quot;&quot;&quot;Encrypt: c = m^e mod n&quot;&quot;&quot;
n, e = public_key
return pow(message, e, n)
def rsa_decrypt(ciphertext: int, private_key: Tuple[int, int]) -&gt; int:
&quot;&quot;&quot;Decrypt: m = c^d mod n&quot;&quot;&quot;
n, d = private_key
return pow(ciphertext, d, n)
# Example
p, q = 61, 53
keys = generate_rsa_keys(p, q)
print(f&quot;Public key: (n={keys[&#x27;public_key&#x27;][0]}, e={keys[&#x27;public_key&#x27;][1]})&quot;)
print(f&quot;Private key: (n={keys[&#x27;private_key&#x27;][0]}, d={keys[&#x27;private_key&#x27;][1]})&quot;)
message = 123
ciphertext = rsa_encrypt(message, keys[&#x27;public_key&#x27;])
decrypted = rsa_decrypt(ciphertext, keys[&#x27;private_key&#x27;])
print(f&quot;Original message: {message}&quot;)
print(f&quot;Encrypted: {ciphertext}&quot;)
print(f&quot;Decrypted: {decrypted}&quot;)
assert message == decrypted</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Prime Factorization</h3>
<pre><code class="lang-python">def prime_factorization(n: int) -&gt; dict:
&quot;&quot;&quot;Return prime factorization as {prime: exponent}&quot;&quot;&quot;
factors = {}
d = 2
while d * d &lt;= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1
if n &gt; 1:
factors[n] = factors.get(n, 0) + 1
return factors
# Example
n = 360
factors = prime_factorization(n)
print(f&quot;{n} = {&#x27; · &#x27;.join(f&#x27;{p}^{e}&#x27; if e &gt; 1 else str(p) for p, e in factors.items())}&quot;)
# 360 = 2^3 · 3^2 · 5</code></pre>
<h3>Pattern 2: Fermat&#x27;s Little Theorem</h3>
<p><strong>Theorem</strong>: If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p)</p>
<pre><code class="lang-python">def fermat_primality_test(n: int, k: int = 5) -&gt; bool:
&quot;&quot;&quot;
Probabilistic primality test using Fermat&#x27;s Little Theorem
k: number of rounds
&quot;&quot;&quot;
if n &lt; 2:
return False
if n == 2 or n == 3:
return True
import random
for _ in range(k):
a = random.randint(2, n - 2)
if pow(a, n - 1, n) != 1:
return False # Definitely composite
return True # Probably prime (may fail for Carmichael numbers)</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Number-Theoretic Functions</h3>
<p>| Function | Definition | Example | |----------|-----------|---------| | φ(n) | Euler&#x27;s totient | φ(12) = 4 | | τ(n) | Number of divisors | τ(12) = 6 | | σ(n) | Sum of divisors | σ(12) = 28 | | ω(n) | Number of distinct prime factors | ω(12) = 2 | | Ω(n) | Number of prime factors (with multiplicity) | Ω(12) = 4 |</p>
<h3>Important Theorems</h3>
<pre><code>Fermat&#x27;s Little Theorem: p prime, gcd(a,p)=1 ⟹ a^(p-1) ≡ 1 (mod p)
Euler&#x27;s Theorem: gcd(a,n)=1 ⟹ a^φ(n) ≡ 1 (mod n)
Wilson&#x27;s Theorem: p prime ⟺ (p-1)! ≡ -1 (mod p)
Chinese Remainder Theorem: System of congruences has unique solution mod N</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>Using trial division for large primes</strong>: O(√n) too slow ✅ Use Miller-Rabin or other probabilistic tests</p>
<p>❌ <strong>Assuming Fermat test is conclusive</strong>: Carmichael numbers pass but aren&#x27;t prime ✅ Use Miller-Rabin which handles Carmichael numbers</p>
<p>❌ <strong>Computing a^b mod n naively</strong>: Overflow for large numbers ✅ Use built-in <code>pow(a, b, n)</code> with modular exponentiation</p>
<p>❌ <strong>Forgetting coprimality requirement</strong>: CRT needs pairwise coprime moduli ✅ Verify gcd(n_i, n_j) = 1 before applying CRT</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>abstract-algebra.md</code> - Rings ℤ/nℤ, fields, Galois theory</li><li><code>set-theory.md</code> - Cardinality of ℕ, ℤ, ℚ</li><li><code>formal/z3-solver-basics.md</code> - Solving number-theoretic constraints</li><li><code>cryptography.md</code> - RSA, Diffie-Hellman, elliptic curves (if exists)</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-25 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/number-theory.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>