Course Theory

Book 1. Introduction to Olympiad Number Theory

1. Divisibility and Prime Factorisation
2. GCD, LCM and Euclidean Algorithm
3. Modular Arithmetic I: Residues and Contradictions
4. Modular Arithmetic II: Linear Congruences and Systems
5. Diophantine Equations I: Factorisation and Bounds
6. Infinite Descent I
7. Fermat, Euler and Power Cycles
8. Chinese Remainder Theorem
9. Divisor Counting
10. Digits, Bases and Periodicity
11. Mixed Problems I
12. Mock Olympiads I

Back to Course

Chapter

Divisibility and Prime Factorisation

The module introduces the precise language of divisibility, primes, factorisation, divisor counting, and first olympiad techniques: consecutive integers, parameters, and factorial constructions.

Key Idea Divisibility in olympiad number theory is not quick division; it is a way to see integer structure. The notation \(a\mid b\) means that \(b=ak\) for some integer \(k\). Prime factorisation turns a number into a list of prime exponents. Many problems then become questions about which prime factors, and which powers of them, must be present. Basic Facts If \(d\mid a\) and \(d\mid b\), then \(d\mid xa+yb\) for all integers \(x,y\). If \(a\mid b\) and \(b\mid c\), then \(a\mid c\). Every integer \(n>1\) has a unique factorisation into prime powers. If \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), then the number of positive divisors is \((\alpha_1+1)\cdots(\alpha_s+1)\). If \(p\) is prime and \(p\mid ab\), then \(p\mid a\) or \(p\mid b\). Among \(k\) consecutive integers, one is divisible by \(k\), but divisibility by \(k!\) requires careful collection of prime powers. When to Use This Method The statement contains "divisible", "divisor", "prime", "factorisation", or "number of divisors". You need to prove a divisibility statement for all integers \(n\). You need to find all parameters for which one expression divides another. You need to construct a number with prescribed divisors or a prescribed number of divisors. You need to disprove a false divisibility claim by a single counterexample. How to Recognise the Method If the divisor contains a variable, try reducing the variable modulo that divisor. For example, under \(n+3\mid f(n)\), it is natural to write \(n\equiv -3\pmod{n+3}\). If the expression resembles a product of nearby numbers, factor it into consecutive terms. If the problem is about the number of divisors, move immediately to prime exponents. Typical Mistakes From \(ab\mid c\) or \(d\mid ab\), incorrectly concluding divisibility of individual factors. Calling \(1\) prime, which breaks uniqueness of prime factorisation. Proving divisibility by \(2\), \(3\), \(5\), but forgetting that pairwise coprimality is needed to combine them. When counting divisors, forgetting the zero exponent choice. In "for all \(n\)" problems, checking examples instead of proving the statement. Mini-Checklist Can the divisibility be written as \(b=ak\)? Can the expression be reduced modulo the variable divisor? Should the expression be factorised? Which prime powers must divide the number? If the greatest universal divisor is asked for, which small \(n\) gives an upper bound?

Example 1. Divisibility as an Exact Equality The first skill is translating \(a\mid b\) into an equality with an integer factor. Problem. Suppose \(12\mid n\). Prove that \(3\mid n\) and \(4\mid n\). Solution. From \(12\mid n\), we have \(n=12k\) for some integer \(k\). Then \(n=3(4k)\), so \(3\mid n\). Also \(n=4(3k)\), so \(4\mid n\). Comment. No approximate division is needed; everything uses an integer factor. Example 2. A Linear Combination One of the main properties of divisibility: from two divisible expressions we can build new ones. Problem. If \(7\mid a\) and \(7\mid b\), prove that \(7\mid 5a-3b\). Solution. Write \(a=7x\), \(b=7y\). Then \(5a-3b=35x-21y=7(5x-3y)\). Since \(5x-3y\) is an integer, \(7\mid 5a-3b\). Comment. This idea later becomes the language of GCD and the Euclidean algorithm. Example 3. Factorisation and Divisors The number of divisors is counted not by listing divisors, but by choosing prime exponents. Problem. Find the number of positive divisors of \(1260\). Solution. Factorise: \(1260=126\cdot 10=2^2\cdot 3^2\cdot 5\cdot 7\). A divisor has the form \(2^a3^b5^c7^d\), where \(a=0,1,2\), \(b=0,1,2\), \(c=0,1\), \(d=0,1\). Therefore the number of divisors is \(3\cdot 3\cdot 2\cdot 2=36\). Comment. A zero exponent means that the corresponding prime is absent from the divisor. Example 4. Three Consecutive Integers A product of nearby integers usually contains the needed prime factors. Problem. Prove that \(6\mid n(n+1)(n+2)\) for every integer \(n\). Solution. Among three consecutive integers, one is divisible by \(3\). Among any two consecutive integers, one is even, so among three there is also an even number. Hence the product is divisible by both \(2\) and \(3\). Since \(2\) and \(3\) are coprime, the product is divisible by \(6\). Comment. It is important to explicitly combine divisibility by coprime factors. Example 5. A False Claim In olympiad problems it is useful to quickly see where a divisibility property cannot be used. Problem. Is it true that \(6\mid ab\) implies \(6\mid a\) or \(6\mid b\)? Solution. No. Take \(a=2\), \(b=3\). Then \(ab=6\), so \(6\mid ab\). But \(6\nmid 2\) and \(6\nmid 3\). The claim is false. Comment. A similar statement is true for a prime divisor \(p\), but not for the composite number \(6\). Example 6. A Variable Divisor When the divisor contains \(n\), it is often best to replace \(n\) by a convenient remainder. Problem. Find all integers \(n\) for which \(n+3\mid n^2+n+1\). Solution. Modulo \(n+3\), we have \(n\equiv -3\). Hence \(n^2+n+1\equiv 9-3+1=7\pmod{n+3}\). Therefore \(n+3\mid 7\). Thus \(n+3\in\{\pm1,\pm7\}\), and \(n\in\{-2,-4,4,-10\}\). All these values work. Comment. This is a typical move: the remainder of the expression becomes a small constant. Example 7. Greatest Universal Divisor For a statement that holds for all \(n\), we need both a lower and an upper bound. Problem. Find the greatest \(m\) such that \(m\mid n(n+1)(n+2)\) for every integer \(n\). Solution. From the previous example, \(6\) always divides the product of three consecutive integers. Thus \(m=6\) is possible.On the other hand, at \(n=1\), the product is \(1\cdot2\cdot3=6\). Hence any universal divisor \(m\) must divide \(6\). Therefore the greatest possible \(m\) is \(6\). Comment. A small value of \(n\) often gives an upper bound for the answer. Example 8. A Long Block of Composite Numbers A factorial can build many divisors into a construction in advance. Problem. Prove that there exist \(10\) consecutive composite positive integers. Solution. Consider the numbers \(11!+2,11!+3,\ldots,11!+11\). The number \(11!+k\) is divisible by \(k\), because \(11!\) is divisible by \(k\) for \(2\le k\le 11\). Also \(11!+k>k\). Hence each of these numbers has a nontrivial divisor \(k\) and is composite. We have obtained \(10\) consecutive composite numbers. Comment. The same construction gives a block of any prescribed length.

Chapter

GCD, LCM and Euclidean Algorithm

The module turns computational GCD into an olympiad tool: Euclid's algorithm, linear combinations, GCDs of expressions, the GCD-LCM relation, coprimality, and numbers of the form \(a^m-1\).

Key Idea The GCD measures the common part of two numbers, while the LCM is the smallest number containing both structures as divisors. In olympiad problems, the GCD is not just something to compute; common divisors can be moved between expressions. The Euclidean algorithm is based on \(\gcd(a,b)=\gcd(b,a-b)\), and more strongly on \(\gcd(a,b)=\gcd(b,r)\), where \(r\) is the remainder when \(a\) is divided by \(b\). Basic Facts \(\gcd(a,b)\operatorname{lcm}(a,b)=ab\) for positive \(a,b\). If \(d=\gcd(a,b)\), then \(a=dx\), \(b=dy\), where \(\gcd(x,y)=1\). \(\gcd(a,b)=\gcd(a,b-a)=\gcd(b,a\bmod b)\). If \(\gcd(a,b)=1\) and \(a\mid bc\), then \(a\mid c\). A common divisor of two expressions divides every integer linear combination of them. For \(a>1\): \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). When to Use This Method You need to find a common divisor of two expressions with a parameter. The problem contains both a GCD and an LCM. You need to reduce a large pair of numbers without prime factorising them. Numbers of the form \(a^m-1\) and \(a^n-1\) appear. You need to prove that two expressions are coprime. How to Recognise the Method If two expressions depend on \(n\), try subtracting one from the other or forming a linear combination to lower the degree. Often the GCD divides a small constant. If the GCD and LCM of two numbers are given, write \(a=dx\), \(b=dy\), \(\gcd(x,y)=1\). Then the LCM is \(dxy\). Typical Mistakes Computing the GCD of large numbers by factorisation when Euclid is shorter. Using \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) for three numbers, where it is false. After writing \(a=dx\), \(b=dy\), forgetting the condition \(\gcd(x,y)=1\). Cancelling in a divisibility or congruence without checking coprimality. For \(a^m-1\), expanding powers instead of applying Euclid to the exponents. Mini-Checklist Can the pair \((a,b)\) be replaced by \((b,a-b)\) or \((b,r)\)? Can you form a small linear combination of the expressions? If GCD and LCM are known, have you written \(a=dx\), \(b=dy\)? Have you checked that the remaining parts are coprime? For powers \(a^m-1\), can the Euclidean algorithm be applied to the exponents?

Example 1. The Euclidean Algorithm We learn to reduce a pair of numbers without full factorisation. Problem. Find \(\gcd(252,198)\). Solution. \(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=18\). The answer is \(18\). Comment. At each step, replace the larger number by its remainder upon division by the smaller one. Example 2. GCD and LCM by Prime Powers Minimum and maximum exponents give the GCD and LCM. Problem. Find \(\gcd(84,126)\) and \(\operatorname{lcm}(84,126)\). Solution. \(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\). Therefore \(\gcd(84,126)=2\cdot3\cdot7=42\), while \(\operatorname{lcm}(84,126)=2^2\cdot3^2\cdot7=252\). Comment. The GCD takes smaller exponents; the LCM takes larger ones. Example 3. Given the GCD and LCM The relation \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) often finds an unknown number immediately. Problem. Find \(n\) if \(\gcd(n,70)=14\) and \(\operatorname{lcm}(n,70)=420\). Solution. For two positive numbers, \(n\cdot70=\gcd(n,70)\operatorname{lcm}(n,70)\). Hence \(70n=14\cdot420\), so \(n=84\). Check: \(\gcd(84,70)=14\), \(\operatorname{lcm}(84,70)=420\). Comment. The formula applies to exactly two numbers. Example 4. GCD of Expressions with a Parameter A common divisor often divides a small constant. Problem. Prove that \(\gcd(n^2+1,n+3)\) divides \(10\). Solution. Let \(d=\gcd(n^2+1,n+3)\). Then \(n\equiv -3\pmod d\), so \(n^2+1\equiv 9+1=10\pmod d\). Since \(d\mid n^2+1\), we get \(d\mid10\). Comment. This is the main move for problems of the form \(\gcd(f(n),g(n))\). Example 5. Coprimality of Consecutive Integers The simplest example of a GCD equal to one. Problem. Prove that \(\gcd(n,n+1)=1\). Solution. Any common divisor of \(n\) and \(n+1\) divides their difference \((n+1)-n=1\). Hence the only possible common divisor is \(1\). Comment. The difference of consecutive numbers is the shortest route. Example 6. Division Under Coprimality This is one of the most frequently used facts in number theory. Problem. Let \(\gcd(a,b)=1\) and \(a\mid bc\). Prove that \(a\mid c\). Solution. All prime factors of \(a\) are absent from \(b\), since \(\gcd(a,b)=1\). But \(bc\) is divisible by \(a\), so all prime factors of \(a\), with their needed powers, must occur in \(c\). Therefore \(a\mid c\). Comment. Later this becomes a precise tool in congruences. Example 7. Powers Minus One The Euclidean algorithm can be applied to exponents. Problem. Find \(\gcd(2^{18}-1,2^{30}-1)\). Solution. Use \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Since \(\gcd(18,30)=6\), we get \(2^6-1=63\). Comment. The formula can be proved by Euclid: \(a^m-1\) is divisible by \(a^d-1\) when \(d\mid m\). Example 8. GCD of Repeated Blocks Sometimes the GCD of a whole family is visible from a common factor. Problem. Find the GCD of all six-digit numbers of the form \(\overline{abcabc}\). Solution. Such a number equals \(1000\cdot\overline{abc}+\overline{abc}=1001\cdot\overline{abc}\). Hence all such numbers are divisible by \(1001\). On the other hand, among three-digit blocks there are coprime ones, for example \(100\) and \(101\), so no extra common factor is forced. The GCD of the whole family is \(1001\). Comment. This is not a computation for one pair, but a GCD of a family.

Chapter

Modular Arithmetic

Remainders, congruences, arithmetic modulo m, power cycles, and modular contradiction.

