← Back to CSIR NET
CSIR NET > Number Theory

Number Theory

The queen of mathematics — from the ancient Euclidean algorithm and prime factorisation to quadratic reciprocity, arithmetic functions, and modern cryptographic applications.

Divisibility & Primes Congruences Quadratic Residues Arithmetic Functions Diophantine Equations Applications
0 / 6 units completed0%
01 Divisibility & Primes

The fundamental structures of number theory rest on divisibility and prime numbers. The Euclidean algorithm and the Fundamental Theorem of Arithmetic form the bedrock of the subject.

◆ Euclidean Algorithm
Definition — Divisibility For integers $a, b$ with $b \ne 0$, we say $b \mid a$ ($b$ divides $a$) if there exists $k \in \mathbb{Z}$ such that $a = kb$. The greatest common divisor $\gcd(a,b)$ is the largest positive integer dividing both $a$ and $b$.
Theorem — Division Algorithm For any integers $a$ and $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$ with $0 \le r < b$.
Theorem — Euclidean Algorithm & Bézout's Identity The Euclidean algorithm computes $\gcd(a,b)$ by iterated division: $\gcd(a,b) = \gcd(b, a \bmod b)$. Moreover, there exist integers $x, y$ such that $\gcd(a,b) = ax + by$ (Bézout's identity). The extended Euclidean algorithm computes $x$ and $y$.
★ Example
Find $\gcd(252, 105)$ and express it as a linear combination of $252$ and $105$.
Solution: $252 = 2 \cdot 105 + 42$, $105 = 2 \cdot 42 + 21$, $42 = 2 \cdot 21 + 0$. So $\gcd(252, 105) = 21$. Back-substituting: $21 = 105 - 2(42) = 105 - 2(252 - 2 \cdot 105) = 5 \cdot 105 - 2 \cdot 252$. Thus $21 = 252(-2) + 105(5)$.
◆ Fundamental Theorem of Arithmetic
Theorem — Fundamental Theorem of Arithmetic Every integer $n > 1$ can be written uniquely (up to order) as a product of primes: $$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$ where $p_1 < p_2 < \cdots < p_k$ are primes and $a_i \ge 1$.
Theorem — Infinitude of Primes (Euclid) There are infinitely many primes. Proof: Suppose $p_1, \ldots, p_n$ are all primes. Consider $N = p_1 p_2 \cdots p_n + 1$. Then $N$ is not divisible by any $p_i$ (remainder $1$), so $N$ has a prime factor not in the list — contradiction.
02 Congruences

Modular arithmetic provides a powerful algebraic framework for studying divisibility. The Chinese Remainder Theorem, Fermat's little theorem, and Euler's theorem are indispensable tools.

◆ Linear Congruences & CRT
Definition — Congruence We write $a \equiv b \pmod{m}$ if $m \mid (a - b)$. The congruence $ax \equiv b \pmod{m}$ has a solution iff $\gcd(a, m) \mid b$. If solvable, there are exactly $d = \gcd(a, m)$ incongruent solutions modulo $m$.
Theorem — Chinese Remainder Theorem If $m_1, m_2, \ldots, m_k$ are pairwise coprime, then the system $$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$$ has a unique solution modulo $M = m_1 m_2 \cdots m_k$. Explicitly: $x = \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ where $M_i = M/m_i$ and $y_i \equiv M_i^{-1} \pmod{m_i}$.
★ Example
Solve: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.
Solution: $M = 105$. $M_1 = 35$, $M_2 = 21$, $M_3 = 15$. $35y_1 \equiv 1 \pmod{3}$: $2y_1 \equiv 1$, $y_1 = 2$. $21y_2 \equiv 1 \pmod{5}$: $y_2 \equiv 1$, $y_2 = 1$. $15y_3 \equiv 1 \pmod{7}$: $y_3 \equiv 1$, $y_3 = 1$. $x = 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$.
◆ Fermat's Little Theorem & Euler's Theorem
Theorem — Fermat's Little Theorem If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod{p}$. Equivalently, $a^p \equiv a \pmod{p}$ for all $a$.
Theorem — Euler's Theorem If $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is Euler's totient function.
★ Example
Find the last two digits of $3^{100}$ (i.e., compute $3^{100} \pmod{100}$).
Solution: $\phi(100) = 100 \cdot (1 - 1/2)(1 - 1/5) = 40$. Since $\gcd(3, 100) = 1$, Euler's theorem gives $3^{40} \equiv 1 \pmod{100}$. Then $3^{100} = (3^{40})^2 \cdot 3^{20} \equiv 3^{20} \pmod{100}$. Now $3^{10} = 59049 \equiv 49 \pmod{100}$. $3^{20} = (3^{10})^2 \equiv 49^2 = 2401 \equiv 1 \pmod{100}$. So the last two digits of $3^{100}$ are $\mathbf{01}$.
03 Quadratic Residues

