Number theory basics

In short

Number theory is the study of the integers — divisibility, primes, factorisation and arithmetic "modulo n" — and it is the one branch of pure mathematics that runs modern computing. A B.Sc syllabus (UGC CBCS "Number Theory" / "Discrete Mathematics" papers) covers the division algorithm, GCD by Euclid's algorithm, unique factorisation, congruences, the classical theorems of Fermat, Euler and Wilson, the Chinese Remainder Theorem and multiplicative functions. It is examined in GATE (CS and MA), NET/JAM/GATE-MA, CSIR-NET, ISI/CMI entrance and bank/PSU aptitude papers, and appears directly in placement coding rounds at TCS, Infosys, Wipro, Amazon, Microsoft and payment firms. On the job it underlies RSA and Diffie-Hellman in UPI, Aadhaar e-KYC and digital-signature systems, hashing, checksum digits in Aadhaar and ISBN, and competitive-programming problem sets.

Explained

Divisibility and the division algorithm

• Divides: for integers a, b with a ≠ 0, "a | b" means b = ac for some integer c. Then a is a divisor (factor), b a multiple.
• Properties: a|b and b|c ⟹ a|c (transitive); a|b and a|c ⟹ a|(bx + cy) for all integers x, y (linearity — the key tool in GCD proofs); a|b and b|a ⟹ a = ±b.
• Division algorithm: for integers a and b > 0 there exist *unique* q, r with a = bq + r and 0 ≤ r < b. r is the remainder, q the quotient. Holds for negative a too: −17 = 5(−4) + 3, so r = 3, not −2.
• Divisibility tests (base 10, each a congruence in disguise): by 2, 5, 10 — last digit; by 4 — last two digits; by 8 — last three; by 3 and 9 — digit sum (since 10 ≡ 1 mod 9); by 11 — alternating digit sum (10 ≡ −1 mod 11); by 7 — double the last digit and subtract from the rest; by 6, 12, 15 — test the coprime factors separately.
• Greatest integer / floor: the count of multiples of d in 1…n is ⌊n/d⌋ — the basis of counting and trailing-zero problems.

GCD, LCM and the Euclidean algorithm