1. Remainders When an integer \(a\) is divided by a positive integer \(m\), we can write \[ a=mq+r,\qquad 0\le r The number \(r\) is the remainder. Modular arithmetic is a way to work with remainders without carrying the full number. 2. Congruence We write \[ a\equiv b\pmod m \] if \(a\) and \(b\) have the same remainder when divided by \(m\). Equivalently, \[ m\mid a-b. \] For example, \(17\equiv 2\pmod 5\), because \(17-2=15\) is divisible by \(5\). 3. Arithmetic with Congruences If \[ a\equiv b\pmod m,\qquad c\equiv d\pmod m, \] then \[ a+c\equiv b+d\pmod m, \] \[ ac\equiv bd\pmod m. \] This means we can add, subtract, and multiply remainders. 4. Powers and Cycles Powers often repeat modulo \(m\). For example, modulo \(10\), \[ 2^1\equiv2,\quad 2^2\equiv4,\quad 2^3\equiv8,\quad 2^4\equiv6,\quad 2^5\equiv2. \] So the last digit of powers of \(2\) repeats with cycle length \(4\): \(2,4,8,6\). 5. Modular Contradiction To prove that an equation has no integer solutions, look at both sides modulo a small number. If the possible remainders cannot match, the equation is impossible. Example: no integer square is congruent to \(2\pmod 4\), because squares are only \(0\) or \(1\pmod 4\). 6. Divisibility Tests as Modular Arithmetic Digit rules come from modular arithmetic. Since \[ 10\equiv1\pmod 9, \] every power of \(10\) is congruent to \(1\pmod 9\). Therefore a number has the same remainder modulo \(9\) as the sum of its digits.

Example 1. Remainder of a Number This example connects ordinary division with remainders: write the number as \(mq+r\) with \(0\le r Problem. Find the remainder when \(137\) is divided by \(5\). Solution. Since \(137=5\cdot27+2\), the remainder is \(2\). Example 2. Write a Congruence This example shows how congruence notation records the remainder after division by the modulus. Problem. Complete the congruence: \(83\equiv \square \pmod 7\), where the box is one of \(0,1,2,3,4,5,6\). Solution. \(83=7\cdot11+6\), so \(83\equiv6\pmod7\). Example 3. Add Remainders This example shows that congruences let us add remainders first and reduce only at the end. Problem. If \(a\equiv4\pmod9\) and \(b\equiv7\pmod9\), find \(a+b\pmod9\). Solution. \(a+b\equiv4+7=11\equiv2\pmod9\). Example 4. Last Digit of a Power This example shows how powers repeat in cycles modulo \(10\), which controls the last digit. Problem. Find the last digit of \(2^{25}\). Solution. The cycle length is \(4\). Since \(25\equiv1\pmod4\), \(2^{25}\) has the same last digit as \(2^1\), which is \(2\). Example 5. Power Modulo Seven This example shows how to use a power cycle modulo \(7\) instead of computing a huge power. Problem. Find the remainder of \(3^{20}\) when divided by \(7\). Solution. Modulo \(7\): \(3^1\equiv3\), \(3^2\equiv2\), \(3^3\equiv6\), \(3^4\equiv4\), \(3^5\equiv5\), \(3^6\equiv1\). Since \(20\equiv2\pmod6\), \(3^{20}\equiv3^2\equiv2\pmod7\). Example 6. Squares Modulo Four This example shows a standard modular fact: every square has only certain possible residues modulo \(4\). Problem. Prove that every integer square is congruent to \(0\) or \(1\pmod4\). Solution. If \(n=2k\), then \(n^2=4k^2\equiv0\pmod4\). If \(n=2k+1\), then \(n^2=4k^2+4k+1\equiv1\pmod4\). Example 7. No Square of This Form This example shows how modular arithmetic can prove that an equation has no integer solutions. Problem. Prove that the equation \(x^2=4y+2\) has no integer solutions. Solution. The right side satisfies \(4y+2\equiv2\pmod4\). But a square is only \(0\) or \(1\pmod4\). Contradiction. Example 8. Always Divisible by Five This example shows how checking residues modulo \(5\) proves a divisibility statement for every integer. Problem. Prove that \(5\mid n^5-n\) for every integer \(n\). Solution. It is enough to check \(n\equiv0,1,2,3,4\pmod5\). We get \(0^5-0=0\), \(1^5-1=0\), \(2^5-2=30\), \(3^5-3=240\), \(4^5-4=1020\), all divisible by \(5\). Therefore \(5\mid n^5-n\).

Chapter

Modular Arithmetic I: Residues and Contradictions

The module teaches residues as a tool for proving impossibility: tables of squares and cubes, choosing a modulus, last digits, and first modular contradictions.

Key Idea Congruences replace infinitely many integers by a finite table of residues. To prove impossibility, it is often enough to find a modulus in which the two sides always belong to disjoint sets of residues. The main skill in this module is not mechanical computation, but choosing the modulus: \(3,4,5,7,8,9,11,16\) often produce quick contradictions. Basic Facts \(a\equiv b\pmod m\) means that \(m\mid a-b\). If \(a\equiv b\pmod m\), congruences may be added, subtracted, and multiplied. Squares modulo \(4\) are only \(0,1\); squares modulo \(8\) are only \(0,1,4\). Cubes modulo \(9\) are only \(0,1,8\), i.e. \(0,\pm1\). The last digit is a residue modulo \(10\); the last two digits are a residue modulo \(100\). A contradiction modulo one modulus proves that no integer solutions exist. When to Use This Method You need to prove that an equation has no integer solutions. The expression contains squares, cubes, fourth powers, or last digits. You need to find all \(n\) for which an expression is divisible by a small number. Parity matters, but parity alone is not enough. Large powers have repeating residues. How to Recognise the Method If the right side has the form \(4k+3\), \(8k+7\), or \(3k+2\), try square residue tables. If cubes appear, test modulo \(7\) or \(9\). If the problem asks about the last digit, look for a power cycle. The right modulus is usually small and makes one side very restricted: for example, a square modulo \(8\) cannot be \(2,3,5,6,7\). Typical Mistakes Dividing a congruence by a number without checking whether that is allowed. Checking only positive residues and forgetting that negative integers fall into the same residue classes. Assuming that if one modulus gives no contradiction, then solutions must exist. Confusing "a square may have residue \(1\)" with "every number of residue \(1\) is a square". Using only modulo \(10\) in a problem about the last two digits. Mini-Checklist Which residues do squares or cubes give modulo the chosen modulus? Which residues can the left side have? Which residues can the right side have? Do these sets intersect? If there are no solutions modulo \(m\), is the contradiction written explicitly?

Example 1. Residues and Congruences A congruence fixes the residue but lets us work without exact division. Problem. Find the remainder of \(2026^2+2026\) upon division by \(5\). Solution. \(2026\equiv1\pmod5\). Hence \(2026^2+2026\equiv1^2+1=2\pmod5\). The remainder is \(2\). Comment. First replace the number by its residue, then compute. Example 2. Squares Modulo 8 Squares have very few possible residues. Problem. Show that the square of an integer modulo \(8\) can only have residue \(0,1,4\). Solution. Check residues \(0,1,2,\ldots,7\). Their squares modulo \(8\) are \(0,1,4,1,0,1,4,1\). Thus only \(0,1,4\) are possible. Comment. This table will be used many times. Example 3. Impossibility of \(4z+3\) A sum of two squares cannot be \(3\) modulo \(4\). Problem. Prove that \(x^2+y^2=4z+3\) has no integer solutions. Solution. A square modulo \(4\) is \(0\) or \(1\). Therefore a sum of two squares modulo \(4\) can be \(0,1,2\), but not \(3\). The right side \(4z+3\equiv3\pmod4\). Contradiction. Comment. The modulus \(4\) is suggested by the form of the right side. Example 4. Impossibility of \(8z+7\) Modulo \(8\) is stronger than ordinary parity. Problem. Prove that \(x^2+y^2=8z+7\) has no integer solutions. Solution. Squares modulo \(8\) are \(0,1,4\). A sum of two such residues can be \(0,1,2,4,5\), but not \(7\). The right side is \(7\) modulo \(8\). Contradiction. Comment. Here modulo \(4\) would be weaker, while modulo \(8\) solves the problem. Example 5. Divisibility of \(n^2+n+1\) by 7 Sometimes it is easiest to check all residues modulo a small number. Problem. Find all residues \(n\pmod7\) for which \(7\mid n^2+n+1\). Solution. Check \(n=0,1,2,3,4,5,6\). The values of \(n^2+n+1\) modulo \(7\) are \(1,3,0,6,0,3,1\). Thus \(n\equiv2\) and \(n\equiv4\pmod7\) work. Comment. A seven-row table is acceptable when it gives the full answer. Example 6. Cubes Modulo 9 Cubes modulo \(9\) have only three possible residues. Problem. Show that the cube of an integer modulo \(9\) is \(0,1\), or \(8\). Solution. Check residues \(0,\ldots,8\): the cubes are \(0,1,8,0,1,8,0,1,8\). Hence only \(0,1,8\), i.e. \(0,\pm1\), are possible. Comment. This table is useful for sums of cubes. Example 7. Last Digit of a Power The last digit is work modulo \(10\). Problem. Find the last digit of \(7^{2026}\). Solution. The last digits of powers of \(7\) cycle as \(7,9,3,1\). The cycle length is \(4\). Since \(2026\equiv2\pmod4\), we take the second digit in the cycle: \(9\). Comment. There is no need to compute the large power. Example 8. Choosing the Right Modulus Sometimes the modulus is suggested by a coefficient. Problem. Prove that the equation \(x^2=3y^2+2\) has no integer solutions. Solution. Consider the equation modulo \(3\). The right side satisfies \(3y^2+2\equiv2\pmod3\). But a square modulo \(3\) can only be \(0\) or \(1\). Contradiction. Comment. Modulo \(3\) is chosen because the right side is almost a multiple of \(3\).

Chapter

Congruences and Remainders

Residue classes, linear congruences, compatible remainders, and olympiad-style remainder arguments.

1. Residue Classes Modulo \(m\), every integer belongs to exactly one of the classes \[ 0,1,2,\ldots,m-1. \] For example, modulo \(5\), the integers split into five residue classes. The number \(23\) belongs to class \(3\), because \(23\equiv3\pmod5\). 2. Congruence as a Tool The statement \[ a\equiv b\pmod m \] means that \(a-b\) is divisible by \(m\). This turns questions about large numbers into questions about small remainders. 3. Solving Linear Congruences A congruence such as \[ ax\equiv b\pmod m \] is called a linear congruence. If \(\gcd(a,m)=1\), then \(a\) has an inverse modulo \(m\), and the congruence has exactly one solution modulo \(m\). Example: \[ 3x\equiv5\pmod7. \] Since \(3\cdot5\equiv1\pmod7\), multiply both sides by \(5\): \[ x\equiv25\equiv4\pmod7. \] 4. When Division Is Dangerous In ordinary equations, we often divide both sides. In congruences, division is allowed only when the divisor is invertible modulo \(m\). For example, \[ 2x\equiv2\pmod6 \] cannot simply be divided by \(2\) to get \(x\equiv1\pmod6\). In fact, the solutions are \[ x\equiv1,4\pmod6. \] 5. Compatible Remainders Sometimes a number must satisfy several remainder conditions: \[ n\equiv a\pmod m,\qquad n\equiv b\pmod k. \] When \(m\) and \(k\) are small, we can list one residue class and test it in the other condition. This prepares for the Chinese Remainder Theorem later. 6. Remainder Arguments in Olympiad Problems Remainders are useful for proving that something is impossible, finding the form of a number, or reducing many cases to a few. A good habit is to ask: Which modulus makes the expression simple? Which remainders are possible? Can a common divisor, square, or power force a contradiction?

Example 1. Residue Class This example shows how a standard residue identifies the residue class of an integer modulo a fixed number. Problem. Find the residue class of \(94\) modulo \(9\). Solution. Since \(94=9\cdot10+4\), we have \(94\equiv4\pmod9\). Example 2. Negative Residue This example reminds students that negative numbers also have standard residues between 0 and m-1. Problem. Write \(-17\) as a standard residue modulo \(6\). Solution. \(-17+18=1\), so \(-17\equiv1\pmod6\). Example 3. Equivalent Congruences This example connects congruence notation with the divisibility condition behind it. Problem. Explain why \(a\equiv b\pmod m\) is equivalent to \(m\mid a-b\). Solution. If \(a=mq+r\) and \(b=mk+r\), then \(a-b=m(q-k)\), so \(m\mid a-b\). Conversely, if \(m\mid a-b\), then \(a\) and \(b\) differ by a multiple of \(m\), so they have the same remainder modulo \(m\). Example 4. Solve a Simple Congruence This example shows how to solve a linear congruence by using an inverse modulo m. Problem. Solve \(4x\equiv3\pmod7\). Solution. Since \(4\cdot2=8\equiv1\pmod7\), multiply both sides by \(2\). Then \(x\equiv6\pmod7\). Example 5. Two Solutions This example shows how to solve a linear congruence by using an inverse modulo m. Problem. Solve \(2x\equiv4\pmod6\). Solution. Testing residues modulo \(6\), \(x=2\) and \(x=5\) work. Thus \(x\equiv2,5\pmod6\). Equivalently, after dividing by \(2\), we get \(x\equiv2\pmod3\), which gives residues \(2\) and \(5\) modulo \(6\). Example 6. Compatible Remainders I This example develops the habit of listing one residue class and checking the second condition. Problem. Find the smallest positive integer \(n\) such that \(n\equiv2\pmod3\) and \(n\equiv1\pmod5\). Solution. The numbers \(1\pmod5\) are \(1,6,11,16,\ldots\). Checking modulo \(3\), we get \(1,0,2,1,\ldots\). The first suitable number is \(11\). Example 7. Polynomial Residue This example shows how reducing the variable first makes polynomial remainders manageable. Problem. If \(n\equiv5\pmod8\), find \(n^2+3n+1\pmod8\). Solution. \(n^2+3n+1\equiv5^2+3\cdot5+1=25+15+1=41\equiv1\pmod8\). Example 8. Congruent Squares This example shows how a congruence identity can be proved by multiplying congruent quantities. Problem. Prove that if \(a\equiv b\pmod m\), then \(a^2\equiv b^2\pmod m\). Solution. Since \(a\equiv b\pmod m\), multiplying both sides by the congruent quantities gives \(a\cdot a\equiv b\cdot b\pmod m\). Hence \(a^2\equiv b^2\pmod m\).

Chapter

Modular Arithmetic II: Linear Congruences and Systems

The module teaches solving linear congruences, using inverses, knowing when division is allowed, checking system compatibility, and constructing numbers with prescribed remainders.

Key Idea A linear congruence \(ax\equiv b\pmod m\) resembles a linear equation, but division is not always allowed. The main question is whether the coefficient \(a\) is compatible with the modulus \(m\). If \(\gcd(a,m)=1\), then \(a\) has an inverse modulo \(m\). If \(\gcd(a,m)>1\), the congruence may have no solutions or several residue classes of solutions. Basic Facts The congruence \(ax\equiv b\pmod m\) has solutions if and only if \(\gcd(a,m)\mid b\). If \(d=\gcd(a,m)\mid b\), divide \(a,b,m\) by \(d\) and solve \(\frac adx\equiv\frac bd\pmod{\frac md}\). If \(\gcd(a,m)=1\), then \(a\) has a multiplicative inverse modulo \(m\). The system \(x\equiv r\pmod m\), \(x\equiv s\pmod n\) is compatible if and only if \(r\equiv s\pmod{\gcd(m,n)}\). If the moduli are coprime, the system has a unique solution modulo the product of the moduli. When to Use This Method A number must be found from several remainders. An expression \(ax+b\) is divisible by \(m\). You must decide whether a congruence may be divided by a common factor. Remainder conditions have non-coprime moduli. A divisibility condition \(f(n)\mid g(n)\) reduces to a variable divisor dividing a constant. How to Recognise the Method If the statement gives several remainders, write a system of congruences immediately. If \(ax\equiv b\pmod m\) appears, first compute \(\gcd(a,m)\), rather than trying to divide by \(a\). For systems with non-coprime moduli, first check compatibility modulo the common divisor of the moduli. Typical Mistakes Dividing \(6x\equiv12\pmod{18}\) by \(6\) while keeping modulus \(18\), losing solutions. Forgetting that one congruence can have several solutions modulo the original modulus. Applying the Chinese remainder theorem to non-coprime moduli without checking compatibility. Finding one solution of a system but not stating the modulus of all solutions. In divisibility problems, failing to check the candidates found. Mini-Checklist What is \(\gcd(a,m)\) in \(ax\equiv b\pmod m\)? Does this GCD divide the right-hand side? Did the modulus change after division? Are the residues compatible modulo common divisors of moduli? Modulo what number should the final answer be written?

Example 1. Multiplicative Inverse If the coefficient is coprime to the modulus, it can be inverted. Problem. Solve \(3x\equiv5\pmod7\). Solution. The inverse of \(3\) modulo \(7\) is \(5\), because \(3\cdot5\equiv1\). Multiply: \(x\equiv5\cdot5=25\equiv4\pmod7\). Comment. This is the correct replacement for division. Example 2. No Solutions Before dividing, check the GCD. Problem. Solve \(6x\equiv5\pmod9\). Solution. \(\gcd(6,9)=3\), but \(3\nmid5\). Therefore the congruence has no solutions. Comment. One GCD check settles the problem. Example 3. Several Solutions If the common divisor divides the right side, several solutions appear. Problem. Solve \(6x\equiv12\pmod{18}\). Solution. Divide \(6,12,18\) by \(6\): \(x\equiv2\pmod3\). Modulo \(18\), this gives \(x\equiv2,5,8,11,14,17\pmod{18}\). Comment. The modulus changed; this is the main source of mistakes. Example 4. A Simple System For coprime moduli, the solution is unique modulo their product. Problem. Solve \(x\equiv2\pmod3\), \(x\equiv3\pmod5\). Solution. The numbers \(2,5,8,11,\ldots\) have residue \(2\) modulo \(3\). Among them, \(8\equiv3\pmod5\). Hence \(x\equiv8\pmod{15}\). Comment. One may search within one residue class. Example 5. Incompatible Conditions Non-coprime moduli require a common-divisor check. Problem. Prove that the system \(x\equiv2\pmod6\), \(x\equiv3\pmod9\) has no solutions. Solution. If \(x\equiv2\pmod6\), then \(x\equiv2\pmod3\). If \(x\equiv3\pmod9\), then \(x\equiv0\pmod3\). One number cannot have two different residues modulo \(3\). No solutions exist. Comment. This is compatibility modulo \(\gcd(6,9)=3\). Example 6. Compatible Non-Coprime Moduli If residues agree modulo the common divisor, the system can be solved. Problem. Solve \(x\equiv4\pmod6\), \(x\equiv10\pmod{15}\). Solution. Both residues are \(1\) modulo \(3\), so the system is compatible. Let \(x=6k+4\). Then \(6k+4\equiv10\pmod{15}\), so \(6k\equiv6\pmod{15}\). Divide by \(3\): \(2k\equiv2\pmod5\), hence \(k\equiv1\pmod5\). Thus \(x\equiv10\pmod{30}\). Comment. The answer is written modulo \(\operatorname{lcm}(6,15)=30\). Example 7. A System from the Statement Sometimes the conditions already contain a hidden contradiction. Problem. Find all \(x\pmod{84}\) such that \(x\equiv2\pmod3\), \(x\equiv3\pmod7\), \(x\equiv4\pmod{12}\). Solution. From \(x\equiv4\pmod{12}\), we get \(x\equiv1\pmod3\). But the first condition requires \(x\equiv2\pmod3\). Contradiction, so there are no solutions. Comment. Check compatibility before computing. Example 8. Divisibility Reduces to a Constant A variable divisor can be forced to divide a small number. Problem. Find all positive \(n\) such that \(2n+1\mid n^2+n+7\). Solution. If \(2n+1\mid n^2+n+7\), then it divides \(4(n^2+n+7)=(2n+1)^2+27\). Hence \(2n+1\mid27\). Since \(n>0\), \(2n+1\in\{3,9,27\}\). Thus \(n=1,4,13\), and all three values work. Comment. This is not a direct congruence, but it leads to a linear restriction.

Chapter

Diophantine Equations

Integer solutions, linear Diophantine equations, factorisation, modular obstructions, and positivity constraints.

1. What Is a Diophantine Equation? A Diophantine equation is an equation where the required solutions are integers, or sometimes positive integers. For example, \[ 3x+5y=17 \] is not just an equation in real numbers. In number theory, we ask for integer pairs \((x,y)\). 2. Linear Diophantine Equations The equation \[ ax+by=c \] has integer solutions if and only if \[ \gcd(a,b)\mid c. \] This condition is necessary because every common divisor of \(a\) and \(b\) divides \(ax+by\). It is also sufficient because the Euclidean algorithm can write \(\gcd(a,b)\) as a linear combination of \(a\) and \(b\). 3. General Solutions If \((x_0,y_0)\) is one solution of \(ax+by=c\), and \(g=\gcd(a,b)\), then all integer solutions are \[ x=x_0+\frac{b}{g}t,\qquad y=y_0-\frac{a}{g}t, \] where \(t\) is an integer. 4. Factorisation Method Many Diophantine equations become easier after factorisation: \[ xy+x+y=11 \] can be rewritten as \[ (x+1)(y+1)=12. \] Then integer factors of \(12\) give the solutions. 5. Modular Obstructions Sometimes an equation has no integer solutions because of remainders. For example, \(x^2=3y+2\) has no solution if \(x^2\) cannot be congruent to \(2\pmod3\). Modular arithmetic can prove impossibility quickly. 6. Nonnegative and Positive Solutions Olympiad problems often ask for positive or nonnegative solutions. After finding a parametric form, the inequalities restrict the parameter.

Example 1. Integer Solution Check This is the first obstruction: the GCD must divide the constant. Problem. Decide whether \(6x+10y=15\) has integer solutions. Solution. \(\gcd(6,10)=2\). The left side is always even, but \(15\) is odd. Therefore there are no integer solutions. Example 2. One Bezout Solution Connect directly to the Euclidean algorithm from Module 2. Problem. Find one integer solution of \(3x+5y=1\). Solution. Since \(2\cdot3-1\cdot5=1\), one solution is \((x,y)=(2,-1)\). Example 3. All Linear Solutions Stress that the parameter moves along the line without changing the value. Problem. Find all integer solutions of \(3x+5y=17\). Solution. One solution is \((4,1)\), because \(3\cdot4+5\cdot1=17\). Since \(\gcd(3,5)=1\), all solutions are \(x=4+5t\), \(y=1-3t\), where \(t\in\mathbb Z\). Example 4. A Factor Pair Equation Factor-pair problems train completeness. Problem. Solve \(xy=18\) in positive integers. Solution. The positive factor pairs are \((1,18),(2,9),(3,6),(6,3),(9,2),(18,1)\). Example 5. Complete the Product This is a central olympiad factorisation trick. Problem. Solve \(xy+x+y=11\) in positive integers. Solution. We rewrite as \((x+1)(y+1)=12\). Since \(x,y>0\), both factors are at least \(2\). The factor pairs are \((2,6),(3,4),(4,3),(6,2)\), giving \((x,y)=(1,5),(2,3),(3,2),(5,1)\). Example 6. Difference of Squares Watch for missing negative factor pairs. Problem. Find all integer solutions of \(x^2-y^2=15\). Solution. Let \(a=x-y\), \(b=x+y\). Then \(ab=15\), and \(a,b\) have the same parity. Since \(15\) is odd, factor pairs are odd: \((1,15),(3,5),(5,3),(15,1)\) and their negatives. From \(x=(a+b)/2\), \(y=(b-a)/2\), we get \((8,7),(4,1),(4,-1),(8,-7)\) and the four corresponding negative pairs \((-8,-7),(-4,-1),(-4,1),(-8,7)\). Example 7. Modulo Obstruction This problem links Module 4 to Diophantine equations. Problem. Prove that \(x^2+y^2=4z+3\) has no integer solutions. Solution. Squares are \(0\) or \(1\pmod4\). Therefore \(x^2+y^2\) can be \(0,1,\) or \(2\pmod4\), but \(4z+3\equiv3\pmod4\). Contradiction. Example 8. A Product Plus Sum Students may need help choosing the shifted factors. Problem. Find all integer solutions of \(xy-2x+3y=7\). Solution. We have \((x+3)(y-2)=xy-2x+3y-6\). Since \(xy-2x+3y=7\), this gives \((x+3)(y-2)=1\). Thus \((x+3,y-2)=(1,1)\) or \((-1,-1)\). The solutions are \((-2,3)\) and \((-4,1)\).

Chapter

Diophantine Equations I: Factorisation and Bounds

The module teaches first olympiad-style Diophantine equations: linear equations, completing a product, difference of squares, reciprocal equations, modular obstructions, and bounds.

Key Idea A Diophantine equation is an equation in which integer or positive integer solutions are required. One cannot simply solve over the real numbers and ignore the integer condition: every transformation must preserve integrality. The main idea of this first module is to turn the equation into a form where divisibility, factors, residues, or bounds become visible. Often we should not expand; instead, we add the missing term and obtain a product. Basic Facts The linear equation \(ax+by=c\) has integer solutions if and only if \(\gcd(a,b)\mid c\). If \(x_0,y_0\) is one solution of \(ax+by=c\), then all solutions are \(x=x_0+\frac{b}{d}t\), \(y=y_0-\frac{a}{d}t\), where \(d=\gcd(a,b)\) and \(t\in\mathbb Z\). An equation of the form \(xy+ax+by=c\) is often solved by adding \(ab\): \((x+b)(y+a)=c+ab\). The equation \(x^2-y^2=n\) becomes \((x-y)(x+y)=n\). The two factors must have the same parity. If the right-hand side is small and the variables are positive, use bounds: a product grows faster than a sum. If an expression cannot have the required residue modulo \(m\), then there are no solutions. When to Use This Method The problem asks for integer or positive integer solutions. The equation contains a product \(xy\), a sum \(x+y\), a difference of squares, or a fraction such as \(\frac{1}{x}+\frac{1}{y}\). You need to prove that there are no solutions, and parity or quadratic residues are visible. The number of possible values can be sharply limited by an inequality. After transformation, one side becomes a product of two integer factors with known value. How to Recognise the Method If you see \(xy+ax+by\), try adding \(ab\). If you see \(x^2-y^2\), immediately factor it as \((x-y)(x+y)\). If you see \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\), multiply by \(nxy\) and complete the product \((x-n)(y-n)=n^2\). If the equation seems too flexible, check residues modulo small moduli \(2,3,4,8\). If the variables are positive, order them, for example \(x\le y\), and derive an upper bound. Typical Mistakes Dividing a linear equation by a number without checking that the whole right-hand side is divisible. After factorising \(AB=n\), forgetting negative factors or the positivity condition. In \(x^2-y^2=n\), taking arbitrary factor pairs of \(n\) without checking that \(x-y\) and \(x+y\) have the same parity. When completing a product, adding a term to one side but not to the other. In positive-integer problems, finding integer parameters but not selecting the positive values. Mini-Checklist Which solutions are required: integer, positive integer, or nonnegative? Can the equation be turned into a product of two integer factors? Is there a parity condition on the factors? Can we first prove impossibility modulo a small number? If there are many solutions, can they be written parametrically? If there are finitely many solutions, which bound limits the search?

Example 1. A Linear Equation in Integers The first skill is to check the GCD and write all solutions with a parameter. Problem. Solve the equation \(6x+10y=14\) in integers. Solution. Since \(\gcd(6,10)=2\) and \(2\mid14\), solutions exist. Divide by \(2\): \(3x+5y=7\). One solution is \(x=-1\), \(y=2\), because \(3(-1)+5\cdot2=7\). All solutions are \(x=-1+5t\), \(y=2-3t\), where \(t\in\mathbb Z\). Comment. The coefficients \(5\) and \(3\) in the parameters come from the coprime coefficients \(3\) and \(5\). Example 2. Positive Solutions of a Linear Equation After the general method, we must be able to select only positive solutions. Problem. Find all positive integer solutions of \(3x+5y=41\). Solution. Consider the equation modulo \(3\): \(5y\equiv 41\pmod3\), so \(2y\equiv2\pmod3\). Hence \(y\equiv1\pmod3\). Since \(y>0\) and \(5y<41\), we get \(y\in\{1,4,7\}\). Then \(x=\frac{41-5y}{3}\), giving the solutions \((12,1)\), \((7,4)\), \((2,7)\). Comment. A congruence modulo one coefficient quickly removes unnecessary search. Example 3. Completing a Product The expression \(xy+x+y\) is almost the product \((x+1)(y+1)\). Problem. Find all positive integers \(x,y\) such that \(xy+x+y=35\). Solution. Add \(1\) to both sides: \(xy+x+y+1=36\), hence \((x+1)(y+1)=36\). Now \(x+1\) and \(y+1\) are positive divisors of \(36\), and both are at least \(2\). Therefore the pairs \((x,y)\) are \((1,17)\), \((2,11)\), \((3,8)\), \((5,5)\), \((8,3)\), \((11,2)\), \((17,1)\). Comment. The main idea is to notice the missing \(1\). Example 4. Difference of Squares Factoring \(x^2-y^2\) also requires checking the parity of the factors. Problem. Find all positive integer solutions of \(x^2-y^2=45\). Solution. We have \((x-y)(x+y)=45\). Both factors are positive and have the same parity, because their sum is \(2x\). Since \(45\) is odd, both factors must be odd. Take the factor pairs of \(45\): \((1,45)\), \((3,15)\), \((5,9)\). They give respectively \((x,y)=(23,22)\), \((9,6)\), \((7,2)\). Comment. The pair \((x-y,x+y)\) determines \(x\) and \(y\) uniquely. Example 5. An Equation with Reciprocals A fractional equation often becomes a product after multiplying by a common denominator. Problem. Find all positive integers \(x,y\) such that \(\frac{1}{x}+\frac{1}{y}=\frac{1}{6}\). Solution. Multiply by \(6xy\): \(6x+6y=xy\). Move terms and complete a product: \(xy-6x-6y=0\), so \((x-6)(y-6)=36\). If \(d\) is a positive divisor of \(36\), then \(x=6+d\), \(y=6+\frac{36}{d}\). This gives all solutions. Comment. This move is often called completing a rectangle. Example 6. A Hidden Product The coefficients of \(x\) and \(y\) indicate exactly what must be added. Problem. Find all positive integer solutions of \(xy=3x+4y\). Solution. Rewrite as \(xy-3x-4y=0\). Add \(12\): \((x-4)(y-3)=12\). Let \(d\mid12\), \(d>0\). Then \(x=4+d\), \(y=3+\frac{12}{d}\). For \(d=1,2,3,4,6,12\), we obtain all positive solutions. Comment. We do not need to guess \(x\) and \(y\); after factorisation only divisors remain. Example 7. A Modular Obstruction Sometimes it is better to prove first that no solutions can exist. Problem. Prove that the equation \(x^2+y^2=8z+6\) has no integer solutions. Solution. A square modulo \(8\) can only have residue \(0,1,4\). Therefore a sum of two squares modulo \(8\) can only have residues \(0,1,2,4,5\). The right-hand side \(8z+6\) has residue \(6\) modulo \(8\), which is impossible for a sum of two squares. Hence there are no integer solutions. Comment. Modulo \(8\) is especially useful for squares and parity. Example 8. Bounding Instead of Long Search If a product divides a small sum, positivity sharply limits the possibilities. Problem. Find all positive integers \(x,y\) such that \(xy\mid x+y+1\). Solution. The condition is symmetric, so assume \(x\le y\). Then \(xy\le x+y+1\). If \(x\ge3\), then \(xy\ge3y\), while \(x+y+1\le2y+1\), impossible for \(y\ge3\). Thus \(x=1\) or \(x=2\). For \(x=1\), we get \(y\mid y+2\), so \(y\mid2\), hence \(y=1,2\). For \(x=2\), \(2y\mid y+3\), so \(y\le3\); checking \(y=2,3\) leaves only \(y=3\). By symmetry, the solutions are \((1,1)\), \((1,2)\), \((2,1)\), \((2,3)\), \((3,2)\). Comment. The bound tells us which small cases actually need checking.

Chapter

Infinite Descent

Infinite descent, parity lemmas, minimal counterexamples, primitive solutions, and contradiction by smaller solutions.

1. The Main Idea Infinite descent is a proof method. We assume that a positive integer solution exists, then construct a smaller positive integer solution of the same type. Repeating this forever is impossible, because positive integers cannot decrease forever. The typical structure is: Assume a solution exists. Choose one with a smallest positive measure. Prove that this solution forces a smaller solution. Contradiction. 2. Descent and Parity Many descent arguments begin with parity. If \(x^2\) is even, then \(x\) is even. This can force both variables to be divisible by \(2\), creating a smaller solution after division. 3. Example: \(x^2=2y^2\) Suppose \(x^2=2y^2\) has a nonzero integer solution. Then \(x^2\) is even, so \(x=2k\). Substituting: \[ 4k^2=2y^2,\qquad y^2=2k^2. \] So \(y\) is even too. Thus both \(x\) and \(y\) are even, and dividing by \(2\) gives a smaller solution. Repeating is impossible. Therefore the only integer solution is \((0,0)\). 4. Minimal Counterexample Often we assume a smallest counterexample. If the argument creates a smaller counterexample, the original one could not have existed. 5. Descent in Olympiad Problems Descent usually appears when: an equation forces all variables to share a factor; a minimal solution can be transformed into a smaller one; parity or modular residues repeat after scaling; a "smallest" object produces an even smaller object.

Example 1. Even Square This lemma is used repeatedly in descent arguments. Problem. Prove that if \(n^2\) is even, then \(n\) is even. Solution. If \(n\) is odd, then \(n=2k+1\). Hence \(n^2=4k^2+4k+1\), which is odd. Therefore if \(n^2\) is even, \(n\) cannot be odd, so \(n\) is even. Example 2. First Descent This is the model descent proof for the whole module. Problem. Show that the only integer solution of \(x^2=2y^2\) is \((0,0)\). Solution. Suppose a nonzero solution exists. Since \(x^2=2y^2\), \(x^2\) is even, so \(x=2k\). Then \(4k^2=2y^2\), hence \(y^2=2k^2\), so \(y\) is even. Thus both \(x\) and \(y\) are even, and dividing by \(2\) gives a smaller nonzero solution. Repeating forever is impossible. Hence only \((0,0)\) works. Example 3. Irrational Square Root Make explicit that lowest terms means not both even. Problem. Use infinite descent to prove that \(\sqrt2\) is irrational. Solution. If \(\sqrt2=a/b\), then \(a^2=2b^2\). By the previous descent idea, \(a\) and \(b\) must both be even. This contradicts the assumption that the fraction was in lowest terms. Therefore \(\sqrt2\) is irrational. Example 4. Descent by Three Use this to generalize the \(2\)-descent idea. Problem. Prove that the only integer solution of \(x^2=3y^2\) is \((0,0)\). Solution. If \(x^2=3y^2\), then \(3\mid x^2\), so \(3\mid x\). Write \(x=3k\). Then \(9k^2=3y^2\), so \(y^2=3k^2\), hence \(3\mid y\). Dividing both variables by \(3\) gives a smaller nonzero solution, impossible by descent. Thus only \((0,0)\) works. Example 5. No Sum of Squares This is the first three-variable descent in the course. Problem. Prove that the only integer solution of \(x^2+y^2=3z^2\) is \((0,0,0)\). Solution. Modulo \(3\), the right side is \(0\). Since square residues are \(0\) and \(1\), the only way \(x^2+y^2\equiv0\pmod3\) is \(x^2\equiv y^2\equiv0\pmod3\). Thus \(3\mid x\) and \(3\mid y\). Then the equation gives \(3\mid z\) as well. Dividing all variables by \(3\) gives a smaller nonzero solution, impossible by descent. Hence only \((0,0,0)\) works. Example 6. Minimal Counterexample This is the logic foundation behind the method. Problem. Explain why there cannot be a nonempty set of positive integers with no smallest element. Solution. The positive integers are well ordered: every nonempty set of positive integers has a smallest element. Infinite descent uses the contrapositive spirit: if every supposed element produces a smaller positive element, no such set can exist. Example 7. Descent Chain This abstract problem helps students name the proof skeleton. Problem. Suppose a positive integer \(n\) has a property \(P\), and every positive integer with property \(P\) gives a smaller positive integer with property \(P\). Prove that no positive integer has property \(P\). Solution. If such integers exist, choose the smallest one, say \(n\). By the property, \(n\) gives a smaller positive integer with property \(P\), contradicting the minimality of \(n\). Therefore no positive integer has property \(P\). Example 8. Divisible by All Powers This justifies the phrase divisible by arbitrarily large powers. Problem. Prove that if an integer \(n\) is divisible by \(2^k\) for every positive integer \(k\), then \(n=0\). Solution. If \(n\ne0\), choose \(k\) with \(2^k>|n|\). A nonzero multiple of \(2^k\) has absolute value at least \(2^k\), impossible because \(|n|<2^k\). Thus \(n=0\).

Chapter

Infinite Descent I

The module introduces infinite descent: minimal counterexamples, descent by parity and prime divisor, irrationality of square roots, modular obstructions, primitive solutions, and a first Vieta-descent preview.

Key Idea Infinite descent proves impossibility as follows: assume that a positive integer solution exists, choose the smallest one according to some parameter, and then construct an even smaller positive solution from it. This contradicts the fact that positive integers cannot decrease forever. In this first descent module, the main sources of decrease are parity, divisibility by a prime, a common factor, and passing from a solution to a primitive solution. Basic Facts If \(a^2\) is even, then \(a\) is even. If \(p\mid a^2\) for a prime \(p\), then \(p\mid a\). If a solution \((x,y)\) forces both \(x\) and \(y\) to have a common divisor \(d>1\), then often dividing by \(d\) gives a smaller solution. To prove that \(\sqrt{n}\) is irrational, assume \(\sqrt{n}=\frac{a}{b}\) in lowest terms and derive a common divisor of \(a\) and \(b\). For equations with sums of squares, quadratic residues modulo \(3,5,7,8\) are useful. In descent, it is essential to state which quantity decreases: \(x+y\), \(z\), \(\max(x,y)\), or the denominator of a fraction. When to Use This Method You need to prove that there are no integer or positive integer solutions. The equation implies that all variables are divisible by the same prime. The condition remains the same after dividing all variables by a common factor. A modular check gives not an immediate contradiction, but forced common divisibility. The problem concerns irrationality of a square root or impossibility of a quadratic equation in integers. How to Recognise the Method If reducing modulo \(p\) gives \(p\mid x\), \(p\mid y\), \(p\mid z\), ask whether dividing all variables by \(p\) produces the same equation. If yes, the descent is almost ready. If the problem says “prove that there are no solutions” and a simple residue check does not finish the problem, try choosing a solution with minimal sum of variables and constructing a smaller one. Typical Mistakes Saying “we get infinite descent” without showing the actual smaller solution. Dividing by a common factor without checking that the new solution remains integral and positive. In irrationality proofs, forgetting to start with a fraction in lowest terms. From \(p\mid a^2\), claiming \(p^2\mid a^2\) without first explaining \(p\mid a\). Using a “minimal solution” without naming the parameter of minimality. Mini-Checklist What is assumed to exist: a positive solution, a nonzero solution, or a rational fraction? Which parameter is chosen minimal? Which modular check forces the variables to be divisible by one prime? After division, do we get exactly the same equation? Is the new solution strictly smaller than the old one? Where exactly is the contradiction with minimality?

Example 1. An Even Square The smallest brick of descent is passing from divisibility of a square to divisibility of the number. Problem. Prove that if \(a^2\) is even, then \(a\) is even. Solution. Argue by contradiction. If \(a\) is odd, then \(a=2k+1\). Thus \(a^2=4k^2+4k+1=2(2k^2+2k)+1\), so \(a^2\) is odd. Contradiction. Hence \(a\) is even. Comment. This is exactly the step that starts the classical proof of irrationality of \(\sqrt{2}\). Example 2. The Equation \(x^2=2y^2\) Here we see how one positive solution produces a smaller one. Problem. Prove that the equation \(x^2=2y^2\) has no positive integer solutions. Solution. Suppose a solution exists. Then \(x^2\) is even, so \(x\) is even: \(x=2u\). Substitute: \(4u^2=2y^2\), so \(y^2=2u^2\). Then \(y^2\) is even, so \(y\) is even: \(y=2v\). We get a new solution \(u^2=2v^2\), with \(u=\frac{x}{2} Comment. Equivalently, choose a solution with minimal \(x+y\) and get an immediate contradiction. Example 3. Irrationality of \(\sqrt{2}\) The lowest-terms fraction proof is the same descent idea in rational-number language. Problem. Prove that \(\sqrt{2}\) is irrational. Solution. Suppose \(\sqrt{2}=\frac{a}{b}\), where \(a,b\) are positive integers and the fraction is in lowest terms. Then \(a^2=2b^2\). By the previous reasoning, \(a\) is even, so \(a=2c\). Then \(4c^2=2b^2\), hence \(b^2=2c^2\), and \(b\) is also even. Thus \(a\) and \(b\) have common divisor \(2\), contradicting that the fraction was in lowest terms. Therefore \(\sqrt{2}\) is irrational. Comment. The key is to start with a fraction in lowest terms. Example 4. A Prime Divides a Square Descent by a prime divisor needs a general fact about squares. Problem. Let \(p\) be prime. Prove that if \(p\mid a^2\), then \(p\mid a\). Solution. If \(p\nmid a\), then \(\gcd(p,a)=1\). Then \(p\) divides neither factor in \(a\cdot a\), which is impossible for a prime \(p\) if \(p\mid a^2\). Therefore \(p\mid a\). Comment. This is a direct application of Euclid's lemma. Example 5. Descent in a Sum of Squares Sometimes a modulus gives not an immediate contradiction, but forced common divisibility. Problem. Prove that the equation \(x^2+y^2=3z^2\) has no positive integer solutions. Solution. Modulo \(3\), a square is \(0\) or \(1\). If \(x^2+y^2\equiv0\pmod3\), then both squares must be \(0\) modulo \(3\). Thus \(3\mid x\) and \(3\mid y\). Let \(x=3x_1\), \(y=3y_1\). Then \(9x_1^2+9y_1^2=3z^2\), so \(3x_1^2+3y_1^2=z^2\). Hence \(3\mid z^2\), and \(3\mid z\). Dividing all variables by \(3\) gives a smaller positive solution of the same equation. Infinite descent is impossible. Comment. The decreasing quantity can be \(x+y+z\). Example 6. Reducing to a Forbidden Equation Some equations need no new descent: they reduce to a basic impossible case. Problem. Prove that \(x^2=8y^2\) has no positive integer solutions. Solution. If \(x^2=8y^2\), then \(x^2\) is even, so \(x=2u\). Then \(4u^2=8y^2\), hence \(u^2=2y^2\). But the equation \(u^2=2y^2\) has no positive integer solutions. Contradiction. Comment. The strong move is noticing a familiar forbidden form. Example 7. A Minimal Counterexample Descent is often cleanest when formulated using a minimal solution. Problem. Show how to prove impossibility of \(x^2=2y^2\) by choosing a solution with minimal \(x+y\). Solution. Assume positive solutions exist, and choose one \((x,y)\) with minimal sum \(x+y\). As in Example 2, \(x^2=2y^2\) implies that both \(x\) and \(y\) are even. Then \(\left(\frac{x}{2},\frac{y}{2}\right)\) is a new positive solution. Its sum is \(\frac{x+y}{2}\), which is smaller than \(x+y\). This contradicts the minimality of the chosen solution. Comment. This format is especially useful in harder problems. Example 8. First Vieta-Descent Preview Sometimes the smaller solution comes not from division, but from replacing one root of a quadratic equation. Problem. Prove that the equation \(x^2+y^2=3xy\) has no positive integer solutions. Solution. Suppose a solution exists, and choose one with minimal \(x+y\). Let \(x>y\); the case \(x=y\) is impossible. View the equation as a quadratic in \(x\): \(x^2-3yx+y^2=0\). The second root is \(x'=3y-x\). By Vieta's formulas, \(xx'=y^2\), so \(x'>0\). Since \(x>y\), we have \(x'=\frac{y^2}{x} Comment. This is only a preview; full Vieta jumping belongs to the next book.

Chapter

Fermat and Euler

Fermat's Little Theorem, Euler's totient function, Euler's theorem, modular inverses, and large power computations.

1. Fermat's Little Theorem If \(p\) is prime and \(p\nmid a\), then \[ a^{p-1}\equiv1\pmod p. \] Equivalently, for every integer \(a\), \[ a^p\equiv a\pmod p. \] This theorem is a powerful way to reduce large powers modulo a prime. 2. Modular Inverses If \(\gcd(a,m)=1\), then \(a\) has an inverse modulo \(m\). That means there is an integer \(b\) such that \[ ab\equiv1\pmod m. \] Fermat's theorem gives a useful inverse modulo a prime: \[ a^{-1}\equiv a^{p-2}\pmod p. \] 3. Euler's Totient Function Euler's totient function \(\varphi(n)\) counts the positive integers from \(1\) to \(n\) that are relatively prime to \(n\). For example, \[ \varphi(10)=4, \] because \(1,3,7,9\) are relatively prime to \(10\). If \[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \] then \[ \varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right). \] 4. Euler's Theorem If \(\gcd(a,n)=1\), then \[ a^{\varphi(n)}\equiv1\pmod n. \] Fermat's Little Theorem is the special case when \(n\) is prime. 5. Strategy for Large Powers To compute \(a^k\pmod n\): Check whether \(\gcd(a,n)=1\). If yes, reduce the exponent modulo \(\varphi(n)\), or use a shorter cycle. If not, use direct factorisation, prime powers, or another modulus.