Quadratic residues reveal the structure of perfect squares modulo primes. The Legendre symbol and the law of quadratic reciprocity are central to this theory.

◆ Legendre Symbol & Quadratic Reciprocity
Definition — Quadratic Residue An integer $a$ with $\gcd(a, p) = 1$ is a quadratic residue mod $p$ if $x^2 \equiv a \pmod{p}$ has a solution; otherwise, $a$ is a quadratic non-residue.
Definition — Legendre Symbol For odd prime $p$ and $\gcd(a, p) = 1$: $$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a QR mod } p \\ -1 & \text{if } a \text{ is a QNR mod } p \end{cases}$$ Euler's criterion: $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$.
Theorem — Law of Quadratic Reciprocity For distinct odd primes $p$ and $q$: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$ Supplements: $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$ and $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$.
★ Example
Determine whether $3$ is a quadratic residue modulo $23$.
Solution: By Euler's criterion: $\left(\frac{3}{23}\right) \equiv 3^{11} \pmod{23}$. Compute: $3^2 = 9$, $3^4 = 81 \equiv 12$, $3^8 \equiv 144 \equiv 6$, $3^{11} = 3^8 \cdot 3^2 \cdot 3 = 6 \cdot 9 \cdot 3 = 162 \equiv 162 - 7(23) = 162 - 161 = 1$. So $\left(\frac{3}{23}\right) = 1$; $3$ is a QR mod $23$. Indeed $7^2 = 49 \equiv 3 \pmod{23}$.
04 Arithmetic Functions

Arithmetic (number-theoretic) functions encode information about divisibility, prime decomposition, and structural properties of integers. Möbius inversion and Dirichlet convolution give them an algebraic structure.

◆ Euler's Totient & Möbius Function
Definition — Euler's Totient Function $\phi(n)$ counts the number of integers in $\{1, 2, \ldots, n\}$ coprime to $n$. For $n = p_1^{a_1} \cdots p_k^{a_k}$: $$\phi(n) = n\prod_{p \mid n}\left(1 - \frac{1}{p}\right) = n \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdots \frac{p_k - 1}{p_k}.$$ Key identity: $\sum_{d \mid n} \phi(d) = n$.
Definition — Möbius Function $$\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n = p_1 p_2 \cdots p_k \text{ (square-free)} \\ 0 & \text{if } p^2 \mid n \text{ for some prime } p \end{cases}$$ Key identity: $\sum_{d \mid n} \mu(d) = [n = 1]$ (equals $1$ if $n = 1$, else $0$).
◆ Dirichlet Convolution & Möbius Inversion
Definition — Dirichlet Convolution For arithmetic functions $f, g$, the Dirichlet convolution is: $$(f * g)(n) = \sum_{d \mid n} f(d)\,g(n/d).$$ This operation is associative and commutative, with identity $\varepsilon(n) = [n=1]$.
Theorem — Möbius Inversion Formula If $F(n) = \sum_{d \mid n} f(d)$, then $f(n) = \sum_{d \mid n} \mu(d)\,F(n/d) = \sum_{d \mid n} \mu(n/d)\,F(d)$. In convolution notation: $F = f * \mathbf{1}$ implies $f = F * \mu$.
★ Example
Use Möbius inversion to derive $\phi(n)$ from $\sum_{d \mid n} \phi(d) = n$.
Solution: Let $F(n) = n = \sum_{d \mid n} \phi(d)$, so $F = \phi * \mathbf{1}$. By Möbius inversion: $\phi(n) = \sum_{d \mid n} \mu(d) \cdot F(n/d) = \sum_{d \mid n} \mu(d) \cdot \frac{n}{d} = n \sum_{d \mid n} \frac{\mu(d)}{d}$. For $n = p^a$: $\phi(p^a) = p^a(1 - 1/p) = p^a - p^{a-1}$. For general $n$, multiplicativity gives $\phi(n) = n\prod_{p \mid n}(1 - 1/p)$.
05 Diophantine Equations

