Number Theory: Congruences, CRT and Primitive Roots
CSIR NET algebra: divisibility, gcd and Bezout, linear congruences, Chinese remainder theorem, Fermat, Euler and Wilson, Euler phi and primitive roots.
- 20 min
On this page · 15 sections
Prerequisites
- Combinatorics: Counting, Pigeonhole and Derangements: inclusion-exclusion gives the formula for \( \varphi(n) \), and pigeonhole shows that powers mod \( n \) repeat.
- The Part A treatment of divisors, HCF and remainders in Counting, Probability and Number Properties.
- Groups are not needed to read this page, but the results here are the first examples on Groups, Subgroups and Homomorphisms: \( \mathbb{Z}_n \) and \( U(n) \).
The Hook: Counting Soldiers by Remainders
Divisibility and the GCD
Division algorithm. For integers \( a \) and \( b > 0 \) there are unique \( q, r \) with \( a = bq + r \) and \( 0 \le r < b \).
GCD and Bézout. \( \gcd(a, b) \) is the largest common divisor, and
$$\boxed{\gcd(a, b) = \min\{ax + by > 0 : x, y \in \mathbb{Z}\}}$$so \( \gcd(a, b) = ax + by \) for some integers \( x, y \). In particular \( \gcd(a, b) = 1 \) iff \( ax + by = 1 \) is solvable.
Euclid’s lemma. If \( p \) is prime and \( p \mid ab \), then \( p \mid a \) or \( p \mid b \). More generally, \( a \mid bc \) and \( \gcd(a, b) = 1 \) give \( a \mid c \).
Fundamental theorem of arithmetic. Every \( n > 1 \) is a product of primes, uniquely up to order. Writing \( n = p_1^{a_1}\cdots p_r^{a_r} \):
$$\tau(n) = \prod_i (a_i + 1) \ \text{(number of divisors)}, \qquad \sigma(n) = \prod_i \frac{p_i^{a_i+1} - 1}{p_i - 1} \ \text{(sum of divisors)}.$$For \( 360 = 2^3 \cdot 3^2 \cdot 5 \): \( \tau = 4 \cdot 3 \cdot 2 = 24 \), \( \sigma = 15 \cdot 13 \cdot 6 = 1170 \). Also \( \gcd(a,b)\,\mathrm{lcm}(a,b) = ab \).
Linear Diophantine equations. \( ax + by = c \) has integer solutions iff \( d = \gcd(a, b) \mid c \). If \( (x_0, y_0) \) is one solution, all solutions are \( x = x_0 + \frac{b}{d}t \), \( y = y_0 - \frac{a}{d}t \), \( t \in \mathbb{Z} \).
Congruences
\( a \equiv b \pmod m \) means \( m \mid a - b \). Congruence mod \( m \) is an equivalence relation compatible with \( + \) and \( \times \), so \( \mathbb{Z}_m = \mathbb{Z}/m\mathbb{Z} \) is a ring.
Linear congruences
$$\boxed{ax \equiv b \pmod m \text{ is solvable} \iff d = \gcd(a, m) \mid b, \text{ and then it has exactly } d \text{ solutions mod } m.}$$To solve, divide through by \( d \): \( \frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}} \) has a unique solution \( x_0 \) mod \( \frac{m}{d} \), and the solutions mod \( m \) are \( x_0, x_0 + \frac{m}{d}, \dots, x_0 + (d-1)\frac{m}{d} \).
\( a \) has a multiplicative inverse mod \( m \) iff \( \gcd(a, m) = 1 \); Bézout produces it. The units of \( \mathbb{Z}_m \) form the group \( U(m) \) of order \( \varphi(m) \).
The Chinese Remainder Theorem
Construction. Let \( M_i = \frac{M}{m_i} \) and \( y_i \equiv M_i^{-1} \pmod{m_i} \). Then \( x = \sum_i a_i M_i y_i \) works.
In an exam, successive substitution is usually faster: \( x = 7t + 2 \); mod 5 this is \( 2t + 2 \equiv 3 \), so \( t \equiv 3 \); \( x = 35s + 23 \); mod 3, \( 2s + 2 \equiv 2 \), so \( s \equiv 0 \): \( x \equiv 23 \pmod{105} \).
Non-coprime moduli. \( x \equiv a_1 \pmod{m_1} \), \( x \equiv a_2 \pmod{m_2} \) is solvable iff \( a_1 \equiv a_2 \pmod{\gcd(m_1, m_2)} \), and then the solution is unique mod \( \mathrm{lcm}(m_1, m_2) \). Example: \( x \equiv 2 \pmod 6 \), \( x \equiv 5 \pmod 9 \): \( 2 \equiv 5 \pmod 3 \), so solvable, with unique solution \( x \equiv 14 \pmod{18} \). But \( x \equiv 1 \pmod 4 \), \( x \equiv 2 \pmod 6 \) has none (parities clash).
Counting solutions with CRT. The number of solutions of a polynomial congruence \( f(x) \equiv 0 \pmod{m_1 m_2} \) (coprime moduli) is the product of the counts mod \( m_1 \) and mod \( m_2 \). Example: \( x^2 \equiv 1 \) has 2 solutions mod 3 and 2 mod 5, so 4 mod 15 (namely 1, 4, 11, 14). Mod 8 it has 4 solutions (1, 3, 5, 7), more than a prime modulus allows.
Fermat, Euler and Wilson
| Theorem | Statement |
|---|---|
| Fermat’s little theorem | \( p \) prime, \( p \nmid a \): \( a^{p-1} \equiv 1 \pmod p \); for all \( a \): \( a^p \equiv a \pmod p \) |
| Euler’s theorem | \( \gcd(a, n) = 1 \): \( a^{\varphi(n)} \equiv 1 \pmod n \) |
| Wilson’s theorem | \( n > 1 \) is prime iff \( (n-1)! \equiv -1 \pmod n \) |
| Consequence of Wilson | \( p \) prime: \( (p-2)! \equiv 1 \pmod p \) |
Euler’s theorem is Lagrange’s theorem in the group \( U(n) \). The converse of Fermat fails: \( 561 = 3 \cdot 11 \cdot 17 \) is composite, yet \( a^{560} \equiv 1 \pmod{561} \) for every \( a \) coprime to 561 (a Carmichael number).
Euler’s Phi Function
\( \varphi(n) = \#\{1 \le k \le n : \gcd(k, n) = 1\} = \lvert U(n) \rvert \).
$$\boxed{\varphi(n) = n\prod_{p \mid n}\left(1 - \frac{1}{p}\right)}, \qquad \varphi(p^k) = p^k - p^{k-1}, \qquad \varphi(mn) = \varphi(m)\varphi(n) \text{ if } \gcd(m, n) = 1.$$| \( n \) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \( \varphi(n) \) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 | 8 |
Properties CSIR NET uses
- Gauss’s identity: \( \sum_{d \mid n}\varphi(d) = n \). (Group-theoretically: \( \mathbb{Z}_n \) has exactly \( \varphi(d) \) elements of order \( d \) for each \( d \mid n \).)
- \( \varphi(n) \) is even for \( n \ge 3 \).
- \( \varphi(n) = n - 1 \) iff \( n \) is prime; \( \varphi(n) = \frac{n}{2} \) iff \( n = 2^k \), \( k \ge 1 \).
- In general \( \varphi(mn) = \varphi(m)\varphi(n)\frac{d}{\varphi(d)} \) with \( d = \gcd(m, n) \); so \( \varphi(2n) = \varphi(n) \) for odd \( n \) and \( \varphi(2n) = 2\varphi(n) \) for even \( n \).
- Inverting \( \varphi \). \( \varphi(n) = 12 \) has exactly six solutions: \( 13, 21, 26, 28, 36, 42 \). \( \varphi(n) = 8 \) has five: \( 15, 16, 20, 24, 30 \). \( \varphi(n) = 14 \) has none (14 is a “nontotient”: a solution would need a prime \( p \) with \( p - 1 \mid 14 \), i.e. \( p \in \{2, 3\} \), and no combination works).
Method for \( \varphi(n) = k \). List the primes \( p \) with \( p - 1 \mid k \); \( n \) can only be built from these primes. Then check prime powers and combinations.
Möbius function (needed for counting irreducible polynomials later): \( \mu(1) = 1 \), \( \mu(n) = (-1)^r \) if \( n \) is a product of \( r \) distinct primes, and \( \mu(n) = 0 \) if \( n \) has a square factor. Möbius inversion: if \( g(n) = \sum_{d \mid n} f(d) \) then \( f(n) = \sum_{d \mid n}\mu(d)g(n/d) \). Applied to Gauss’s identity: \( \varphi(n) = \sum_{d \mid n}\mu(d)\frac{n}{d} \).
Order of an Element and Primitive Roots
For \( \gcd(a, n) = 1 \), the order \( \mathrm{ord}_n(a) \) is the least \( k \ge 1 \) with \( a^k \equiv 1 \pmod n \).
- \( a^m \equiv 1 \iff \mathrm{ord}_n(a) \mid m \). In particular \( \mathrm{ord}_n(a) \mid \varphi(n) \).
- \( \mathrm{ord}_n(a^k) = \frac{\mathrm{ord}_n(a)}{\gcd(k, \mathrm{ord}_n(a))} \).
A primitive root mod \( n \) is an \( a \) with \( \mathrm{ord}_n(a) = \varphi(n) \), i.e. a generator of \( U(n) \).
Test for a primitive root mod a prime \( p \). \( g \) is a primitive root iff \( g^{(p-1)/q} \not\equiv 1 \pmod p \) for every prime \( q \mid p - 1 \).
| Modulus | Smallest primitive root | Number of primitive roots |
|---|---|---|
| 7 | 3 | \( \varphi(6) = 2 \) |
| 11 | 2 | \( \varphi(10) = 4 \) |
| 13 | 2 | \( \varphi(12) = 4 \) |
| 17 | 3 | \( \varphi(16) = 8 \) |
| 23 | 5 | \( \varphi(22) = 10 \) |
| 41 | 6 | \( \varphi(40) = 16 \) |
| 9 | 2 | \( \varphi(6) = 2 \) |
| 25 | 2 | \( \varphi(20) = 8 \) |
| 18 | 5 | \( \varphi(6) = 2 \) |
| 8, 12, 15, 16, 20 | none | \( U(n) \) not cyclic |
Structure of \( U(n) \). By CRT, \( U(mn) \cong U(m) \times U(n) \) for coprime \( m, n \). Further \( U(p^k) \cong \mathbb{Z}_{p^{k-1}(p-1)} \) for odd \( p \), \( U(2) \) trivial, \( U(4) \cong \mathbb{Z}_2 \), and \( U(2^k) \cong \mathbb{Z}_2 \times \mathbb{Z}_{2^{k-2}} \) for \( k \ge 3 \). So \( U(8) \cong \mathbb{Z}_2 \times \mathbb{Z}_2 \), \( U(15) \cong U(3) \times U(5) \cong \mathbb{Z}_2 \times \mathbb{Z}_4 \), \( U(16) \cong \mathbb{Z}_2 \times \mathbb{Z}_4 \).
Quadratic residues (one line each). For an odd prime \( p \) and \( p \nmid a \), Euler’s criterion says \( a^{(p-1)/2} \equiv \pm 1 \pmod p \), with \( +1 \) exactly when \( a \) is a square mod \( p \). There are \( \frac{p-1}{2} \) non-zero squares mod \( p \), and \( -1 \) is a square mod \( p \) iff \( p \equiv 1 \pmod 4 \). A primitive root is never a square mod an odd prime.
graph LR
A["Compute a^k mod n"] --> B{gcd of a and n is 1?}
B -->|yes| C["Reduce k mod phi(n), or mod ord(a)"]
B -->|no| D["Split n by CRT into prime powers"]
D --> E["Work mod each prime power, then recombine"]
C --> F[Answer]
E --> FMemory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| \( \varphi(n) \): count of units mod \( n \) | \( \varphi(\varphi(n)) \): count of primitive roots (when they exist) | |
| Fermat: exponent \( p - 1 \), prime modulus | Euler: exponent \( \varphi(n) \), any modulus, needs \( \gcd(a, n) = 1 \) | |
| CRT with coprime moduli: always solvable | non-coprime moduli: solvable only if residues agree mod the gcd | |
| \( ax \equiv b \pmod m \) has \( \gcd(a, m) \) solutions | \( ax \equiv b \) with \( \gcd(a, m) \nmid b \): none | |
| \( U(2p^k) \) cyclic | \( U(4p^k) \), \( U(pq) \) not cyclic |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- Compute \( \varphi(360) \).
- Find \( 3^{100} \bmod 7 \).
- How many primitive roots are there mod 13?
Answers
- 96. \( 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96 \).
- 4. \( 3^6 \equiv 1 \); \( 100 = 6 \cdot 16 + 4 \); \( 3^4 = 81 = 77 + 4 \).
- 4. \( \varphi(\varphi(13)) = \varphi(12) = 4 \).
Level 2: Part B Style
Practice Q1. The least positive integer \( x \) with \( x \equiv 1 \pmod 4 \), \( x \equiv 2 \pmod 5 \), \( x \equiv 3 \pmod 7 \) is:
(a) 17 (b) 37 (c) 57 (d) 157
Answer: (a)
\( x = 7t + 3 \). Mod 5: \( 2t + 3 \equiv 2 \), so \( 2t \equiv 4 \), \( t \equiv 2 \): \( x = 35s + 17 \). Mod 4: \( 3s + 1 \equiv 1 \), so \( s \equiv 0 \). Hence \( x \equiv 17 \pmod{140} \). Check: \( 17 = 16 + 1 = 15 + 2 = 14 + 3 \).
Practice Q2. The remainder when \( 2^{2026} \) is divided by 13 is:
(a) 1 (b) 4 (c) 10 (d) 12
Answer: (c)
\( 2^{12} \equiv 1 \pmod{13} \) and \( 2026 \equiv 10 \pmod{12} \), so the answer is \( 2^{10} = 1024 \equiv 10 \).
Practice Q3. For which of the following \( n \) does a primitive root mod \( n \) exist?
(a) 12 (b) 15 (c) 18 (d) 20
Answer: (c)
\( 18 = 2 \cdot 3^2 \) is of the form \( 2p^k \). The others are \( 4 \cdot 3 \), \( 3 \cdot 5 \), \( 4 \cdot 5 \), none of the allowed forms. (5 is a primitive root mod 18: its powers are 5, 7, 17, 13, 11, 1.)
Practice Q4. The number of solutions of \( 12x \equiv 18 \pmod{30} \) in \( \{0, 1, \dots, 29\} \) is:
(a) 0 (b) 1 (c) 3 (d) 6
Answer: (d)
\( \gcd(12, 30) = 6 \) and \( 6 \mid 18 \), so there are 6 solutions: \( 4, 9, 14, 19, 24, 29 \).
Level 3: Part C Style
Practice Q5. Which of the following are true?
(a) \( U(25) \) is cyclic. (b) \( U(16) \) is cyclic. (c) There are exactly 6 primitive roots mod 27. (d) \( U(15) \cong \mathbb{Z}_8 \).
Answer: (a) and (c)
- (a) True. \( 25 = 5^2 \) is an odd prime power. (2 is a primitive root mod 25.)
- (b) False. \( U(16) \cong \mathbb{Z}_2 \times \mathbb{Z}_4 \); every element has order at most 4 \( < 8 \).
- (c) True. \( 27 = 3^3 \) has primitive roots, and their number is \( \varphi(\varphi(27)) = \varphi(18) = 6 \).
- (d) False. \( U(15) \cong U(3) \times U(5) \cong \mathbb{Z}_2 \times \mathbb{Z}_4 \): no element of order 8 (all of 1, 2, 4, 7, 8, 11, 13, 14 have order 1, 2 or 4).
Practice Q6. Let \( p = 29 \). Which of the following are true?
(a) \( 28! \equiv -1 \pmod{29} \). (b) \( 27! \equiv -1 \pmod{29} \). (c) \( 2^{28} \equiv 1 \pmod{29} \). (d) 2 is a primitive root mod 29.
Answer: (a), (c) and (d)
- (a) True. Wilson’s theorem.
- (b) False. \( 28! = 28 \cdot 27! \equiv -27! \pmod{29} \), and \( 28! \equiv -1 \), so \( 27! \equiv 1 \).
- (c) True. Fermat.
- (d) True. \( 28 = 2^2 \cdot 7 \), so check \( 2^{14} \) and \( 2^4 \). \( 2^4 = 16 \not\equiv 1 \). \( 2^7 = 128 = 4 \cdot 29 + 12 \equiv 12 \), so \( 2^{14} \equiv 144 = 4 \cdot 29 + 28 \equiv -1 \not\equiv 1 \). Hence the order of 2 is 28.
Practice Q7. Which of the following are true?
(a) The equation \( \varphi(n) = 12 \) has exactly six solutions in positive integers. (b) The equation \( \varphi(n) = 14 \) has no solution. (c) \( \varphi(n) = \frac{n}{2} \) if and only if \( n \) is a power of 2 with exponent at least 1. (d) \( \varphi(mn) = \varphi(m)\varphi(n) \) for all positive integers \( m, n \).
Answer: (a), (b) and (c)
- (a) True. Primes with \( p - 1 \mid 12 \): 2, 3, 5, 7, 13. Building \( n \) from them gives exactly \( 13, 21, 26, 28, 36, 42 \).
- (b) True. Primes with \( p - 1 \mid 14 \): only 2 and 3 (8 and 15 are not prime). Then \( n = 2^a3^b \) and \( \varphi(n) \) has the form \( 2^{a-1} \), \( 2 \cdot 3^{b-1} \) or \( 2^a 3^{b-1} \); none equals 14, because of the factor 7.
- (c) True. \( \frac{\varphi(n)}{n} = \prod_{p \mid n}(1 - \frac{1}{p}) = \frac{1}{2} \) forces the only prime factor to be 2.
- (d) False. \( \varphi(4) = 2 \ne 1 = \varphi(2)^2 \).
Quick Revision Table
| Idea | Fact |
|---|---|
| Bézout | \( \gcd(a,b) = ax + by \); smallest positive such combination |
| \( ax \equiv b \pmod m \) | solvable iff \( d = \gcd(a,m) \mid b \); then \( d \) solutions |
| Cancellation | \( ac \equiv bc \pmod m \Rightarrow a \equiv b \pmod{m/\gcd(c,m)} \) |
| CRT | coprime moduli: unique solution mod product; else need agreement mod gcd |
| Fermat / Euler | \( a^{p-1} \equiv 1 \); \( a^{\varphi(n)} \equiv 1 \) when \( \gcd(a,n)=1 \) |
| Wilson | \( (p-1)! \equiv -1 \), \( (p-2)! \equiv 1 \pmod p \) |
| \( \varphi \) | \( n\prod(1 - 1/p) \); multiplicative; \( \sum_{d \mid n}\varphi(d) = n \) |
| Primitive roots exist | \( n = 1, 2, 4, p^k, 2p^k \) |
| Number of primitive roots | \( \varphi(\varphi(n)) \) |
| \( U(2^k) \), \( k \ge 3 \) | \( \mathbb{Z}_2 \times \mathbb{Z}_{2^{k-2}} \) |
Key Takeaways
What’s Next
- Groups, Subgroups and Homomorphisms: \( \mathbb{Z}_n \), \( U(n) \) and cyclic groups in the language of group theory.
- Rings, Ideals and Polynomial Rings: \( \mathbb{Z}_n \) as a ring, its ideals, units and nilpotents, and CRT as a ring isomorphism.
- Fields, Extensions and Galois Theory: the multiplicative group of every finite field is cyclic, the generalisation of primitive roots.
- Algebra: Quick Revision.