Number Theory, Groups & Algebraic Structures
Complete Guide for GATE CS — Divisibility, GCD, Modular Arithmetic, Fermat’s & Euler’s Theorems, Groups, Rings & Fields
Last Updated: April 2026
📌 Key Takeaways
- GCD via Euclidean Algorithm: gcd(a,b) = gcd(b, a mod b), base case gcd(a,0) = a. Time complexity: O(log(min(a,b))).
- Modular arithmetic: a ≡ b (mod m) iff m | (a−b). Addition, subtraction, multiplication all work under mod. Division requires modular inverse (exists iff gcd(a,m)=1).
- Fermat’s Little Theorem: p prime, gcd(a,p)=1 → ap−1 ≡ 1 (mod p). Used to reduce large exponents mod (p−1).
- Euler’s Theorem: gcd(a,n)=1 → aφ(n) ≡ 1 (mod n). Generalises Fermat (which is Euler when n is prime).
- φ(n): Count of integers 1..n coprime to n. For n=p₁a₁p₂a₂…: φ(n) = n×∏(1−1/pᵢ).
- Group: Closure + Associativity + Identity + Inverse. Abelian group: also commutative.
- Field: Both addition and multiplication form abelian groups (with 0 excluded for ×). ℤₚ (p prime) is always a field.
1. Divisibility & Prime Numbers
An integer a divides b (written a | b) if there exists an integer k such that b = ak. Equivalently, b mod a = 0.
Divisibility Properties
If a|b and a|c, then a|(bx + cy) for any integers x, y.
If a|b and b|c, then a|c (transitivity).
If a|b and b|a, then a = ±b.
Division Algorithm: For any integers a, b (b>0): a = qb + r where 0 ≤ r < b. q = quotient, r = remainder.
1.1 Prime Numbers
An integer p > 1 is prime if its only positive divisors are 1 and p. Otherwise it is composite.
Fundamental Theorem of Arithmetic
Every integer n > 1 can be expressed uniquely as a product of primes: n = p₁a₁ × p₂a₂ × … × pₖaₖ
Number of divisors of n: τ(n) = (a₁+1)(a₂+1)…(aₖ+1)
Example: 12 = 2²×3¹ → τ(12) = (2+1)(1+1) = 6 divisors: {1,2,3,4,6,12}
Sum of divisors of n: σ(n) = ∏ (pᵢaᵢ+1 − 1)/(pᵢ−1)
Primality test: To check if n is prime, test divisibility by all primes up to √n.
2. GCD, LCM & Euclidean Algorithm
GCD and LCM
gcd(a,b) = largest integer dividing both a and b
lcm(a,b) = smallest positive integer divisible by both a and b
Key identity: gcd(a,b) × lcm(a,b) = |a × b|
For prime factorizations: gcd takes MIN of exponents; lcm takes MAX.
a=12=2²3¹, b=18=2¹3²: gcd=2¹3¹=6, lcm=2²3²=36; 6×36=216=12×18 ✓
2.1 Euclidean Algorithm
Euclidean Algorithm: gcd(a, b)
Repeat: gcd(a, b) = gcd(b, a mod b) until b = 0; then gcd = a.
Example: gcd(252, 105):
252 = 2×105 + 42 → gcd(105, 42)
105 = 2×42 + 21 → gcd(42, 21)
42 = 2×21 + 0 → gcd = 21
Time Complexity: O(log(min(a,b))) steps
2.2 Extended Euclidean Algorithm
Finds x, y such that ax + by = gcd(a,b) (Bézout’s Identity). Used to find modular inverses.
3. Modular Arithmetic
a ≡ b (mod m) (a is congruent to b modulo m) means m | (a − b).
Modular Arithmetic Rules
If a ≡ b (mod m) and c ≡ d (mod m):
(a + c) ≡ (b + d) (mod m) [Addition]
(a − c) ≡ (b − d) (mod m) [Subtraction]
(a × c) ≡ (b × d) (mod m) [Multiplication]
Division (modular inverse): a/c ≡ a × c⁻¹ (mod m) where c⁻¹ is the modular inverse of c.
Modular inverse c⁻¹ (mod m) exists iff gcd(c, m) = 1
Find c⁻¹ via: Extended Euclidean, or Fermat’s (if m is prime): c⁻¹ ≡ cm−2 (mod m)
3.1 Solving Linear Congruences
To solve ax ≡ b (mod m):
- If gcd(a,m) ∤ b → no solution.
- If gcd(a,m) | b → exactly gcd(a,m) solutions modulo m.
- If gcd(a,m) = 1 → unique solution: x ≡ a⁻¹ × b (mod m).
4. Fermat’s & Euler’s Theorems
Fermat’s Little Theorem
If p is prime and gcd(a, p) = 1: ap−1 ≡ 1 (mod p)
Equivalently, for all a: ap ≡ a (mod p)
Application — reducing large exponents: ak mod p = ak mod (p−1) mod p (when gcd(a,p)=1)
Example: 7100 mod 13. Since 13 is prime, gcd(7,13)=1: 712≡1 mod 13. 100 = 8×12 + 4 → 7100 ≡ 74 = 2401 ≡ 2401 mod 13 = 2401−184×13 = 2401−2392 = 9
Euler’s Totient Function φ(n)
φ(n) = count of integers in {1,…,n} that are coprime to n
φ(1) = 1
φ(p) = p − 1 for prime p
φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p−1)
φ(mn) = φ(m)×φ(n) when gcd(m,n)=1 (multiplicative)
φ(n) = n × ∏p|n (1 − 1/p) (product over distinct prime factors)
| n | Factorization | φ(n) |
|---|---|---|
| 6 | 2×3 | 6×(1−½)×(1−⅓) = 2 |
| 12 | 2²×3 | 12×½×⅔ = 4 |
| 30 | 2×3×5 | 30×½×⅔×⅘ = 8 |
| 100 | 2²×5² | 100×½×⅘ = 40 |
Euler’s Theorem
If gcd(a, n) = 1: aφ(n) ≡ 1 (mod n)
Fermat’s theorem is the special case when n is prime (φ(p) = p−1).
RSA connection: RSA encryption uses Euler’s theorem with n=pq (product of two primes): encrypt with eᵏ, decrypt with d where ed ≡ 1 (mod φ(n)).
5. Chinese Remainder Theorem (CRT)
Chinese Remainder Theorem
If m₁, m₂, …, mₖ are pairwise coprime (gcd(mᵢ, mⱼ)=1 for i≠j), then the system:
x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₖ (mod mₖ)
has a unique solution modulo M = m₁×m₂×…×mₖ.
Solution: x = ∑ aᵢ × Mᵢ × (Mᵢ⁻¹ mod mᵢ) where Mᵢ = M/mᵢ
6. Groups & Subgroups
A group (G, ∗) is a set G with a binary operation ∗ satisfying:
| Axiom | Condition | Symbol |
|---|---|---|
| Closure | ∀ a,b ∈ G: a∗b ∈ G | — |
| Associativity | ∀ a,b,c ∈ G: (a∗b)∗c = a∗(b∗c) | — |
| Identity | ∃ e ∈ G: a∗e = e∗a = a for all a | e (unique) |
| Inverse | ∀ a ∈ G, ∃ a⁻¹ ∈ G: a∗a⁻¹ = a⁻¹∗a = e | a⁻¹ (unique) |
| Commutative (optional) | ∀ a,b ∈ G: a∗b = b∗a → Abelian group | — |
Key Group Results for GATE
Order of element a = smallest positive k with aᵏ = e
Lagrange’s Theorem: If H is a subgroup of finite group G, then |H| divides |G|.
Order of a divides |G| (direct consequence of Lagrange’s theorem)
Cyclic group: Generated by a single element g — every element is gᵏ for some k. Every cyclic group is abelian. ℤₙ under addition is cyclic of order n.
Number of generators of ℤₙ: φ(n) — the elements of order n, i.e., elements coprime to n.
6.1 Common Groups in CS
| Group | Operation | Order | Abelian? |
|---|---|---|---|
| (ℤ, +) | Addition | Infinite | Yes |
| (ℤₙ, +) | Addition mod n | n | Yes |
| (ℤₙ*, ×) | Multiplication mod n (units only) | φ(n) | Yes |
| (Sₙ, ∘) | Permutation composition | n! | No (n≥3) |
| ({0,1}ⁿ, XOR) | Bitwise XOR | 2ⁿ | Yes |
7. Rings & Fields
| Structure | Operations | Requirements | Example |
|---|---|---|---|
| Group | One (∗) | Closure, Assoc, Identity, Inverse | (ℤ,+) |
| Ring | Two (+, ×) | (R,+) abelian group; (R,×) closed+assoc+identity; × distributes over + | (ℤ,+,×) |
| Commutative Ring | Two (+, ×) | Ring + multiplication is commutative | (ℤ,+,×) |
| Integral Domain | Two (+, ×) | Commutative ring with no zero divisors | (ℤ,+,×) |
| Field | Two (+, ×) | Ring where every nonzero element has a multiplicative inverse | (ℚ,+,×), ℤₚ (p prime) |
Finite Fields (Galois Fields) GF(q)
A finite field exists for order q iff q = pⁿ for some prime p and positive integer n.
GF(p) = ℤₚ — integers mod prime p, with + and × mod p. Every element ≠0 has a multiplicative inverse.
GF(2) = {0,1} with addition = XOR, multiplication = AND. Used extensively in coding theory and cryptography.
GF(2ⁿ) — used in AES (GF(2⁸)) and error-correcting codes.
8. Worked Examples (GATE CS Level)
Example 1 — GCD, Modular Inverse & Fermat’s Theorem
Problem: (a) Find gcd(1071, 462) using the Euclidean algorithm. (b) Find the modular inverse of 7 modulo 11. (c) Compute 3200 mod 13.
(a) gcd(1071, 462):
1071 = 2 × 462 + 147 → gcd(462, 147)
462 = 3 × 147 + 21 → gcd(147, 21)
147 = 7 × 21 + 0 → gcd = 21
(b) Inverse of 7 mod 11:
Need x such that 7x ≡ 1 (mod 11). Since 11 is prime, use Fermat: 7⁻¹ ≡ 711−2 = 7⁹ (mod 11).
7² = 49 ≡ 5 (mod 11); 7⁴ ≡ 5² = 25 ≡ 3 (mod 11); 7⁸ ≡ 3² = 9 (mod 11); 7⁹ = 7⁸×7 ≡ 9×7 = 63 ≡ 8 (mod 11).
7⁻¹ ≡ 8 (mod 11). Verify: 7×8 = 56 = 5×11+1 ≡ 1 (mod 11) ✓
(c) 3200 mod 13:
13 is prime, gcd(3,13)=1. By Fermat: 312 ≡ 1 (mod 13).
200 = 16×12 + 8 → 3200 ≡ (312)16 × 38 ≡ 116 × 38 ≡ 38 (mod 13)
3² = 9; 3⁴ ≡ 81 ≡ 81−6×13 = 81−78 = 3 (mod 13); 3⁸ ≡ 3² = 9 (mod 13)
3200 mod 13 = 9
Example 2 — Euler’s Totient & CRT
Problem: (a) Compute φ(360). (b) Find the smallest positive x such that x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
(a) φ(360):
360 = 2³ × 3² × 5¹
φ(360) = 360 × (1−1/2) × (1−1/3) × (1−1/5) = 360 × ½ × ⅔ × ⅘ = 360 × 8/30 = 96
(b) CRT: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7):
M = 3×5×7 = 105; M₁=35, M₂=21, M₃=15
Find inverses: 35 mod 3 = 2, need 35y₁≡1(mod 3) → 2y₁≡1(mod 3) → y₁=2
21 mod 5 = 1, need 21y₂≡1(mod 5) → y₂=1
15 mod 7 = 1, need 15y₃≡1(mod 7) → y₃=1
x = 2×35×2 + 3×21×1 + 2×15×1 = 140 + 63 + 30 = 233
x ≡ 233 mod 105 = 233 − 2×105 = 233−210 = 23
Verify: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓
Example 3 — Group Properties & Order
Problem: (a) Is (ℤ₆, +) a group? What is the order of element 4? (b) How many generators does ℤ₁₂ have? (c) Is ℤ₆ under multiplication mod 6 a group? Why or why not?
(a) (ℤ₆, +) and order of 4:
ℤ₆ = {0,1,2,3,4,5} under addition mod 6. Identity = 0. Inverses: −a mod 6.
Closure ✓, Associativity ✓, Identity (0) ✓, Inverses ✓ → Yes, (ℤ₆,+) is a group.
Order of 4: find smallest k with 4k ≡ 0 (mod 6): 4,8≡2,12≡0 → k=3.
Order of 4 in (ℤ₆,+) = 3 (since 3 divides 6 — consistent with Lagrange’s theorem)
(b) Generators of ℤ₁₂:
Number of generators = φ(12) = 12×(1−½)×(1−⅓) = 4.
Generators: elements coprime to 12 in {1..12} = {1,5,7,11} → 4 generators
(c) ℤ₆ under multiplication — is it a group?
ℤ₆ = {0,1,2,3,4,5}. Multiplicative identity would be 1. Check inverses:
Element 2: need 2x ≡ 1 (mod 6) → 2x = 1,7,13,19… none divisible check: gcd(2,6)=2 ≠ 1 → no inverse exists.
No — (ℤ₆, ×) is NOT a group. Element 0 has no inverse, and elements 2,3,4 have gcd with 6 > 1, so no multiplicative inverses exist. Also, 2×3=6≡0 — zero divisors exist.
However, (ℤ₆*, ×) = ({1,5}, ×) IS a group (both elements coprime to 6).
9. 5 Common Mistakes in Number Theory & Algebra
Mistake 1 — Applying Fermat’s Theorem Without Checking Primality and Coprimality
What happens: Students apply ap−1 ≡ 1 (mod p) when p is not prime, or when gcd(a,p) ≠ 1.
Root cause: The theorem requires p to be prime AND gcd(a,p)=1. If p is composite, use Euler’s theorem with φ(p). If p | a, then a ≡ 0 (mod p) and ap−1 ≡ 0 ≢ 1.
Correct approach: Always verify: is p prime? Is gcd(a,p)=1? If p is composite, use aφ(p) ≡ 1 (mod p) when gcd(a,p)=1.
Mistake 2 — Confusing GCD Formula with Sum vs Product
What happens: Students write gcd(a,b)+lcm(a,b) = a×b instead of gcd×lcm = |a×b|.
Root cause: The identity is multiplicative: gcd(a,b) × lcm(a,b) = |a × b|.
Correct approach: lcm(a,b) = |a×b| / gcd(a,b). Always: the product of GCD and LCM equals the product of the two numbers (for positive integers).
Mistake 3 — Computing φ(n) Incorrectly for Composite n
What happens: For n=12, students count {1,5,7,11} correctly but might think φ(12)=5 (including 12 itself, or miscounting).
Root cause: Not using the formula consistently: φ(n) = n × ∏(1−1/p) over distinct prime factors.
Correct approach: φ(12) = 12×(1−½)×(1−⅓) = 12×⅙×2 = wait: 12×½=6, 6×⅔=4. Count manually: {1,5,7,11} = 4. ✓
Mistake 4 — Claiming Every Structure with Two Operations is a Field
What happens: Students say ℤ (integers) is a field because it has + and ×.
Root cause: A field requires every non-zero element to have a multiplicative inverse. In ℤ, 2 has no integer multiplicative inverse (2×x=1 has no integer solution).
Correct approach: Fields require division (÷) to be defined for all non-zero divisors. ℤ is a ring (and integral domain), not a field. ℚ, ℝ, ℂ, and ℤₚ (p prime) are fields.
Mistake 5 — Misidentifying the Order of an Element
What happens: In (ℤ₁₂, +), students say the order of 4 is 4 (because 4×4=16=12+4… not 0) instead of 3.
Root cause: Order is the smallest k with aᵏ = e (identity). In additive groups, aᵏ means k copies of a added: 4+4+4 = 12 ≡ 0 (mod 12) → order = 3.
Correct approach: Order of element a in (ℤₙ, +) = n / gcd(a, n). For a=4, n=12: order = 12/gcd(4,12) = 12/4 = 3. ✓
10. Frequently Asked Questions
Q1. What is Euler’s totient function φ(n) and why does it matter for CS?
φ(n) counts the positive integers up to n that are coprime to n. It is multiplicative: φ(mn)=φ(m)φ(n) when gcd(m,n)=1. The formula φ(n) = n × ∏(1−1/p) over distinct primes p dividing n makes it easy to compute. In CS, φ(n) appears in: (1) RSA cryptography — the private key exponent d satisfies ed ≡ 1 (mod φ(n)); (2) Euler’s theorem aφ(n)≡1 (mod n) for gcd(a,n)=1; (3) Primitive roots — ℤₙ* has φ(n) elements; (4) Cyclic group generators — ℤₙ has φ(n) generators.
Q2. State Fermat’s Little Theorem and how is it used in GATE problems?
Fermat’s Little Theorem: if p is prime and gcd(a,p)=1, then ap−1 ≡ 1 (mod p). In GATE problems, it is used to: (1) Reduce large exponents: ak mod p = ak mod (p−1) mod p. (2) Find modular inverses: a⁻¹ ≡ ap−2 (mod p) when p is prime. (3) Quick primality testing (Fermat test). Example: compute 21000 mod 7. Since 7 is prime: 2⁶≡1 (mod 7). 1000 = 166×6+4 → 21000 ≡ 2⁴ = 16 ≡ 2 (mod 7).
Q3. What is the difference between a group, ring, and field?
A group has one binary operation satisfying closure, associativity, identity, and inverse — integers under addition form a group. A ring has two operations (addition and multiplication) where addition forms an abelian group, multiplication is associative with identity, and multiplication distributes over addition — integers ℤ form a ring. A field is a ring where additionally every nonzero element has a multiplicative inverse — rationals ℚ, reals ℝ, and ℤₚ (p prime) are fields. The key distinction: fields have division defined for all nonzero elements. In CS, finite fields GF(2) and GF(2ⁿ) are fundamental to cryptography and error-correcting codes.
Q4. How does the Extended Euclidean Algorithm find modular inverses?
The Extended Euclidean Algorithm (EEA) finds integers x and y satisfying ax + by = gcd(a,b) (Bézout’s Identity). To find a⁻¹ mod m: set up ax + my = gcd(a,m). If gcd(a,m)=1, then ax + my = 1, meaning ax ≡ 1 (mod m), so x = a⁻¹ mod m. Example: find 17⁻¹ mod 43. Run EEA on (43,17): 43=2×17+9 → 17=1×9+8 → 9=1×8+1. Back-substitute: 1=9−8=(9)−(17−9)=2×9−17=2(43−2×17)−17=2×43−5×17. So 17×(−5)≡1 (mod 43), and −5 mod 43 = 38. Answer: 17⁻¹ ≡ 38 (mod 43). Verify: 17×38=646=15×43+1 ✓