Example 1. Fermat Modulo Five This is the cleanest first FLT computation. Problem. Find \(3^{2026}\pmod5\). Solution. By Fermat's theorem, \(3^4\equiv1\pmod5\). Since \(2026\equiv2\pmod4\), \(3^{2026}\equiv3^2=9\equiv4\pmod5\). Example 2. Fast Power Modulo Seven Short cycles may be better than a theorem. Problem. Find \(2^{100}\pmod7\). Solution. Since \(2^3=8\equiv1\pmod7\), reduce the exponent modulo \(3\). Since \(100\equiv1\pmod3\), \(2^{100}\equiv2\pmod7\). Example 3. Totient by Listing Listing before formula keeps the function meaningful. Problem. Find \(\varphi(12)\) by listing the positive integers from \(1\) to \(12\) that are coprime to \(12\). Solution. The numbers are \(1,5,7,11\). Hence \(\varphi(12)=4\). Example 4. Totient Formula Require prime factorisation before applying the formula. Problem. Find \(\varphi(45)\). Solution. \(\varphi(45)=45\left(1-\frac13\right)\left(1-\frac15\right)=45\cdot\frac23\cdot\frac45=24\). Example 5. Euler Modulo Ten Connect Euler theorem to familiar last-digit work. Problem. Find the last digit of \(7^{100}\). Solution. Euler's theorem gives \(7^4\equiv1\pmod{10}\). Since \(100\equiv0\pmod4\), \(7^{100}\equiv1\pmod{10}\). The last digit is \(1\). Example 6. Inverse Modulo Eleven Do this by inspection before using Fermat's formula. Problem. Find the inverse of \(3\) modulo \(11\). Solution. \(3\cdot4=12\equiv1\pmod{11}\), so the inverse is \(4\). Example 7. Fermat Inverse This is conceptually important for solving congruences. Problem. Use Fermat's Little Theorem to explain why \(a^{p-2}\) is an inverse of \(a\pmod p\) when \(p\) is prime and \(p\nmid a\). Solution. By Fermat's theorem, \(a^{p-1}\equiv1\pmod p\). But \(a\cdot a^{p-2}=a^{p-1}\), so \(a\cdot a^{p-2}\equiv1\pmod p\). Therefore \(a^{p-2}\) is an inverse of \(a\pmod p\). Example 8. Euler Power Again, short cycles are often more efficient than full Euler theorem. Problem. Find \(5^{123}\pmod8\). Solution. Since \(5^2=25\equiv1\pmod8\), odd powers of \(5\) are congruent to \(5\pmod8\). Hence \(5^{123}\equiv5\pmod8\).