Diophantine equations seek integer (or rational) solutions to polynomial equations. From linear equations to Pythagorean triples and Pell's equation, these problems lie at the heart of number theory.

◆ Linear Diophantine Equations
Theorem The equation $ax + by = c$ has integer solutions if and only if $d = \gcd(a,b) \mid c$. If $(x_0, y_0)$ is one solution, the general solution is: $$x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t, \qquad t \in \mathbb{Z}.$$
◆ Pythagorean Triples & Pell's Equation
Theorem — Pythagorean Triples All primitive Pythagorean triples $(a, b, c)$ with $a$ odd, $b$ even, $c > 0$ and $\gcd(a,b) = 1$ are given by: $$a = m^2 - n^2, \quad b = 2mn, \quad c = m^2 + n^2$$ where $m > n > 0$, $\gcd(m,n) = 1$, and $m - n$ is odd.
Theorem — Pell's Equation For a non-square positive integer $d$, the equation $x^2 - dy^2 = 1$ has infinitely many positive integer solutions. If $(x_1, y_1)$ is the fundamental (smallest positive) solution, all solutions are given by $x_n + y_n\sqrt{d} = (x_1 + y_1\sqrt{d})^n$ for $n = 1, 2, 3, \ldots$.
★ Example
Find all positive integer solutions of $x^2 - 2y^2 = 1$ with $x, y \le 100$.
Solution: The fundamental solution is $(x_1, y_1) = (3, 2)$ since $9 - 8 = 1$. Subsequent solutions from $(x_n + y_n\sqrt{2}) = (3 + 2\sqrt{2})^n$: $(x_2, y_2) = (17, 12)$ (check: $289 - 288 = 1$), $(x_3, y_3) = (99, 70)$ (check: $9801 - 9800 = 1$). Next: $(x_4, y_4) = (577, 408)$ exceeds $100$. Solutions: $(3,2)$, $(17,12)$, $(99,70)$.
06 Applications

Number theory has found spectacular applications in cryptography and computational mathematics. RSA encryption and primality testing are landmark achievements.

