Skip to content

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 read
  • Updated
On this page · 15 sections
  1. Prerequisites
  2. The Hook: Counting Soldiers by Remainders
  3. Divisibility and the GCD
  4. Congruences
  5. The Chinese Remainder Theorem
  6. Fermat, Euler and Wilson
  7. Euler’s Phi Function
  8. Order of an Element and Primitive Roots
  9. Memory Tricks
  10. Don’t Confuse
  11. Common Mistakes
  12. Practice
  13. Quick Revision Table
  14. Key Takeaways
  15. What’s Next

Prerequisites

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

TheoremStatement
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 \)1234567891011121314151617181920
\( \varphi(n) \)112242646410412688166188

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 \).

ModulusSmallest primitive rootNumber of primitive roots
73\( \varphi(6) = 2 \)
112\( \varphi(10) = 4 \)
132\( \varphi(12) = 4 \)
173\( \varphi(16) = 8 \)
235\( \varphi(22) = 10 \)
416\( \varphi(40) = 16 \)
92\( \varphi(6) = 2 \)
252\( \varphi(20) = 8 \)
185\( \varphi(6) = 2 \)
8, 12, 15, 16, 20none\( 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 --> F

Memory Tricks

Don’t Confuse

ThisvsThat
\( \varphi(n) \): count of units mod \( n \)\( \varphi(\varphi(n)) \): count of primitive roots (when they exist)
Fermat: exponent \( p - 1 \), prime modulusEuler: exponent \( \varphi(n) \), any modulus, needs \( \gcd(a, n) = 1 \)
CRT with coprime moduli: always solvablenon-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

  1. Compute \( \varphi(360) \).
  2. Find \( 3^{100} \bmod 7 \).
  3. How many primitive roots are there mod 13?
Answers
  1. 96. \( 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96 \).
  2. 4. \( 3^6 \equiv 1 \); \( 100 = 6 \cdot 16 + 4 \); \( 3^4 = 81 = 77 + 4 \).
  3. 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

IdeaFact
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)} \)
CRTcoprime 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