Chapter

Fermat, Euler and Power Cycles

The module teaches how to work with large powers modulo an integer: short cycles, Fermat's little theorem, Euler's theorem, order of an element, modular inverses, and first restrictions on prime divisors of power expressions.

Key Idea Powers modulo a number do not grow forever: residues begin to repeat. The olympiad task is usually not to “compute a huge power”, but to choose the right period: a short cycle, Fermat's little theorem, Euler's theorem, or the order of an element. First look for a short cycle. If the modulus is prime, check Fermat. If the modulus is composite and the base is coprime to it, use Euler or split the modulus into parts. Basic Facts If \(p\) is prime and \(p\nmid a\), then \(a^{p-1}\equiv1\pmod p\). For every prime \(p\), \(a^p\equiv a\pmod p\). If \(\gcd(a,m)=1\), then \(a^{\varphi(m)}\equiv1\pmod m\). The order \(\operatorname{ord}_m(a)\) is the least positive \(t\) such that \(a^t\equiv1\pmod m\). If \(a^n\equiv1\pmod m\), then \(\operatorname{ord}_m(a)\mid n\). For the last two digits work modulo \(100\); for the last digit work modulo \(10\). When to Use This Method You need the residue of a large power. You need to prove divisibility such as \(m\mid a^n-1\) or \(m\mid a^n-a\). The problem contains a prime divisor of an expression with powers. You need a modular inverse \(a^{-1}\pmod p\). The modulus is composite, but the base is coprime to it. How to Recognise the Method If the exponent is huge, reduce it modulo a period. If the modulus is a prime \(p\), the period often divides \(p-1\). If the modulus is composite, first check \(\gcd(a,m)=1\); otherwise Euler's theorem is not available. If a prime \(p\mid a^k-1\) appears, move to the order of \(a\) modulo \(p\). The order divides both \(k\) and \(p-1\), which often strongly restricts \(p\). Typical Mistakes Applying Fermat's theorem to a composite modulus. Applying Euler's theorem when the base is not coprime to the modulus. Reducing the exponent by the wrong period, for example by \(\varphi(m)\) when a shorter cycle is known. For last-two-digit problems, working only modulo \(10\). Writing \(a^{p-1}\equiv1\pmod p\) without checking \(p\nmid a\). Mini-Checklist Which modulus is needed: \(10\), \(100\), a prime \(p\), or a composite \(m\)? Is the base coprime to the modulus? Is there a short cycle better than Euler? What is the exponent modulo the period? If a prime divisor is involved, what order appears? Should the modulus be split using CRT?