◆ RSA Cryptography
RSA Algorithm Key generation: Choose large primes $p, q$. Let $n = pq$ and $\phi(n) = (p-1)(q-1)$. Choose $e$ with $\gcd(e, \phi(n)) = 1$ and compute $d \equiv e^{-1} \pmod{\phi(n)}$.
Public key: $(n, e)$. Private key: $d$.
Encryption: $c \equiv m^e \pmod{n}$.
Decryption: $m \equiv c^d \pmod{n}$.
Correctness follows from Euler's theorem: $m^{ed} = m^{1 + k\phi(n)} \equiv m \pmod{n}$.
★ Example
In a toy RSA system with $p = 11$, $q = 13$, $e = 7$, encrypt $m = 9$ and then decrypt.
Solution: $n = 143$, $\phi(n) = 10 \times 12 = 120$. $\gcd(7, 120) = 1$. Find $d$: $7d \equiv 1 \pmod{120}$. $7 \times 103 = 721 = 6 \times 120 + 1$, so $d = 103$. Encryption: $c = 9^7 \pmod{143}$. $9^2 = 81$, $9^4 \equiv 81^2 = 6561 \equiv 6561 - 45 \times 143 = 6561 - 6435 = 126$, $9^7 = 9^4 \cdot 9^2 \cdot 9 \equiv 126 \times 81 \times 9$. $126 \times 81 = 10206 \equiv 10206 - 71 \times 143 = 10206 - 10153 = 53$. $53 \times 9 = 477 \equiv 477 - 3 \times 143 = 48$. So $c = 48$. Decryption: $48^{103} \pmod{143}$. By construction, $48^{103} \equiv 9 \pmod{143}$.
◆ Primality Testing
Fermat Primality Test To test if $n$ is prime: pick random $a$ with $1 < a < n$. If $a^{n-1} \not\equiv 1 \pmod{n}$, then $n$ is composite. If $a^{n-1} \equiv 1$, $n$ is probably prime. Carmichael numbers (e.g., $561 = 3 \times 11 \times 17$) fool this test for all $a$ coprime to $n$.
Miller-Rabin Test Write $n - 1 = 2^s \cdot d$ with $d$ odd. For a random base $a$: compute $a^d \pmod{n}$. If $a^d \equiv 1$ or $a^{2^r d} \equiv -1$ for some $0 \le r < s$, then $n$ passes. Otherwise $n$ is composite. Repeating with multiple bases gives a probabilistic primality certificate with error probability at most $4^{-k}$ for $k$ trials.
★ Key Takeaways
✎ Practice Problems
Problem 1
Find all solutions to $17x \equiv 5 \pmod{23}$.
Show Solution ▼
$\gcd(17, 23) = 1$, so a unique solution exists mod $23$. Find $17^{-1} \pmod{23}$: by extended Euclidean: $23 = 1 \times 17 + 6$, $17 = 2 \times 6 + 5$, $6 = 1 \times 5 + 1$. Back-substitute: $1 = 6 - 5 = 6 - (17 - 2 \times 6) = 3 \times 6 - 17 = 3(23 - 17) - 17 = 3 \times 23 - 4 \times 17$. So $17^{-1} \equiv -4 \equiv 19 \pmod{23}$. Then $x \equiv 19 \times 5 = 95 \equiv 95 - 4 \times 23 = 3 \pmod{23}$.
Problem 2
Compute $\phi(360)$ and determine how many integers from $1$ to $360$ are coprime to $360$.
Show Solution ▼
$360 = 2^3 \times 3^2 \times 5$. $\phi(360) = 360(1 - 1/2)(1 - 1/3)(1 - 1/5) = 360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 360 \times \frac{8}{30} = 96$. There are $96$ integers from $1$ to $360$ coprime to $360$.
Problem 3
Using quadratic reciprocity, determine $\left(\frac{5}{41}\right)$.
Show Solution ▼
Both $5$ and $41$ are odd primes. $\frac{5-1}{2} \cdot \frac{41-1}{2} = 2 \times 20 = 40$ (even). So $\left(\frac{5}{41}\right) = \left(\frac{41}{5}\right) = \left(\frac{1}{5}\right) = 1$ (since $41 \equiv 1 \pmod{5}$). Therefore $5$ is a quadratic residue mod $41$. Verification: $28^2 = 784 = 19 \times 41 + 5$, so $28^2 \equiv 5 \pmod{41}$.
Problem 4
Find all primitive Pythagorean triples with hypotenuse $c \le 50$.
Show Solution ▼
Using $a = m^2 - n^2$, $b = 2mn$, $c = m^2 + n^2$ with $m > n > 0$, $\gcd(m,n) = 1$, $m - n$ odd: $(m,n) = (2,1)$: $(3,4,5)$. $(3,2)$: $(5,12,13)$. $(4,1)$: $(15,8,17)$. $(4,3)$: $(7,24,25)$. $(5,2)$: $(21,20,29)$. $(5,4)$: $(9,40,41)$. $(6,1)$: $(35,12,37)$. $(6,5)$: $(11,60,61)$, $c = 61 > 50$. $(7,2)$: $c = 53 > 50$. Triples with $c \le 50$: $(3,4,5)$, $(5,12,13)$, $(8,15,17)$, $(7,24,25)$, $(20,21,29)$, $(12,35,37)$, $(9,40,41)$.
Problem 5
Prove that if $p$ is an odd prime, then $\sum_{a=1}^{p-1} \left(\frac{a}{p}\right) = 0$.
Show Solution ▼
Among $\{1, 2, \ldots, p-1\}$, exactly $(p-1)/2$ are quadratic residues and $(p-1)/2$ are non-residues. This is because the map $a \mapsto a^2 \pmod{p}$ on $(\mathbb{Z}/p\mathbb{Z})^*$ is exactly $2$-to-$1$ (as $x^2 = (-x)^2$ and these are the only collisions). So $\sum \left(\frac{a}{p}\right) = \frac{p-1}{2}(1) + \frac{p-1}{2}(-1) = 0$.
🎯 Interactive Quiz
1. The linear congruence $6x \equiv 4 \pmod{10}$ has:
A No solution
B Exactly 1 solution mod 10
C Exactly 2 solutions mod 10
D Exactly 5 solutions mod 10
2. By Fermat's little theorem, $2^{10} \pmod{11}$ equals:
A $1$
B $2$
C $10$
D $0$
3. The Möbius function $\mu(12)$ equals:
A $1$
B $-1$
C $0$
D $2$
4. The fundamental solution to $x^2 - 3y^2 = 1$ is:
A $(1, 1)$
B $(2, 1)$
C $(7, 4)$
D $(3, 2)$
5. In RSA, security relies on the difficulty of:
A Computing $\gcd$ of two numbers
B Factoring large integers
C Computing modular exponentiation
D Computing Euler's totient