• gcd(a, b) = largest d with d|a and d|b; lcm(a, b) = smallest positive common multiple. a and b are coprime (relatively prime) if gcd = 1.
• Euclidean algorithm: gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0; the last non-zero remainder is the GCD. It needs O(log min(a,b)) divisions — worst case is consecutive Fibonacci numbers (Lamé's theorem).
• Bézout's identity: gcd(a, b) = ax + by for some integers x, y, found by the extended Euclidean algorithm (back-substitution of the division steps). x, y are not unique: (x + kb/g, y − ka/g) also work.
• Linear Diophantine equation ax + by = c has a solution iff gcd(a, b) | c; then all solutions are x = x₀ + (b/g)t, y = y₀ − (a/g)t, t ∈ ℤ.
• Modular inverse: a has an inverse mod n iff gcd(a, n) = 1; find it from ax + ny = 1, giving a⁻¹ ≡ x (mod n).
• Useful identities: gcd(a,b)·lcm(a,b) = |ab| (two numbers only — it fails for three); gcd(ka, kb) = k·gcd(a,b); gcd(a, b) = gcd(a ± b, b).

Primes and the fundamental theorem of arithmetic

• Prime: p > 1 with no divisors other than 1 and p. 1 is neither prime nor composite; 2 is the only even prime.
• Fundamental theorem of arithmetic (FTA): every integer n > 1 is a product of primes, unique up to order: n = p₁^a₁ p₂^a₂ … p_k^a_k (canonical form).
• Euclid's lemma: if p is prime and p | ab then p | a or p | b — the engine of FTA's uniqueness.
• Euclid's theorem: there are infinitely many primes (assume finitely many, form N = p₁p₂…p_k + 1; it has a prime factor outside the list).
• Primality testing: trial division by primes up to √n suffices. Sieve of Eratosthenes lists all primes ≤ n in O(n log log n) time — start crossing out from p² for each p ≤ √n.
• Twin primes (p, p+2), Mersenne primes (2^p − 1), Fermat numbers (2²ⁿ + 1), perfect numbers (σ(n) = 2n; even ones are 2^p−1(2^p − 1) with 2^p − 1 prime — Euclid–Euler).
• Prime number theorem (statement only at B.Sc level): π(n) ~ n/ln n, so primes thin out but never stop. Goldbach (every even n > 2 is a sum of two primes) and the twin-prime conjecture remain unproved.
• From the canonical form: number of divisors d(n) = Π(aᵢ + 1); sum of divisors σ(n) = Π (p^aᵢ+1 − 1)/(pᵢ − 1); product of divisors = n^d(n)/2.

Congruences and modular arithmetic

• Definition: a ≡ b (mod n) iff n | (a − b). This is an equivalence relation; it partitions ℤ into n residue classes 0, 1, …, n−1 (ℤ_n).
• Arithmetic: congruences add, subtract and multiply freely; a ≡ b ⟹ a^k ≡ b^k. Division does not work directly: ca ≡ cb (mod n) ⟹ a ≡ b (mod n/gcd(c,n)).
• Linear congruence ax ≡ b (mod n) has a solution iff g = gcd(a, n) divides b, and then exactly g solutions mod n.
• Chinese Remainder Theorem (CRT): if n₁, n₂, …, n_k are pairwise coprime, the system x ≡ aᵢ (mod nᵢ) has a unique solution modulo N = n₁n₂…n_k. Construct it as x = Σ aᵢ Mᵢ yᵢ where Mᵢ = N/nᵢ and yᵢ ≡ Mᵢ⁻¹ (mod nᵢ).
• Fermat's little theorem: p prime, gcd(a, p) = 1 ⟹ a^p−1 ≡ 1 (mod p); equivalently a^p ≡ a (mod p) for all a. Converse is false — Carmichael numbers (561, 1105, 1729) pass for every coprime base.
• Euler's theorem: gcd(a, n) = 1 ⟹ a^φ(n) ≡ 1 (mod n). Used to reduce huge exponents mod n.
• Wilson's theorem: p is prime ⟺ (p − 1)! ≡ −1 (mod p).
• Order and primitive roots: ord_n(a) = least k with a^k ≡ 1 (mod n); ord_n(a) | φ(n). If ord_n(a) = φ(n), a is a primitive root mod n — these exist only for n = 1, 2, 4, p^k, 2p^k (p odd prime).
• Quadratic residues: a is a QR mod p if x² ≡ a (mod p) is solvable. Euler's criterion: a^(p−1)/2 ≡ +1 for a QR, −1 for a non-residue. The Legendre symbol (a/p) and quadratic reciprocity (p/q)(q/p) = (−1)^{(p−1)/2·(q−1)/2} appear in honours papers.

Arithmetic (number-theoretic) functions

• Multiplicative function: f(mn) = f(m)f(n) whenever gcd(m, n) = 1 — so f is fixed by its values on prime powers.
• Euler's totient φ(n): count of integers in 1…n coprime to n. φ(p) = p − 1, φ(p^k) = p^k − p^k−1, φ multiplicative, and Gauss's identity Σ_{d|n} φ(d) = n.
• d(n) (or τ), σ(n) — divisor count and sum; both multiplicative. n is perfect / deficient / abundant as σ(n) = / < / > 2n.
• Möbius function μ(n): 1 if n = 1, (−1)^k if n is a product of k distinct primes, 0 if any prime repeats (not squarefree). Σ_{d|n} μ(d) = 1 for n = 1, else 0.
• Möbius inversion: F(n) = Σ_{d|n} f(d) ⟺ f(n) = Σ_{d|n} μ(d) F(n/d).
• Greatest integer function results: exponent of p in n! is Σ_{i≥1} ⌊n/pⁱ⌋ (Legendre's formula) — used for trailing zeros of n!.

Applications: cryptography and coding

• Fast modular exponentiation (square-and-multiply): compute a^b mod n in O(log b) multiplications — the standard interview coding question.
• RSA: choose primes p, q; n = pq; φ(n) = (p−1)(q−1); pick e coprime to φ(n); d ≡ e⁻¹ (mod φ(n)). Encrypt c = m^e mod n, decrypt m = c^d mod n — correctness follows from Euler's theorem. Security rests on the hardness of factoring n.
• Diffie–Hellman: shared key g^ab mod p; security rests on the discrete logarithm problem. ECC (used in Aadhaar/UIDAI and TLS) is the elliptic-curve analogue.
• Checksums: the Verhoeff algorithm supplies the 12th digit of Aadhaar; ISBN-10 uses a mod-11 weighted check digit, ISBN-13/EAN a mod-10 one; the GSTIN's 15th character is a check digit computed over the earlier 14.
• Hashing and data structures: hash tables take a key mod a prime table size; CRT speeds RSA decryption; linear congruential generators (x_{n+1} = (ax_n + c) mod m) produce pseudo-random numbers.
• Indian standards note: cryptographic algorithm choices for Indian e-governance are set by CCA (Controller of Certifying Authorities) guidelines under the Information Technology Act, 2000 — current practice is RSA 2048-bit or above and SHA-256; the specific key-length mandate is revised periodically, so check the CCA's latest interoperability guideline rather than quoting a fixed figure.

Key points

• Division algorithm — a = bq + r with 0 ≤ r < b, unique; the remainder is always non-negative.
• Linearity of divisibility — d|a and d|b ⟹ d|(ax + by); almost every GCD proof uses it.
• Euclidean algorithm — gcd(a,b) = gcd(b, a mod b); O(log n), worst case consecutive Fibonacci numbers.
• Bézout — gcd(a,b) is the smallest positive integer expressible as ax + by.
• Diophantine solvability — ax + by = c solvable ⟺ gcd(a,b) | c; infinitely many solutions then.
• FTA — unique prime factorisation; everything about divisors, GCD and LCM follows from exponents.
• Divisor formulas — d(n) = Π(aᵢ+1), σ(n) = Π(p^aᵢ+1−1)/(p−1), gcd takes min exponents, lcm takes max.
• gcd × lcm = ab — for exactly two numbers; not valid for three or more.
• Congruence — a ≡ b (mod n) ⟺ n | (a−b); respects +, −, × but not ÷.
• Modular inverse exists ⟺ gcd(a, n) = 1; ℤ_n is a field exactly when n is prime.
• Fermat's little theorem — a^p−1 ≡ 1 (mod p) for prime p, p ∤ a; fails as a primality test on Carmichael numbers.
• Euler's theorem — a^φ(n) ≡ 1 (mod n) when gcd(a,n) = 1; the tool for reducing giant exponents.
• φ(n) — multiplicative, φ(p^k) = p^k − p^k−1, Σ_{d|n} φ(d) = n.
• Wilson's theorem — (p−1)! ≡ −1 (mod p) characterises primes (too slow to be a practical test).
• CRT — pairwise coprime moduli give a unique solution mod the product; splits one hard modulus into easy ones.
• Order divides φ(n); a primitive root exists only for n = 1, 2, 4, p^k, 2p^k.
• Sieve of Eratosthenes — all primes up to n in O(n log log n); trial division only needs factors up to √n.
• RSA — public (e, n), private d with ed ≡ 1 (mod φ(n)); breaks if n can be factored.

Formulas and examples

Example 1 — Extended Euclid and a modular inverse. Find gcd(1071, 462) and express it as a combination; then find 11⁻¹ mod 26.

• 1071 = 2(462) + 147; 462 = 3(147) + 21; 147 = 7(21) + 0 → gcd = 21.
• Back-substitute: 21 = 462 − 3(147) = 462 − 3(1071 − 2·462) = 7(462) − 3(1071). Check: 3234 − 3213 = 21. ✓
• For 11 mod 26: 26 = 2(11) + 4; 11 = 2(4) + 3; 4 = 1(3) + 1. So 1 = 4 − 3 = 4 − (11 − 2·4) = 3(4) − 11 = 3(26 − 2·11) − 11 = 3(26) − 7(11). Hence 11⁻¹ ≡ −7 ≡ 19 (mod 26). Check: 11 × 19 = 209 = 8(26) + 1. ✓

Example 2 — Divisor functions and φ. For n = 360.

• 360 = 2³ × 3² × 5.
• d(360) = (3+1)(2+1)(1+1) = 24 divisors.
• σ(360) = (2⁴−1)/1 × (3³−1)/2 × (5²−1)/4 = 15 × 13 × 6 = 1170. Since 1170 > 720, 360 is abundant.
• φ(360) = 360(1 − 1/2)(1 − 1/3)(1 − 1/5) = 360 × 1/2 × 2/3 × 4/5 = 96.
• Product of divisors = 360¹² .
• With m = 84 = 2²·3·7: gcd(360, 84) = 2^min(3,2)·3^min(2,1) = 4 × 3 = 12; lcm = 2³·3²·5·7 = 2520. Check 12 × 2520 = 30240 = 360 × 84. ✓

Example 3 — Chinese Remainder Theorem. Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

• N = 105; M₁ = 35, M₂ = 21, M₃ = 15.
• 35 ≡ 2 (mod 3) → y₁ = 2 (2·2 = 4 ≡ 1). 21 ≡ 1 (mod 5) → y₂ = 1. 15 ≡ 1 (mod 7) → y₃ = 1.
• x = 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 ≡ 233 − 2(105) = 23 (mod 105).
• Verify: 23 = 3(7)+2 ✓, 23 = 5(4)+3 ✓, 23 = 7(3)+2 ✓.

Example 4 — Reducing a huge power (Euler + fast exponentiation). Find 7²²² mod 100.

• φ(100) = 100(1/2)(4/5) = 40, gcd(7,100) = 1, so 7⁴⁰ ≡ 1. 222 = 40(5) + 22 → 7²²² ≡ 7²² (mod 100).
• 7² = 49; 7⁴ = 49² = 2401 ≡ 1 (mod 100). So 7²² = 7^{4·5 + 2} ≡ 1⁵ × 49 = 49 (mod 100).
• Same method for last digits: 2¹⁰⁰⁰ mod 10 → the cycle of 2 is 2,4,8,6 (period 4); 1000 ≡ 0 mod 4 → last digit 6.

Example 5 — Trailing zeros and a small RSA.

• Zeros at the end of 100!: exponent of 5 = ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24 (2s are plentiful), so 100! ends in 24 zeros.
• RSA with p = 11, q = 13: n = 143, φ(n) = 10 × 12 = 120, take e = 7. Then d = 7⁻¹ mod 120 = 103 (7 × 103 = 721 = 6×120 + 1 ✓). Encrypt m = 9: 9² = 81, 9⁴ = 81² = 6561 ≡ 6561 − 45(143) = 126, 9⁶ ≡ 126 × 81 = 10206 ≡ 10206 − 71(143) = 53, 9⁷ ≡ 53 × 9 = 477 ≡ 477 − 3(143) = 48. So c = 48.

def egcd(a, b):                 # returns (g, x, y) with ax + by = g
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def power_mod(a, b, n):         # square and multiply, O(log b)
    r = 1
    a %= n
    while b:
        if b & 1:
            r = r * a % n
        a = a * a % n
        b >>= 1
    return r

Where it is used

• Digital payments and banking IT: RSA/ECC signatures and key exchange in UPI, NPCI switches, net-banking TLS and HSM-backed PIN blocks; roles in payment security at NPCI, Razorpay, PhonePe, Paytm, HDFC/ICICI tech teams.
• e-Governance and identity: Aadhaar's Verhoeff check digit and digital signatures under the IT Act, 2000 and CCA-licensed certifying authorities (eMudhra, NIC CA); DigiLocker and e-Sign stacks; GSTIN and PAN validation logic in ERP and billing software.
• Defence and government research: cryptology and cryptanalysis posts at DRDO (SAG), ISRO, C-DAC, SETS Chennai and RBI's IDRBT; NET/GATE-qualified mathematicians work on stream ciphers and lattice/post-quantum schemes.
• Software product and placement coding rounds: GCD/LCM, modular arithmetic "answer mod 10⁹+7", sieve, modular inverse for nCr — standard in Amazon, Microsoft, Adobe, Goldman Sachs, Flipkart and Directi tests, and in ICPC/CodeChef.
• Error detection and data engineering: check digits in ISBN, EAN barcodes, IMEI (Luhn), cheque MICR routines; hash table sizing with primes; CRC and Reed–Solomon in storage and telecom.
• Teaching and academia: UGC-NET/CSIR-NET, GATE MA and CS, assistant-professor and actuarial/analytics roles that test discrete mathematics.

Interview questions

• Q: Why does the Euclidean algorithm work? A: Because any common divisor of a and b also divides a − bq, so gcd(a, b) = gcd(b, a mod b); the remainders strictly decrease and must reach 0.
• Q: When does ax ≡ b (mod n) have a solution, and how many? A: When g = gcd(a, n) divides b; it then has exactly g solutions modulo n, differing by n/g.
• Q: When does a have a multiplicative inverse modulo n? A: Exactly when gcd(a, n) = 1; the inverse comes from Bézout's coefficients, ax + ny = 1.
• Q: Is gcd(a,b) × lcm(a,b) = abc-style identity valid for three numbers? A: No — gcd × lcm = ab holds only for two integers; for three you must work with prime exponents (min and max) separately.
• Q: State Fermat's little theorem and say why it is not a reliable primality test. A: a^p−1 ≡ 1 (mod p) for prime p with p ∤ a; the converse fails because Carmichael numbers such as 561 satisfy it for every coprime base.
• Q: How would you compute 3¹⁰⁰⁰ mod 7 by hand? A: φ(7) = 6 and 3⁶ ≡ 1, 1000 = 6(166) + 4, so the answer is 3⁴ = 81 ≡ 4 (mod 7).
• Q: What makes RSA secure, and what breaks it? A: Recovering d needs φ(n), which needs the factors of n; efficient factoring (or a large quantum computer running Shor's algorithm) breaks it.
• Q: Why must the moduli in the CRT be pairwise coprime? A: Otherwise the map to the residue tuples is not a bijection — the system may have no solution or many, and uniqueness mod the product fails.
• Q: Explain the sieve of Eratosthenes and its complexity. A: Mark multiples of each prime p ≤ √n starting at p²; everything unmarked is prime, in O(n log log n) time and O(n) space.
• Q: How do you compute nCr mod a prime p for large n? A: Precompute factorials mod p and use Fermat's little theorem for inverses (x⁻¹ ≡ x^p−2 mod p), or Lucas' theorem when n exceeds p.
• Q: Give a quick derivation of φ(n) for n = p·q with distinct primes. A: Of the pq numbers, q are multiples of p and p are multiples of q, with 1 counted twice, so φ = pq − p − q + 1 = (p−1)(q−1).
• Q: How many trailing zeros does 1000! have? A: ⌊1000/5⌋ + ⌊1000/25⌋ + ⌊1000/125⌋ + ⌊1000/625⌋ = 200 + 40 + 8 + 1 = 249.

Common mistakes

• Taking a negative remainder: −17 mod 5 is 3, not −2; the division algorithm demands 0 ≤ r < b.
• Cancelling a common factor across a congruence: from 6 ≡ 24 (mod 9) you may only conclude 1 ≡ 4 (mod 3), not mod 9.
• Assuming a⁻¹ exists for every a mod n, or treating ℤ_n as a field when n is composite (ℤ_6 has zero divisors).
• Applying Euler's theorem when gcd(a, n) ≠ 1 — e.g. reducing 10^k mod 100 by φ(100); here use the pattern or CRT instead.
• Calling 1 prime, or forgetting that 2 is prime, which corrupts d(n), φ(n) and sieve code.
• Using gcd × lcm = ab for three or more numbers, or forgetting the absolute value for negatives.
• Using CRT with non-coprime moduli, or missing the "exactly g solutions" count in a linear congruence and reporting just one.

Related topics

Group theory and rings (ℤ_n as a group and field) · Cryptography and network security · Discrete mathematics and combinatorics · Algorithms and complexity · Graph theory basics · Linear algebra over finite fields