Chapter 5 · Introduction

Chapter 5 — Combinatorics and Number Theory

The algebra half of the course begins with whole numbers: counting arrangements without listing them, the pigeonhole and inclusion–exclusion principles, unique factorisation, congruences and the Chinese Remainder Theorem, and the powers of a number modulo $n$.

In 1708 Pierre Rémond de Montmort, writing about the card game Treize, asked a question that sounds like a party trick: if thirteen cards numbered $1$ to $13$ are shuffled and turned over one by one while the dealer counts "one, two, …, thirteen", how likely is it that no card turns up at its own count? The answer — almost exactly $1/e$, whatever the number of cards — was found by Montmort and Nicolaus Bernoulli and later re-derived by Euler, and the method behind it, inclusion–exclusion, became one of the two great tools of exact counting. The other is even simpler. Peter Gustav Lejeune Dirichlet used the Schubfachprinzip (the "drawer principle") in 1842 to prove that every irrational number has unusually good rational approximations: if more letters are put into drawers than there are drawers, some drawer holds two letters. Section 5.1 develops both tools, together with permutations and combinations, the binomial and multinomial theorems, stars and bars, derangements, surjections and Stirling numbers. These are not only exam topics in their own right: the counting arguments of Chapter 6 (Lagrange's theorem, the class equation, Sylow's theorems, Burnside's lemma) and of Chapter 8 (the number of irreducible polynomials over a finite field) are all built from them.

The second half of the chapter is number theory, the oldest continuously studied part of mathematics. Euclid's Elements (about 300 BCE) already contains the algorithm for the greatest common divisor and the proof that there are infinitely many primes. The Chinese mathematical text Sunzi Suanjing (third to fifth century CE) asks for a number that leaves remainders $2$, $3$, $2$ on division by $3$, $5$, $7$ — the first recorded instance of the Chinese Remainder Theorem (the answer is $23$). Pierre de Fermat stated his "little theorem" $a^{p}\equiv a\pmod p$ in a letter of 1640; Leonhard Euler proved it and in 1763 generalised it with his $\varphi$-function; and Carl Friedrich Gauss, in his Disquisitiones Arithmeticae of 1801, introduced the notation $a\equiv b\pmod n$ that we still use and proved that primitive roots exist modulo every prime. Section 5.2 develops divisibility, unique factorisation, congruences and the Chinese Remainder Theorem; Section 5.3 treats Euler's function, orders of elements and primitive roots. Today the same results secure the internet: RSA encryption works because of Euler's theorem, and the Chinese Remainder Theorem makes its decryption about four times faster. For us they are also the first examples of the groups $\mathbb{Z}_n$ and $U(n)$ of Chapter 6 and the finite fields of Chapter 8.

Sum & product rules→Permutations, combinations→Binomial & multinomial→Stars and bars→Pigeonhole→Inclusion–exclusion→Derangements, surjections→gcd & Bézout→Unique factorisation→Congruences, CRT→Fermat, Wilson→φ & Euler→Primitive roots
🎯 By the end of this chapter you can…
  • choose the right counting model — ordered or unordered, with or without repetition, distinct or identical objects and boxes — and count arrangements, selections, distributions and integer solutions of equations with bounds;
  • prove binomial identities by double counting and expand multinomial powers;
  • apply the pigeonhole principle and its generalised form to prove existence statements, and recognise when a bound is sharp;
  • use inclusion–exclusion to count derangements, surjections and integers avoiding given divisors, and work with Stirling and Bell numbers and the number of relations of each type on a finite set;
  • compute gcds with Euclid's algorithm, find Bézout coefficients, prove unique factorisation and solve linear Diophantine equations and linear congruences;
  • solve systems of congruences by the Chinese Remainder Theorem, and use the theorems of Fermat, Euler and Wilson to reduce large powers and factorials;
  • compute $\varphi(n)$, orders and primitive roots, decide for which $n$ primitive roots exist, and count them.
Teaser — Powers on a Clock

The remainders $0,1,\dots,n-1$ modulo $n$ sit round a clock. Starting at $1$, multiply by $a$ again and again, always reducing modulo $n$: $1\to a\to a^2\to\cdots$. There are only $n$ remainders, so by the pigeonhole principle some power must repeat within $n$ steps. Press Play to watch the walk, or move the sliders. When $\gcd(a,n)=1$ the walk always returns to $1$, after a number of steps that divides $\varphi(n)$; when it takes exactly $\varphi(n)$ steps, $a$ is a primitive root.

143
n, a, gcd(a, n)—
powers so far—
tail + cycle length—
φ(n)—
order of a—

How this is examined

Chapter 5 is the most "numerical" part of the algebra syllabus, and CSIR NET uses it in Part B for short computations with a single correct answer: the number of derangements of a small set, or of permutations with exactly $k$ fixed points; the number of surjections, of equivalence relations, or of relations with given properties on a set with four or five elements; the number of integer solutions of $x_1+\cdots+x_r=n$ with lower or upper bounds; the least number of objects that forces a repetition; a remainder such as $7^{2026}\bmod 13$ or $40!\bmod 41$; the smallest positive solution of a system of congruences; $\varphi(n)$ or the number of primitive roots modulo $n$. Part C, where more than one option may be correct, prefers statements to be judged: "for which $n$ does a primitive root exist?", "is $a^{n-1}\equiv1\pmod n$ enough to make $n$ prime?", "is $\varphi(n)$ even?", "which of these congruences are solvable?", or a list of counting claims in which one option forgets inclusion–exclusion and another confuses identical with distinct boxes. The false options are exactly the counterexamples collected in the ⚠️ boxes of the three sections. Number theory also feeds the group theory of Chapter 6 — the orders of elements of $\mathbb{Z}_n$ and $U(n)$, the number of generators of a cyclic group and the number of homomorphisms $\mathbb{Z}_m\to\mathbb{Z}_n$ are all questions about gcds and $\varphi$. GATE MA asks similar questions, often as numerical-answer items.

Sections in this chapter

✅ Before you start

This chapter does not depend on the complex analysis of Chapters 1–4; you can start the algebra half here. You need proof by induction (including strong induction) and by contradiction, the well-ordering principle (every nonempty set of positive integers has a least element), and the language of sets, functions, injections, surjections and equivalence relations — treated in the sister course CSIR NET Unit 1 — Analysis and Linear Algebra (§1.1, Sets, Functions and Countable Sets). Roots of unity (§1.1) appear once or twice as an illustration, and the binomial theorem from school is assumed only as a formula — we prove it in §5.1. If this is your first visit, read the welcome page for how the sections are organised and how to use the 🎯 Exam corner.