Example 1. A Short Cycle Sometimes the period is visible faster than any big theorem. Problem. Find the remainder of \(3^{20}\) modulo \(7\). Solution. We have \(3^1\equiv3\), \(3^2\equiv2\), \(3^3\equiv6\), \(3^6\equiv1\pmod7\). Since \(20\equiv2\pmod6\), \(3^{20}\equiv3^2\equiv2\pmod7\). Comment. The period is \(6\), but it was enough to find the return to \(1\). Example 2. Last Digit The last digit is the residue modulo \(10\). Problem. Find the last digit of \(7^{2026}\). Solution. The last digits of powers of \(7\) are \(7,9,3,1\), then the cycle repeats. The period is \(4\). Since \(2026\equiv2\pmod4\), the last digit is the second digit of the cycle, namely \(9\). Comment. No need to compute the power; only the exponent modulo the period matters. Example 3. Fermat's Little Theorem For a prime modulus, the exponent \(p-1\) often neutralises the problem. Problem. Prove that \(11\mid 2^{10}-1\). Solution. Since \(11\) is prime and \(11\nmid2\), Fermat's little theorem gives \(2^{10}\equiv1\pmod{11}\). Therefore \(11\mid2^{10}-1\). Comment. It is important to check that the base is not divisible by \(11\). Example 4. Reducing the Exponent Fermat lets us replace a large exponent by its remainder modulo \(p-1\). Problem. Find the remainder of \(5^{100}\) modulo \(13\). Solution. By Fermat, \(5^{12}\equiv1\pmod{13}\). Since \(100\equiv4\pmod{12}\), \(5^{100}\equiv5^4\pmod{13}\). Also \(5^2=25\equiv-1\pmod{13}\), so \(5^4\equiv1\pmod{13}\). Comment. Sometimes after Fermat a small convenient square remains. Example 5. Last Two Digits For the last two digits we work modulo \(100\), not only modulo \(10\). Problem. Find the last two digits of \(7^{100}\). Solution. Since \(\gcd(7,100)=1\), we can look for a cycle. Notice that \(7^2=49\), and \(7^4\equiv49^2=2401\equiv1\pmod{100}\). Hence \(7^{100}=(7^4)^{25}\equiv1\pmod{100}\). The last two digits are \(01\). Comment. A short cycle is better than Euler's theorem here. Example 6. When Euler Works For a composite modulus, coprimality must be checked. Problem. Find the remainder of \(3^{100}\) modulo \(35\). Solution. \(\gcd(3,35)=1\), so Euler's theorem applies. \(\varphi(35)=\varphi(5)\varphi(7)=4\cdot6=24\). Since \(100\equiv4\pmod{24}\), we get \(3^{100}\equiv3^4=81\equiv11\pmod{35}\). Comment. If the base and modulus were not coprime, this move would be illegal. Example 7. Order of an Element The order is the true period of powers returning to \(1\). Problem. Find the order of \(2\) modulo \(9\). Solution. Compute: \(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\), \(2^4\equiv7\), \(2^5\equiv5\), \(2^6\equiv1\pmod9\). Since \(1\) did not occur earlier, \(\operatorname{ord}_9(2)=6\). Comment. After this, \(2^n\equiv1\pmod9\) if and only if \(6\mid n\). Example 8. Modular Inverse via Fermat Fermat gives inverses modulo a prime. Problem. Find the inverse of \(4\) modulo \(17\). Solution. By Fermat, \(4^{16}\equiv1\pmod{17}\), so \(4^{15}\) is an inverse of \(4\). But direct computation is shorter: \(4\cdot13=52\equiv1\pmod{17}\). Therefore the inverse is \(13\). Comment. The theorem explains existence, but a short calculation is often faster.

