Solve Modular Arithmetic
Parse congruence systems → extended Euclidean for inverses → CRT for systems → Euler for exponentiation. Verify all by substitution.
Use When
- Single linear congruence ax = b (mod m)
- System of simultaneous congruences (CRT)
- Mod inverse a^{-1} (mod m)
- Large mod exp a^k (mod m)
- Order of element in Z/mZ
- Cyclic groups, primitive roots, discrete log
In
- Required: Congruence(s) | mod eqn
- Optional: Show extended Euclidean steps explicit?
- Optional: Apply Euler | Fermat?
- Optional: Find primitive roots | element orders?
- Optional: Output (step-by-step, compact, proof)
Do
Step 1: Parse System / Eqn
Extract math structure.
ID type:
- Single linear: ax = b (mod m)
- System: x = a1 (mod m1), x = a2 (mod m2), ...
- Mod exp: a^k (mod m)
- Mod inverse: find a^{-1} (mod m)
Normalize: Reduce coefs mod respective moduli. a, b, m non-neg, m > 0.
Record parsed problem in standard notation.
Got: Clearly parsed + normalized problem, all values reduced.
If err: Ambiguous notation ("solve 3x + 5 = 2 mod 7" → equation or 5=2 mod 7?) → clarify w/ user. Default: mod applies to entire eqn.
Step 2: Solve Single Congruence
ax = b (mod m) via extended Euclidean.
g = gcd(a, m) via Euclidean:
- Repeated div: m = q1·a + r1, a = q2·r1 + r2, ... until rem = 0
- Last non-zero rem = gcd(a, m)
Solvability: solution iff g | b. Else no solution. Stop.
Reduce: ÷ g → (a/g)x = (b/g) (mod m/g). Now gcd(a/g, m/g) = 1.
Find inverse of a/g mod m/g via extended Euclidean:
- Back-sub through Euclidean → 1 = (a/g)·s + (m/g)·t
- Coef s (reduced mod m/g) = inverse
Particular sol: x0 = s·(b/g) mod (m/g).
General sol: x = x0 + (m/g)·k for k = 0, 1, ..., g-1 → all g incongruent solutions mod m.
Extended Euclidean ex (find 17^{-1} mod 43):
43 = 2*17 + 9
17 = 1*9 + 8
9 = 1*8 + 1
8 = 8*1 + 0
Back-substitute:
1 = 9 - 1*8
= 9 - 1*(17 - 1*9) = 2*9 - 17
= 2*(43 - 2*17) - 17 = 2*43 - 5*17
So 17*(-5) = 1 (mod 43), i.e., 17^{-1} = -5 = 38 (mod 43).
Got: Complete solution set, or proof no solution exists.
If err: Back-sub wrong result → verify each div step. Most common err: sign mistake in back-sub. Check: a · inverse mod m should = 1.
Step 3: System via CRT
Solve x = a1 (mod m1), x = a2 (mod m2), ..., x = ak (mod mk).
Pairwise coprime check: every pair (mi, mj), gcd(mi, mj) = 1.
- All coprime → CRT applies directly
- Some not coprime → check compat: each non-coprime pair, ai = aj (mod gcd(mi, mj)). Compat → reduce via lcm. Incompat → no sol.
M = m1 · m2 · ... · mk (product of all).
Each i, Mi = M/mi (product except mi).
Each i, yi = Mi^{-1} (mod mi) via extended Euclidean (Step 2).
Solution: x = sum(ai · Mi · yi for i = 1..k) mod M.
State: x = [val] (mod M). Unique sol mod M.
Common totients ref:
| n |
phi(n) |
n |
phi(n) |
n |
phi(n) |
| 2 |
1 |
10 |
4 |
20 |
8 |
| 3 |
2 |
11 |
10 |
24 |
8 |
| 4 |
2 |
12 |
4 |
25 |
20 |
| 5 |
4 |
13 |
12 |
30 |
8 |
| 6 |
2 |
14 |
6 |
36 |
12 |
| 7 |
6 |
15 |
8 |
48 |
16 |
| 8 |
4 |
16 |
8 |
60 |
16 |
| 9 |
6 |
18 |
6 |
100 |
40 |
Got: Unique sol mod M, or proof of incompat.
If err: CRT result fails verification → check Step 4 inverse calcs. Common: computing Mi^{-1} mod M instead of mod mi. Each inverse is mod individual mi, not product.
Step 4: Apply Euler / Fermat
Eval mod exponentiations | simplify w/ Euler.
Euler: gcd(a, m) = 1 → a^{phi(m)} = 1 (mod m).
- phi(m): if m = p1^e1 · p2^e2 · ... · pk^ek, phi(m) = m · product((1 - 1/pi) per prime pi | m).
Fermat little (special): p prime, gcd(a, p) = 1 → a^{p-1} = 1 (mod p).
Reduce exp: compute a^k (mod m):
- r = k mod phi(m)
- a^k = a^r (mod m)
a^r (mod m) via repeated squaring (binary exp):
- r in binary: r = b_n · 2^n + ... + b_1 · 2 + b_0
- result = 1
- Each bit MSB → LSB: result = result² mod m; bit = 1 → result = result · a mod m
gcd(a, m) > 1: Euler doesn't apply. Factor m + CRT to combine results from prime power moduli, lifting exponent | direct compute.
Got: a^k (mod m) value via exp reduction + repeated squaring.
If err: gcd(a, m) > 1 + result wrong → don't apply Euler. Compute direct | factor m into coprime parts where some coprime to a, solve mod each, recombine via CRT.
Step 5: Verify by Substitution
Plug solution back.
Single congruence: a · x mod m = b?
CRT systems: each x = ai (mod mi), x mod mi = ai?
Mod exponentiation: verify w/ 2nd method (direct for small | independent repeated squaring impl).
Document explicit:
Solution: x = 23
Check 1: 23 mod 3 = 2 = a1. Correct.
Check 2: 23 mod 5 = 3 = a2. Correct.
Check 3: 23 mod 7 = 2 = a3. Correct.
All congruences satisfied.
Got: All eqns verified w/ explicit computation.
If err: Verify fails → trace back. Common: arith mistakes in extended Euclidean, wrong sign in back-sub, forget reduce mod M in final CRT step.
Check
Traps
- CRT w/o coprime check: Standard formula needs pairwise coprime. Non-coprime → wrong answer not error. Check gcd(mi, mj) = 1 first.
- Wrong inverse: Mi^{-1} mod mi (individual), NOT mod M (product). Most common CRT impl err.
- Euler when gcd(a, m) > 1: a^{phi(m)} = 1 (mod m) needs gcd = 1. Else theorem doesn't apply, result wrong.
- Sign errs in extended Euclidean back-sub: Track signs each step. Final inverse may be neg → reduce mod m for positive rep.
- Overflow in mod exp: Even repeated squaring → intermediate products overflow. Reduce mod m after every mult, not just end.
- Forget multiple solutions: ax = b (mod m), g = gcd(a, m) > 1, g | b → exactly g incongruent solutions mod m, not just one.
→
analyze-prime-numbers — prime fact needed for phi(m) + verify coprime
explore-diophantine-equations — linear Diophantine ax + by = c equiv to linear congruence ax = c (mod b)
prove-geometric-theorem — mod arith in constructibility proofs (which regular n-gons are constructible)
1---2name: solve-modular-arithmetic-103description: "Solve mod arithmetic probs: congruences, systems via CRT, mod inverses, Euler's theorem. Manual + computational. Use → linear congruences, mod inverses, large mod exponentiation, simultaneous congruences (CRT), cyclic groups + discrete log contexts."4license: MIT5---67# Solve Modular Arithmetic89Parse congruence systems → extended Euclidean for inverses → CRT for systems → Euler for exponentiation. Verify all by substitution.1011## Use When1213- Single linear congruence ax = b (mod m)14- System of simultaneous congruences (CRT)15- Mod inverse a^{-1} (mod m)16- Large mod exp a^k (mod m)17- Order of element in Z/mZ18- Cyclic groups, primitive roots, discrete log1920## In2122- **Required**: Congruence(s) | mod eqn23- **Optional**: Show extended Euclidean steps explicit?24- **Optional**: Apply Euler | Fermat?25- **Optional**: Find primitive roots | element orders?26- **Optional**: Output (step-by-step, compact, proof)2728## Do2930### Step 1: Parse System / Eqn3132Extract math structure.33341. **ID type**:35 - Single linear: ax = b (mod m)36 - System: x = a1 (mod m1), x = a2 (mod m2), ...37 - Mod exp: a^k (mod m)38 - Mod inverse: find a^{-1} (mod m)39402. **Normalize**: Reduce coefs mod respective moduli. a, b, m non-neg, m > 0.41423. **Record** parsed problem in standard notation.4344**Got:** Clearly parsed + normalized problem, all values reduced.4546**If err:** Ambiguous notation ("solve 3x + 5 = 2 mod 7" → equation or 5=2 mod 7?) → clarify w/ user. Default: mod applies to entire eqn.4748### Step 2: Solve Single Congruence4950ax = b (mod m) via extended Euclidean.51521. **g = gcd(a, m)** via Euclidean:53 - Repeated div: m = q1·a + r1, a = q2·r1 + r2, ... until rem = 054 - Last non-zero rem = gcd(a, m)55562. **Solvability**: solution iff g | b. Else no solution. Stop.57583. **Reduce**: ÷ g → (a/g)x = (b/g) (mod m/g). Now gcd(a/g, m/g) = 1.59604. **Find inverse** of a/g mod m/g via extended Euclidean:61 - Back-sub through Euclidean → 1 = (a/g)·s + (m/g)·t62 - Coef s (reduced mod m/g) = inverse63645. **Particular sol**: x0 = s·(b/g) mod (m/g).65666. **General sol**: x = x0 + (m/g)·k for k = 0, 1, ..., g-1 → all g incongruent solutions mod m.6768**Extended Euclidean ex (find 17^{-1} mod 43):**69```text7043 = 2*17 + 97117 = 1*9 + 872 9 = 1*8 + 173 8 = 8*1 + 07475Back-substitute:761 = 9 - 1*877 = 9 - 1*(17 - 1*9) = 2*9 - 1778 = 2*(43 - 2*17) - 17 = 2*43 - 5*177980So 17*(-5) = 1 (mod 43), i.e., 17^{-1} = -5 = 38 (mod 43).81```8283**Got:** Complete solution set, or proof no solution exists.8485**If err:** Back-sub wrong result → verify each div step. Most common err: sign mistake in back-sub. Check: a · inverse mod m should = 1.8687### Step 3: System via CRT8889Solve x = a1 (mod m1), x = a2 (mod m2), ..., x = ak (mod mk).90911. **Pairwise coprime check**: every pair (mi, mj), gcd(mi, mj) = 1.92 - All coprime → CRT applies directly93 - Some not coprime → check compat: each non-coprime pair, ai = aj (mod gcd(mi, mj)). Compat → reduce via lcm. Incompat → no sol.94952. **M = m1 · m2 · ... · mk** (product of all).96973. **Each i, Mi = M/mi** (product except mi).98994. **Each i, yi = Mi^{-1} (mod mi)** via extended Euclidean (Step 2).1001015. **Solution**: x = sum(ai · Mi · yi for i = 1..k) mod M.1021036. **State**: x = [val] (mod M). Unique sol mod M.104105**Common totients ref:**106107| n | phi(n) | n | phi(n) | n | phi(n) |108|---|---|---|---|---|---|109| 2 | 1 | 10 | 4 | 20 | 8 |110| 3 | 2 | 11 | 10 | 24 | 8 |111| 4 | 2 | 12 | 4 | 25 | 20 |112| 5 | 4 | 13 | 12 | 30 | 8 |113| 6 | 2 | 14 | 6 | 36 | 12 |114| 7 | 6 | 15 | 8 | 48 | 16 |115| 8 | 4 | 16 | 8 | 60 | 16 |116| 9 | 6 | 18 | 6 | 100 | 40 |117118**Got:** Unique sol mod M, or proof of incompat.119120**If err:** CRT result fails verification → check Step 4 inverse calcs. Common: computing Mi^{-1} mod M instead of mod mi. Each inverse is mod *individual* mi, not product.121122### Step 4: Apply Euler / Fermat123124Eval mod exponentiations | simplify w/ Euler.1251261. **Euler**: gcd(a, m) = 1 → a^{phi(m)} = 1 (mod m).127 - phi(m): if m = p1^e1 · p2^e2 · ... · pk^ek, phi(m) = m · product((1 - 1/pi) per prime pi | m).1281292. **Fermat little (special)**: p prime, gcd(a, p) = 1 → a^{p-1} = 1 (mod p).1301313. **Reduce exp**: compute a^k (mod m):132 - r = k mod phi(m)133 - a^k = a^r (mod m)1341354. **a^r (mod m)** via repeated squaring (binary exp):136 - r in binary: r = b_n · 2^n + ... + b_1 · 2 + b_0137 - result = 1138 - Each bit MSB → LSB: result = result² mod m; bit = 1 → result = result · a mod m1391405. **gcd(a, m) > 1**: Euler doesn't apply. Factor m + CRT to combine results from prime power moduli, lifting exponent | direct compute.141142**Got:** a^k (mod m) value via exp reduction + repeated squaring.143144**If err:** gcd(a, m) > 1 + result wrong → don't apply Euler. Compute direct | factor m into coprime parts where some coprime to a, solve mod each, recombine via CRT.145146### Step 5: Verify by Substitution147148Plug solution back.1491501. **Single congruence**: a · x mod m = b?1511522. **CRT systems**: each x = ai (mod mi), x mod mi = ai?1531543. **Mod exponentiation**: verify w/ 2nd method (direct for small | independent repeated squaring impl).1551564. **Document explicit**:157```text158Solution: x = 23159Check 1: 23 mod 3 = 2 = a1. Correct.160Check 2: 23 mod 5 = 3 = a2. Correct.161Check 3: 23 mod 7 = 2 = a3. Correct.162All congruences satisfied.163```164165**Got:** All eqns verified w/ explicit computation.166167**If err:** Verify fails → trace back. Common: arith mistakes in extended Euclidean, wrong sign in back-sub, forget reduce mod M in final CRT step.168169## Check170171- [ ] Type ID'd (single, system, exp, inverse)172- [ ] All coefs reduced mod respective moduli173- [ ] ax = b (mod m): gcd(a, m) | b checked before solving174- [ ] Extended Euclidean back-sub verified: a · inverse mod m = 1175- [ ] CRT: pairwise coprime verified before176- [ ] CRT non-coprime: compat checked177- [ ] Euler applied only when gcd(a, m) = 1178- [ ] phi(m) from prime factorization, not guessed179- [ ] Repeated squaring uses mod reduction every step (no overflow)180- [ ] Every sol verified by substitution181182## Traps183184- **CRT w/o coprime check**: Standard formula needs pairwise coprime. Non-coprime → wrong answer not error. Check gcd(mi, mj) = 1 first.185- **Wrong inverse**: Mi^{-1} mod mi (individual), NOT mod M (product). Most common CRT impl err.186- **Euler when gcd(a, m) > 1**: a^{phi(m)} = 1 (mod m) needs gcd = 1. Else theorem doesn't apply, result wrong.187- **Sign errs in extended Euclidean back-sub**: Track signs each step. Final inverse may be neg → reduce mod m for positive rep.188- **Overflow in mod exp**: Even repeated squaring → intermediate products overflow. Reduce mod m after every mult, not just end.189- **Forget multiple solutions**: ax = b (mod m), g = gcd(a, m) > 1, g | b → exactly g incongruent solutions mod m, not just one.190191## →192193- `analyze-prime-numbers` — prime fact needed for phi(m) + verify coprime194- `explore-diophantine-equations` — linear Diophantine ax + by = c equiv to linear congruence ax = c (mod b)195- `prove-geometric-theorem` — mod arith in constructibility proofs (which regular n-gons are constructible)