Chapter

Chinese Remainder Theorem

The module develops CRT as a method for solving systems of congruences and as an olympiad construction tool: compatibility, non-coprime moduli, shifts, blocks of composite numbers, and constructions with prescribed divisors.

Key Idea The Chinese Remainder Theorem lets us construct a number with several prescribed residues at once. In olympiad problems it is not only a way to solve systems of congruences, but also a method for constructing numbers with planned divisibility. If the moduli are pairwise coprime, the system has a unique solution modulo the product of the moduli. If the moduli are not coprime, compatibility of residues modulo common divisors must be checked first. Basic Facts If \(\gcd(m,n)=1\), then \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) has a unique solution modulo \(mn\). For several pairwise coprime moduli, the solution is unique modulo their product. The system \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) is compatible if and only if \(a\equiv b\pmod{\gcd(m,n)}\). If one solution \(x_0\) is found, all solutions are \(x=x_0+k\operatorname{lcm}(m_1,\ldots,m_s)\). Conditions of the form \(d\mid n+r\) are conveniently rewritten as \(n\equiv-r\pmod d\). When to Use This Method You need a number with several prescribed residues. You need to prove existence of a number with prescribed divisibility of \(n+a_i\). A large modulus splits into coprime parts. You need to construct a counterexample or an infinite family of numbers. You need to prove that a system of congruences is impossible because of a common-divisor conflict. How to Recognise the Method If the problem simultaneously says “when divided by \(3\)”, “when divided by \(5\)”, and “divisible by \(7\)”, translate the conditions into a system of congruences. If numbers \(n+1,n+2,\ldots\) must have different divisors, write one congruence for each shift. Before solving the system, inspect the moduli. Pairwise coprimality gives direct CRT; common divisors require compatibility checks. Typical Mistakes Multiplying moduli immediately even though they are not coprime. Forgetting that the answer is modulo the LCM, not necessarily modulo the product. Writing \(n\equiv r\pmod d\) instead of \(n\equiv-r\pmod d\) from \(d\mid n+r\). Finding one solution but not describing all solutions. In constructions, forgetting to check that the constructed numbers are larger than their nontrivial divisors. Mini-Checklist Have all conditions been written as congruences? Are the moduli pairwise coprime? If not, are the residues compatible modulo the GCD? What is the final modulus of the answer: product or LCM? Do we need the smallest positive solution or all solutions? If this is a construction, why does it give infinitely many numbers?

Example 1. Two Coprime Moduli Basic CRT: substitute one congruence into the other. Problem. Solve \(x\equiv2\pmod3\), \(x\equiv3\pmod5\). Solution. Let \(x=3k+2\). Then \(3k+2\equiv3\pmod5\), so \(3k\equiv1\pmod5\). Multiplying by the inverse \(2\) of \(3\), \(k\equiv2\pmod5\). Thus \(x=3(5t+2)+2=15t+8\). The answer is \(x\equiv8\pmod{15}\). Comment. The moduli \(3\) and \(5\) are coprime, so the answer is unique modulo \(15\). Example 2. Compatible Non-Coprime Moduli If moduli have a common divisor, check residues first. Problem. Solve \(x\equiv4\pmod6\), \(x\equiv1\pmod9\). Solution. The common divisor of \(6\) and \(9\) is \(3\). The residues \(4\) and \(1\) are congruent modulo \(3\), so the system is compatible. Let \(x=6k+4\). Then \(6k+4\equiv1\pmod9\), so \(6k\equiv6\pmod9\). Divide by \(3\): \(2k\equiv2\pmod3\), hence \(k\equiv1\pmod3\). Therefore \(x\equiv10\pmod{18}\). Comment. The answer is modulo \(\operatorname{lcm}(6,9)=18\). Example 3. Incompatibility Sometimes CRT is used to quickly prove that no solution exists. Problem. Prove that \(x\equiv2\pmod6\), \(x\equiv4\pmod9\) has no solutions. Solution. The first congruence gives \(x\equiv2\pmod3\). The second gives \(x\equiv1\pmod3\). One number cannot have two different residues modulo \(3\). Hence there are no solutions. Comment. This is exactly the GCD compatibility check. Example 4. Constructing a Number CRT constructs a number with prescribed residues without searching a large range. Problem. Find the smallest positive \(n\) such that \(n\equiv1\pmod2\), \(n\equiv2\pmod3\), \(n\equiv3\pmod5\). Solution. Check numbers \(n\equiv3\pmod5\): \(3,8,13,18,23,\ldots\). Among them, \(n\equiv2\pmod3\) holds for \(8,23,\ldots\). The first odd one is \(23\). The answer is \(23\). All solutions are \(n\equiv23\pmod{30}\). Comment. For small moduli, careful hand search is fine. Example 5. Infinitely Many Solutions Once one solution is found, we automatically get an infinite family. Problem. Prove that there are infinitely many \(n\) such that \(n\equiv1\pmod2\), \(n\equiv2\pmod3\), \(n\equiv3\pmod5\). Solution. From the previous example, one solution is \(n=23\). Since \(2,3,5\) are pairwise coprime, all solutions are \(n=23+30t\), where \(t\in\mathbb Z\). For \(t=0,1,2,\ldots\), this gives infinitely many positive solutions. Comment. CRT often gives not one number, but an entire arithmetic progression. Example 6. Divisibility of Shifts Conditions on \(n+r\) become residues for \(n\). Problem. Find the smallest positive \(n\) such that \(5\mid n+1\), \(7\mid n+2\), \(11\mid n+3\). Solution. Rewrite as \(n\equiv-1\pmod5\), \(n\equiv-2\pmod7\), \(n\equiv-3\pmod{11}\). That is, \(n\equiv4\pmod5\), \(n\equiv5\pmod7\), \(n\equiv8\pmod{11}\). Checking gives \(n=19\): \(20\) is divisible by \(5\), \(21\) by \(7\), \(22\) by \(11\). All solutions are \(n\equiv19\pmod{385}\). Comment. This is a typical language of CRT constructions. Example 7. A Block of Composite Numbers CRT and factorials build long blocks of numbers with planned divisors. Problem. Prove that there exist \(5\) consecutive composite positive integers. Solution. Take \(N=6!\). Then \(N+2,N+3,N+4,N+5,N+6\) are divisible respectively by \(2,3,4,5,6\). Each is larger than the corresponding divisor, so all are composite. These are \(5\) consecutive numbers. Comment. The factorial is a very fast special case of a CRT construction. Example 8. An Impossible Construction Not every residue system exists. Problem. Is there an integer \(x\) such that \(x\equiv4\pmod6\) and \(x\equiv9\pmod{10}\)? Solution. The first congruence gives \(x\equiv0\pmod2\), while the second gives \(x\equiv1\pmod2\). Contradiction. Therefore no such number exists. Comment. The fastest test is to compare residues modulo the common divisor \(2\).

Chapter

Divisor Counting and Special Numbers

Counting divisors with prime factorization, squarefree divisors, products of divisors, factorial exponents, and special number patterns.

1. Counting DivisorsIf \(n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\), then every divisor is obtained by choosing exponents \(0\le e_i\le a_i\). Thus \(d(n)=(a_1+1)\cdots(a_k+1)\).2. Squarefree DivisorsA squarefree divisor has each prime exponent equal to \(0\) or \(1\).3. Products and FactorialsPair divisors as \(d\) and \(n/d\). For factorials, count prime powers with floors.

Example 1. Count Divisors of 3600 This is the basic divisor-counting model. Problem. How many positive divisors does \(3600\) have? Solution. Since \(3600=2^4\cdot3^2\cdot5^2\), the number of divisors is \(5\cdot3\cdot3=45\). Example 2. Squarefree Divisors This reformulates the squarefree-divisor idea. Problem. How many divisors of \(2^3\cdot3^2\cdot5\cdot7\) are not divisible by any square greater than \(1\)? Solution. There are four available primes, and each is either chosen or not chosen. The answer is \(2^4=16\). Example 3. Seven Divisors Then Squared This tests how divisor counts determine exponent patterns. Problem. A natural number \(n\) has exactly \(7\) positive divisors. How many positive divisors does \(n^2\) have? Solution. If \(n=p^6\), then \(n^2=p^{12}\), so \(d(n^2)=13\). Example 4. Power of Five in a Factorial This is the standard factorial-exponent calculation. Problem. Find the largest exponent \(e\) such that \(5^e\mid100!\). Solution. The exponent is \(\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24\).

Chapter

Divisor Counting

The module develops the divisor-counting formula, odd divisors, the square criterion, inverse problems for \( au(n)\), products of divisors, and smallest numbers with prescribed divisor count.

Key Idea Divisor counting turns a number into a list of prime exponents. If \(n=p_1^{a_1}\cdots p_s^{a_s}\), then each divisor is obtained by independently choosing exponents \(0,1,\ldots,a_i\). The olympiad strength of the method appears when we do not merely count, but reconstruct the form of a number from its number of divisors or find the smallest number with a prescribed number of divisors. Basic Facts If \(n=p_1^{a_1}\cdots p_s^{a_s}\), then \(\tau(n)=(a_1+1)\cdots(a_s+1)\). The number \(\tau(n)\) is odd if and only if \(n\) is a square. The number of odd divisors equals the number of divisors of the odd part of the number. If \(n\) is not a square, its divisors pair as \(d\) and \(\frac{n}{d}\). If \(n\) is a square, one divisor \(\sqrt{n}\) is unpaired. To minimise a number with fixed exponents, put larger exponents on smaller primes: \(2^{a_1}3^{a_2}5^{a_3}\cdots\) with \(a_1\ge a_2\ge a_3\ge\cdots\). When to Use This Method The problem asks for the number of divisors, odd divisors, or divisor pairs. \(\tau(n)\) is given, and the possible form of \(n\) must be described. You need the smallest number with a prescribed number of divisors. You need to decide when the number of divisors is odd. The problem contains a product of divisors or a pairing of divisors. How to Recognise the Method If the statement says “exactly \(k\) divisors”, immediately factor \(k\) into factors of the form \(a_i+1\). If the smallest number is requested, enumerate possible exponent patterns, not the numbers themselves. If odd divisors are requested, remove the power of \(2\). If you need to prove oddness of \(\tau(n)\), use divisor pairing around \(\sqrt{n}\). Typical Mistakes Forgetting the zero exponent choice for a prime factor. Counting divisors by listing them and missing one. When minimising a number, putting a large exponent on a large prime. Confusing the number of divisors of \(n\) and \(n^2\). Thinking that \(\tau(n)\) is odd for “almost squares”; an exact square is needed. Mini-Checklist Has the number been factorised into prime powers? Was exponent \(0\) counted for each prime? If \(\tau(n)\) is given, which multiplicative decompositions are possible? If a minimum is requested, are exponents assigned in decreasing order to primes \(2,3,5,\ldots\)? Are all divisors counted, or only odd divisors? Is \(n\) a square?

Example 1. The Formula for \( au(n)\) The main step is to pass from the number to prime exponents. Problem. Find the number of positive divisors of \(360\). Solution. \(360=2^3\cdot3^2\cdot5\). A divisor has the form \(2^a3^b5^c\), where \(a=0,1,2,3\), \(b=0,1,2\), \(c=0,1\). Therefore \(\tau(360)=4\cdot3\cdot2=24\). Comment. Exponent \(0\) means that the prime factor is absent from the divisor. Example 2. Odd Divisors To count odd divisors, the power of two is irrelevant. Problem. How many positive odd divisors does \(720\) have? Solution. \(720=2^4\cdot3^2\cdot5\). An odd divisor contains no factor \(2\), so we choose only exponents of \(3\) and \(5\). This gives \((2+1)(1+1)=6\) odd divisors. Comment. The odd part is \(3^2\cdot5\). Example 3. When \( au(n)\) Is Odd Divisors usually come in pairs; a square gives one unpaired divisor. Problem. Prove that \(\tau(n)\) is odd if and only if \(n\) is a square. Solution. If \(d\mid n\), then \(\frac{n}{d}\mid n\). Usually divisors pair as \(d\) and \(\frac{n}{d}\). An unpaired divisor can occur only when \(d=\frac{n}{d}\), i.e. \(d^2=n\). Hence the number of divisors is odd exactly for squares. Comment. This proof does not require the formula for \(\tau(n)\), but explains it well. Example 4. Smallest Number with \(12\) Divisors Minimisation uses exponent patterns, not brute force over numbers. Problem. Find the smallest positive integer with exactly \(12\) positive divisors. Solution. We need to write \(12\) as a product of numbers \(a_i+1\). The important possibilities are \(12\), \(6\cdot2\), \(4\cdot3\), \(3\cdot2\cdot2\). They give candidates \(2^{11}\), \(2^5\cdot3=96\), \(2^3\cdot3^2=72\), \(2^2\cdot3\cdot5=60\). The smallest is \(60\). Answer: \(60\). Comment. Larger exponents go on smaller primes. Example 5. Sum of Divisors Although the module is about \( au\), it is useful to see the neighbouring function \(\sigma\). Problem. Find the sum of positive divisors of \(72\). Solution. \(72=2^3\cdot3^2\). The sum of divisors is \((1+2+2^2+2^3)(1+3+3^2)=15\cdot13=195\). Comment. This idea returns later in arithmetic-function modules. Example 6. Divisors of a Square For \(n^2\), all exponents double. Problem. If \(n=2^3\cdot3^2\cdot5\), find \(\tau(n^2)\). Solution. Then \(n^2=2^6\cdot3^4\cdot5^2\). Hence \(\tau(n^2)=(6+1)(4+1)(2+1)=7\cdot5\cdot3=105\). Comment. No need to compute the number \(n^2\) itself. Example 7. Numbers with Four Divisors A prescribed number of divisors restricts the form of the number. Problem. Describe all positive integers \(n\) with exactly \(4\) positive divisors. Solution. We need \((a_1+1)\cdots(a_s+1)=4\). The possibilities are \(4\) or \(2\cdot2\). Therefore \(n=p^3\) for a prime \(p\), or \(n=pq\), where \(p\) and \(q\) are distinct primes. Comment. This is the first step toward inverse problems for \(\tau(n)\). Example 8. Product of Divisors Pairing divisors helps find their product. Problem. Prove that the product of all positive divisors of \(n\) equals \(n^{\tau(n)/2}\). Solution. Each divisor \(d\) corresponds to \(\frac{n}{d}\), and the product of the pair is \(n\). Therefore the product of all divisors is \(n\) multiplied once for each pair. The number of pairs is \(\frac{\tau(n)}{2}\). If \(n\) is a square, the middle divisor \(\sqrt{n}\) is accounted for by the same formula, and the result is still correct. Comment. For a square, the exponent can be half-integer, but the value is still an integer.

Chapter

Number Bases

Base conversion, arithmetic in non-decimal bases, binary notation, digit counts, and trailing zeros in other bases.

1. Place ValueIn base \(b\), the numeral \(a_ka_{k-1}\cdots a_0\) represents \(a_kb^k+a_{k-1}b^{k-1}+\cdots+a_0\).2. Converting and ArithmeticRepeated division by the base gives digits from right to left. Arithmetic works as usual, but carrying happens at the base.3. Trailing ZerosTrailing zeros in base \(b\) are controlled by the prime factorization of \(b\).

Example 1. From Base Seven This is the basic place-value conversion. Problem. Convert \(345_7\) to decimal notation. Solution. \(345_7=3\cdot7^2+4\cdot7+5=147+28+5=180\). Example 2. To Base Five This shows conversion from decimal by powers of the base. Problem. Write \(2026\) in base \(5\). Solution. \(2026=3\cdot625+1\cdot125+1\cdot25+0\cdot5+1\), so \(2026=31101_5\). Example 3. Addition in Base Five This adds arithmetic in non-decimal bases. Problem. Compute \(234_5+143_5\) and write the answer in base \(5\). Solution. \(234_5=69\) and \(143_5=48\), so the sum is \(117=432_5\). Example 4. Trailing Zeros in Base Twelve This connects bases with prime factorization. Problem. How many zeros does \(10!\) end with when written in base \(12\)? Solution. In \(10!\), \(v_2=8\) and \(v_3=4\). Each \(12\) uses two factors \(2\) and one factor \(3\), so the answer is \(\min(\lfloor8/2\rfloor,4)=4\).

Chapter

Digits, Bases and Periodicity

The module translates digit problems into congruences: divisibility rules, last digits, base-\(b\) notation, repunits, decimal periods, and first constructions of numbers with restricted digits.

Key Idea Digit problems are almost always congruence problems. A decimal representation is an expansion in powers of \(10\), and a representation in base \(b\) is an expansion in powers of \(b\). Thus divisibility rules, last digits, and decimal periods should be translated into residues. The main move is this: if \(N=a_k10^k+\cdots+a_1 10+a_0\), then modulo \(m\) we may replace \(10\) by its residue. For example, modulo \(9\) we have \(10\equiv1\), modulo \(11\) we have \(10\equiv-1\), and the last \(r\) digits are determined by the residue modulo \(10^r\). Basic Facts If \(N=\overline{a_ka_{k-1}\ldots a_0}\), then \(N\equiv a_0+\cdots+a_k\pmod9\). Modulo \(11\): \(N\equiv a_0-a_1+a_2-\cdots+(-1)^k a_k\pmod{11}\). The last \(r\) digits of a number are its residue modulo \(10^r\). In base \(b\): \((a_ka_{k-1}\ldots a_0)_b=a_kb^k+\cdots+a_1b+a_0\). If \(\gcd(10,m)=1\), the period of \(\frac{1}{m}\) equals or divides the order of \(10\) modulo \(m\). The repunit \(R_n=\underbrace{11\ldots1}_{n}=\frac{10^n-1}{9}\). When to Use This Method The problem mentions digits, digit sums, rearranged digits, or notation in another base. You need the last one, two, or three digits of a power. You need to prove divisibility of a number made of repeated digits. A decimal fraction appears and the period length is required. You need to construct a number with restricted digits divisible by a given \(m\). How to Recognise the Method If the problem mentions a sum of digits, try modulo \(9\) or \(3\). If an alternating digit sum, symmetry, or an even-length palindrome appears, check modulo \(11\). If last digits of a power are required, work modulo \(10^r\) and find the residue cycle. If the statement contains a number of the form \(111\ldots111\), rewrite it as \(R_n=\frac{10^n-1}{9}\). Divisibility often becomes the condition \(10^n\equiv1\pmod m\). Typical Mistakes Using a divisibility rule as a slogan without naming the modulus behind it. Forgetting the condition \(\gcd(10,m)=1\) when discussing decimal periods. Claiming \(R_a\mid R_b\) is obvious; it should be connected to \(a\mid b\). For last two digits, working only modulo \(25\) and forgetting to combine with modulo \(4\). In base problems, forgetting that each digit must be smaller than the base. Mini-Checklist Which base is used: \(10\) or \(b\)? Which modulus is natural: \(9\), \(11\), \(10^r\), \(b-1\), \(b+1\)? Do we need a power cycle? Can a number of ones be replaced by \(R_n=\frac{10^n-1}{9}\)? Has the coprimality condition for a period been checked? If a number with digits \(0\) and \(1\) is being constructed, can the pigeonhole principle be applied to residues?

Example 1. Digit Sum as a Congruence A basic example: the divisibility rule for \(9\) is proved, not memorised. Problem. Prove that a number \(N\) and the sum of its decimal digits have the same remainder modulo \(9\). Solution. Let \(N=a_k10^k+\cdots+a_1 10+a_0\). Since \(10\equiv1\pmod9\), we have \(10^i\equiv1\pmod9\) for all \(i\). Hence \(N\equiv a_k+\cdots+a_1+a_0\pmod9\). Comment. This is why divisibility by \(9\) is tested by the digit sum. Example 2. Alternating Sum Modulo \(11\) appears because \(10\equiv-1\pmod{11}\). Problem. Check whether \(583946\) is divisible by \(11\). Solution. Compute the alternating sum from the right: \(6-4+9-3+8-5=11\). It is divisible by \(11\), so \(583946\) is divisible by \(11\). Comment. The signs must alternate consistently; direction affects only the sign of the final sum. Example 3. Last Two Digits The last two digits are the residue modulo \(100\). Problem. Find the last two digits of \(7^{50}\). Solution. Since \(7^4=2401\equiv1\pmod{100}\), \(7^{50}=7^{4\cdot12+2}\equiv7^2\equiv49\pmod{100}\). The last two digits are \(49\). Comment. The actual cycle is often shorter than Euler's theorem suggests. Example 4. Base Notation Translating into an expression in the base removes ambiguity. Problem. Find all bases \(b>6\) for which \((253)_b\) is divisible by \(7\). Solution. We have \((253)_b=2b^2+5b+3\). Modulo \(7\), solve \(2b^2+5b+3\equiv0\). Checking residues \(b\pmod7\), we get \(b\equiv4\pmod7\). Since \(b>6\), all bases are \(b=7t+4\), \(t\ge1\). Comment. Remember the base condition: all digits must be smaller than the base. Example 5. Decimal Period The period of \(\frac{1}{m}\) is linked to the order of \(10\) modulo \(m\). Problem. Find the period length of \(\frac{1}{7}\). Solution. We need the least \(k>0\) such that \(10^k\equiv1\pmod7\). The residues are \(10\equiv3\), \(10^2\equiv2\), \(10^3\equiv6\), \(10^4\equiv4\), \(10^5\equiv5\), \(10^6\equiv1\pmod7\). Thus the period is \(6\). Comment. This is not long division; it is a residue cycle. Example 6. A Number of Ones A repunit turns the problem into a congruence for a power of \(10\). Problem. Prove that \(111111\) is divisible by \(7\), \(11\), and \(13\). Solution. We have \(111111=R_6=\frac{10^6-1}{9}\). Also \(1001=7\cdot11\cdot13\), and \(111111=111\cdot1001\). Hence the number is divisible by \(7\), \(11\), and \(13\). Comment. Sometimes block factorisation is easier than direct work with a long decimal. Example 7. All Repunit Lengths The condition \(R_n\mid R_m\) is connected to divisibility of the indices. Problem. Prove that if \(a\mid b\), then \(R_a\mid R_b\). Solution. Let \(b=qa\). Then \(R_b=1+10+\cdots+10^{b-1}\). Split the sum into blocks of length \(a\): \(R_b=R_a(1+10^a+10^{2a}+\cdots+10^{(q-1)a})\). Therefore \(R_a\mid R_b\). Comment. The converse needs more work and is usually proved through the order of \(10\). Example 8. A Number with Digits \(0\) and \(1\) This is the first important example where the pigeonhole principle appears. Problem. Prove that for every \(m\) coprime to \(10\), there exists a number consisting only of ones that is divisible by \(m\). Solution. Consider the \(m\) numbers \(R_1,R_2,\ldots,R_m\). If one is divisible by \(m\), we are done. Otherwise two have the same residue: \(R_i\equiv R_j\pmod m\), \(i Comment. This move constructs a multiple without explicitly finding it.

Chapter

Fractions, Decimals, and Periodicity

Terminating decimals, repeating decimals, decimal periods, and fraction-to-decimal structure.

1. Terminating DecimalsA reduced fraction \(a/b\) has a terminating decimal exactly when the prime factors of \(b\) are only \(2\) and \(5\).2. Number of Decimal PlacesIf \(b=2^r5^s\), then \(a/b\) needs at most \(\max(r,s)\) digits after the decimal point.3. Repeating DecimalsWhen another prime divides the denominator, long division eventually repeats a remainder.

Example 1. Terminating Criterion This is the core theorem for terminating decimals. Problem. Explain why a reduced fraction whose denominator is \(2^a5^b\) has a terminating decimal. Solution. If \(m=\max(a,b)\), then \(2^a5^b\mid10^m\). So the fraction can be written with denominator \(10^m\). Example 2. Decimal Places Needed This turns the criterion into a quick computation. Problem. How many digits after the decimal point are needed to write \(\frac{7}{2^3\cdot5^5}\) as a terminating decimal? Solution. The denominator divides \(10^5\) but not a smaller power of \(10\). Therefore \(5\) decimal places are needed. Example 3. Convert a Repeating Decimal This is the standard algebraic conversion of a repeating decimal. Problem. Write \(0.\overline{27}\) as a reduced fraction. Solution. If \(x=0.\overline{27}\), then \(100x=27.\overline{27}\). Hence \(99x=27\), so \(x=3/11\). Example 4. Fiftieth Digit of One Seventh This is a period-indexing problem. Problem. Find the \(50\)-th digit after the decimal point in \(\frac17=0.\overline{142857}\). Solution. Since \(50\equiv2\pmod6\), the digit is the second digit of \(142857\), which is \(4\).

Chapter

Mixed Problems I

The module trains method selection without an announced topic: divisibility, GCD, congruences, factorisation, Diophantine equations, periods, CRT, descent, and constructions.

Key Idea In mixed problems, the method is not announced in advance. The goal of this module is to learn what blocks a direct solution: a large parameter, a hidden GCD, an impossible residue, an expression that should be factored, or a construction that must be built. Good olympiad work begins not with computation but with choosing the right language: divisibility, congruences, GCD, factorisation, descent, order, or CRT. The same problem may have several starts, but usually only one removes the unnecessary complexity quickly. Basic Facts To prove divisibility by a composite number, split it into coprime factors. For \(\gcd(f(n),g(n))\), use the Euclidean algorithm: subtract multiples of expressions. If an equation seems impossible, check squares modulo \(3,4,5,8\). If products and sums appear together, try to transform the equation into \((x+a)(y+b)=c\). To construct a number with several residues, translate the conditions into a system of congruences. For impossibility or infinite-process arguments, look for a minimal counterexample or descent. When to Use This Method After reading the problem, it is not clear which formula or modulus should be used. The statement mixes powers, divisibility, digits, GCD, or equations. Naive case checking quickly becomes long. You must not only find an answer, but explain why no other cases exist. How to Recognise the Method First ask: what happens if the variable is replaced by a residue? If the expression collapses, it is a modular problem. If two expressions have a common divisor, replace one by a difference. If \(xy\) and linear terms appear together, look for a completed product. If the problem asks for existence, think of CRT or the pigeonhole principle. If it asks for impossibility in positive integers, check residues and the possibility of infinite descent. Typical Mistakes Starting a large search instead of choosing a modulus. Forgetting to check that factor pairs give positive integer solutions. Confusing an existence proof with finding one small example. Dividing a congruence without checking coprimality. In descent problems, not proving that the new solution is genuinely smaller. Mini-Checklist Is there a natural modulus? Can the GCD be replaced by a simpler GCD? Can the expression be factored or completed to a product? Do we need to construct a number rather than compute it? If a candidate is found, have all conditions been checked? If impossibility is proved, where exactly does the contradiction occur?

Example 1. Divisibility Without Search We practise splitting into coprime factors. Problem. Prove that \(n^3-n\) is divisible by \(6\) for every integer \(n\). Solution. We have \(n^3-n=n(n-1)(n+1)\), the product of three consecutive integers. One of them is even, so the product is divisible by \(2\). One of them is divisible by \(3\). Since \(2\) and \(3\) are coprime, the product is divisible by \(6\). Comment. The method is chosen from the composite divisor \(6=2\cdot3\). Example 2. GCD by Subtraction A complicated GCD often hides a small divisor. Problem. Find \(\gcd(n^2+1,n+1)\). Solution. Subtract: \(n^2+1-(n-1)(n+1)=2\). Hence the common divisor divides \(2\). If \(n\) is odd, then both \(n+1\) and \(n^2+1\) are even, so the GCD is \(2\). If \(n\) is even, both cannot be even, so the GCD is \(1\). Comment. The answer is \(2\) for odd \(n\), and \(1\) for even \(n\). Example 3. Impossibility Modulo a Number Sometimes a square table replaces all casework. Problem. Prove that \(x^2+y^2=8z+7\) has no integer solutions. Solution. A square modulo \(8\) can only be \(0,1,4\). The sum of two such residues cannot be \(7\) modulo \(8\); possible sums are \(0,1,2,4,5\). But the right-hand side is \(7\) modulo \(8\). Contradiction. Comment. The key is to choose modulus \(8\), not to solve the equation. Example 4. A Divisor of Linear Form The hidden move is to multiply by \(4\) so that the divisor forms a square. Problem. Find all positive integers \(n\) such that \(2n+1\mid n^2+n+3\). Solution. If \(2n+1\mid n^2+n+3\), then \(2n+1\mid4(n^2+n+3)\). But \(4(n^2+n+3)=(2n+1)^2+11\). Thus \(2n+1\mid11\). Since \(n\ge1\), \(2n+1\ge3\), so \(2n+1=11\), giving \(n=5\). Check: \(11\mid33\). Comment. This is a typical olympiad replacement: make the expression match the divisor. Example 5. Completing to a Product An equation with \(xy\) and linear terms often factors. Problem. Solve \(xy+x+y=35\) in positive integers. Solution. Add \(1\): \((x+1)(y+1)=36\). Now list factor pairs of \(36\) greater than \(1\). We get \((x,y)=(1,17),(2,11),(3,8),(5,5),(8,3),(11,2),(17,1)\). Comment. Factorisation turns an infinite search into a finite divisor list. Example 6. Repunit and Order A long number of ones should become a congruence for \(10^n\). Problem. Find all \(n\) for which \(R_n\) is divisible by \(13\). Solution. Since \(13\) is coprime to \(9\), the condition \(13\mid R_n\) is equivalent to \(10^n\equiv1\pmod{13}\). The order of \(10\) modulo \(13\) is \(6\). Therefore \(13\mid R_n\) exactly when \(6\mid n\). Comment. The method is suggested by the form \(111\ldots111\). Example 7. Descent Instead of Search If one positive solution produces a smaller positive solution, none exist. Problem. Prove that \(x^2+y^2=3xy\) has no positive integer solutions. Solution. Assume a solution exists and choose one with minimal \(x+y\). Let \(x\ge y\). Then \(x<3y\). Treating the equation as quadratic in \(x\), the second root is \(x'=3y-x\). It is positive, integral, and gives another solution. Also \(x(3y-x)=y^2\) implies \(x>2y\), hence \(0 Comment. This is a first taste of Vieta descent without heavy machinery. Example 8. Constructing a Block Existence is often proved by construction rather than by finding a small example. Problem. Prove that there exist \(5\) consecutive composite numbers. Solution. Take \(N=6!\). Then \(N+2,N+3,N+4,N+5,N+6\) are divisible respectively by \(2,3,4,5,6\), and each is larger than its divisor. Hence all are composite. Comment. This is a factorial construction; later it can be replaced by CRT constructions.

Chapter

Divisibility Rules

Digit rules for divisibility, modular proofs of rules, missing digit problems, and last-digit arguments.

1. Digit SumsBecause \(10\equiv1\pmod9\), every decimal number has the same remainder modulo \(9\) as the sum of its digits.2. Last DigitsModulo \(2,4,5,8,10\), only the last few digits matter.3. The Rule for 11Since \(10\equiv-1\pmod{11}\), alternating sums of digits determine divisibility by \(11\).

Example 1. Why the Rule for Nine Works This is the core proof behind digit-sum tests. Problem. Prove that a decimal integer has the same remainder modulo \(9\) as the sum of its digits. Solution. If \(n=a_k10^k+\cdots+a_0\), then \(10^j\equiv1\pmod9\). Hence \(n\equiv a_k+\cdots+a_0\pmod9\). Example 2. A Missing Digit This combines two digit rules. Problem. Find all digits \(A\) such that \(52A8\) is divisible by both \(3\) and \(4\). Solution. For divisibility by \(4\), \(10A+8\equiv2A\pmod4\), so \(A\) is even. For divisibility by \(3\), \(15+A\) is divisible by \(3\), so \(A\in\{0,3,6,9\}\). Thus \(A=0\) or \(6\). Example 3. Digits for Divisibility by 11 and 5 This is a missing-digit problem using the rule for 11. Problem. Find all digits \(A,B\) such that \(3A5B\) is divisible by both \(11\) and \(5\). Solution. For divisibility by \(11\), \(8-A-B\) must be divisible by \(11\). If \(B=0\), then \(A=8\). If \(B=5\), then \(A=3\). The numbers are \(3850\) and \(3355\). Example 4. Divisibility by 72 This is a compact multi-rule digit problem. Problem. Find all digit pairs \(A,B\) such that \(72A4B\) is divisible by \(72\). Solution. We need divisibility by \(8\) and \(9\). Checking the last three digits \(A4B\) and digit sum \(13+A+B\), the pairs are \((1,4)\) and \((6,8)\). The numbers are \(72144\) and \(72648\).

Chapter

Mock Olympiads I

The final module of Number Theory Book 1: training problems without announced methods, imitating short olympiad rounds and consolidating strategy selection.

Key Idea A mock olympiad is different from a thematic worksheet: the method is not written in the statement. The main goal is to classify the problem quickly, choose a meaningful first move, and avoid getting trapped in long casework. In this module, the problems are arranged like training rounds: from short technical questions to problems combining two ideas. After solving, it is important not only to get the answer, but also to state why the chosen method was natural. Basic Facts First look for a small modulus: \(2,3,4,5,7,8,9,11\). For divisibility of \(f(n)\) by a divisor of the form \(an+b\), express \(f(n)\) through that divisor. First-level Diophantine equations often solve by factorisation. Long numbers made of repeated digits become repunits \(R_n=\frac{10^n-1}{9}\). Existence of numbers with prescribed divisibility is often proved by CRT, factorials, or the pigeonhole principle. When to Use This Method You are solving a set of problems without topic labels. The first idea creates too many cases. A problem looks school-like but asks for proof that no other cases exist. You need to manage time between problems of different difficulty. How to Recognise the Method If the problem says “prove divisibility”, split the divisor and check residues. If it says “find all \(n\)”, try to force a small divisor from the expression. If it says “do there exist”, think of construction rather than a small search. For a mock round, it is useful to mark the problems first: technique, standard method, one hidden idea, strong problem. This prevents spending the whole time on one middle problem. Typical Mistakes Solving strictly in order even though a later problem may be shorter. Writing computations without explaining the choice of modulus. In “find all” problems, forgetting the final check. In constructions, finding one example when the statement requires every parameter. After a contradiction, not saying which assumption was contradicted. Mini-Checklist What is required: prove, find all, construct, disprove? Is there a natural small modulus? Can the expression be reduced modulo the divisor? Is there a factorisation after adding a constant? If the problem is constructive, which tool builds the object? Have all found answers been checked at the end?

Example 1. Quick Classification The problem looks like a power problem, but it is solved by splitting the divisor. Problem. Prove that \(30\mid n^5-n\) for every integer \(n\). Solution. We prove divisibility by \(2\), \(3\), and \(5\). By Fermat's little theorem or by checking residues, \(n^5\equiv n\) modulo \(2,3,5\). Thus \(n^5-n\) is divisible by each of \(2,3,5\). They are pairwise coprime, so \(30\mid n^5-n\). Comment. The method is chosen from \(30=2\cdot3\cdot5\). Example 2. All Solutions Without Search Factorisation turns the equation into a divisor list. Problem. Solve \(xy+2x+y=31\) in positive integers. Solution. Add \(2\): \((x+1)(y+2)=33\). Factor pairs of \(33\) are \((3,11),(11,3),(33,1),(1,33)\). With \(x,y>0\), the possible pairs are \((x+1,y+2)=(3,11),(11,3)\). Hence \((x,y)=(2,9),(10,1)\). Comment. After solving, always check positivity. Example 3. A Divisor of the Form \(an+b\) The hidden technique is to express the polynomial through the divisor. Problem. Find all positive integers \(n\) such that \(3n+1\mid n^2+n+1\). Solution. If \(3n+1\mid n^2+n+1\), then \(3n+1\mid9(n^2+n+1)\). But \(9(n^2+n+1)=(3n+1)^2+3(3n+1)+5\). Thus \(3n+1\mid5\). For \(n\ge1\), \(3n+1\ge4\), so \(3n+1=5\), giving \(n=\frac43\), impossible. There are no solutions. Comment. The coefficient \(9\) is chosen to create \((3n+1)^2\). Example 4. Period Instead of a Long Power Last digits are a residue-cycle problem. Problem. Find the last two digits of \(13^{100}\). Solution. Work modulo \(100\). We have \(13^2=169\equiv69\), \(13^4\equiv69^2\equiv61\), and \(13^{20}\equiv1\pmod{100}\). Thus \(13^{100}=(13^{20})^5\equiv1\pmod{100}\). The last two digits are \(01\). Comment. The answer has two digits: \(01\), not just \(1\). Example 5. Construction by Factorial When proving the existence of a block, a small explicit example is not necessary. Problem. Prove that there exist \(8\) consecutive composite numbers. Solution. Take \(N=9!\). Then \(N+2,N+3,\ldots,N+9\) are divisible respectively by \(2,3,\ldots,9\), and each is larger than its divisor. Therefore all are composite. Comment. This construction works for any length of a composite block. Example 6. Checking a False Claim In a mock round, sometimes the key is to notice a counterexample quickly. Problem. Is it true that every number of the form \(n^2+n+41\) is prime? Solution. No. For \(n=41\), we get \(41^2+41+41=41(41+1+1)=41\cdot43\), which is composite. Comment. Words like “every” and “for all” require checking special values.