Course Theory
Book 2. Olympiad Number Theory Methods
Book 2. Olympiad Number Theory Methods
- 1. Advanced GCD Problems
- 2. Quadratic Residues and Modular Obstructions
- 3. Multiplicative Order
- 4. Wilson, Fermat and Euler in Problems
- 5. p-adic Valuations
- 6. LTE: Lifting the Exponent
- 7. Diophantine Equations I: Factorisation and Bounds
- 8. Diophantine Equations II: Descent and Vieta Jumping
- 9. Chinese Remainder Theorem and Construction
- 10. Arithmetic Functions
- 11. Digits, Bases and Decimal Periods
- 12. Polynomials, Sequences and Number Theory
Chapter
Advanced GCD Problems
Key Idea
Strong gcd problems are rarely just computations. The main technique is to replace a pair of numbers by a simpler pair with the same gcd: subtract multiples, take linear combinations, use polynomial remainders, and reduce exponents.
Basic Facts
We use \( \gcd(a,b)=\gcd(a,b-ka) \), \( \gcd(a,b)=\gcd(a, b \bmod a) \), and the fact that if \(d\) divides two numbers, then \(d\) divides every integer linear combination of them. If \( \gcd(a,b)=1 \) and \(a\mid bc\), then \(a\mid c\). For powers, the key identity is \( \gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1 \).
When to Use This Method
Use gcd methods when a problem contains divisibility of two expressions, a condition like \( \gcd(f(n),g(n))>1 \), powers \(a^m-1\), neighbouring terms of a sequence, or a request to find all parameters for which the common divisor is not one.
How to Recognise the Method
Look for a substitution by a remainder: if a divisor contains \(n+c\), replace \(n\) by \(-c\) in the other expression. If powers have different exponents, apply the Euclidean algorithm to the exponents. If numbers are coprime, test whether a common prime divisor would be forced to divide both original numbers.
Typical Mistakes
Do not divide a congruence by a number before checking coprimality. Do not conclude from \(d\mid ab\) that \(d\mid a\) or \(d\mid b\). In power problems, it is easy to prove only one direction; one must also show that the proposed gcd is maximal.
Mini-checklist
1. Which two expressions have a common divisor? 2. Can one expression be replaced by a linear combination? 3. Can a power or exponent be reduced? 4. What happens to a prime divisor? 5. Is there a coprimality condition? 6. Have all residues or parameters been checked?
Example 1. A Remainder Instead of Long Division
This teaches replacing a polynomial by its remainder modulo a linear expression.
Problem. Find all possible values of \( \gcd(n+5,n^2+3n+9) \) for positive integers \(n\).
Let \(d=\gcd(n+5,n^2+3n+9)\). Since \(n\equiv -5 \pmod{n+5}\), we get \(n^2+3n+9\equiv 25-15+9=19\pmod{n+5}\). Hence \(d=\gcd(n+5,19)\). Only \(1\) and \(19\) are possible. Both occur: if \(n+5\) is not divisible by \(19\), the gcd is \(1\), while \(n=14\) gives \(19\).
Comment. A linear factor turns the polynomial into a constant remainder.
Example 2. GCD with a Neighbouring Linear Factor
This shows how to prove that a common divisor is bounded by a small number.
Problem. Prove that \( \gcd(n^2+n+1,n-1) \) divides \(3\).
If \(d\mid n-1\), then \(n\equiv1\pmod d\). Therefore \(n^2+n+1\equiv 1+1+1=3\pmod d\). Hence, if \(d\) also divides \(n^2+n+1\), then \(d\mid3\). Thus \( \gcd(n^2+n+1,n-1)\mid3\).
Comment. We do not always need the exact gcd; often it is enough to restrict it.
Example 3. GCD of Numbers \(a^m-1\)
A standard olympiad template: the Euclidean algorithm moves to the exponents.
Problem. Prove that \( \gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1 \).
Let \(g=\gcd(m,n)\). The number \(2^g-1\) divides both expressions because \(g\mid m\) and \(g\mid n\). Conversely, suppose \(m>n\). Then \(2^m-1-(2^{m-n})(2^n-1)=2^{m-n}-1\). Thus any common divisor of \(2^m-1\) and \(2^n-1\) also divides \(2^{m-n}-1\). Repeating the Euclidean algorithm on the exponents leads to \(2^g-1\).
Comment. The Euclidean algorithm is applied to the exponents, not to the huge numbers themselves.
Example 4. Common Divisors and Coprimality
This teaches excluding a prime divisor by contradiction with \( \gcd(a,b)=1 \).
Problem. Let \( \gcd(a,b)=1 \). Prove that \( \gcd(a+b,a^2+b^2) \) divides \(2\).
Let a prime \(p\) divide both \(a+b\) and \(a^2+b^2\). From \(a+b\equiv0\pmod p\) we get \(b\equiv -a\pmod p\). Then \(a^2+b^2\equiv2a^2\pmod p\). If \(p\ne2\), then \(p\mid a\), hence \(p\mid b\), impossible. Therefore the only possible prime divisor is \(2\), so the whole gcd divides \(2\).
Comment. Factoring is unnecessary; it is enough to study a prime divisor.
Example 5. A Common Divisor Becomes a Congruence
This shows how a condition \( \gcd>1 \) turns into a congruence.
Problem. Find all positive integers \(n\) such that \( \gcd(n^2+2,n^3+3)>1 \).
Let \(d\) be a common divisor. Then \(d\mid n(n^2+2)-(n^3+3)=2n-3\). Multiply the first expression by \(4\): \(4(n^2+2)=4n^2+8\). From \(2n\equiv3\pmod d\), we get \(4n^2\equiv9\pmod d\), so \(d\mid17\). Thus only the common prime divisor \(17\) is possible. It appears exactly when \(2n\equiv3\pmod{17}\), that is, \(n\equiv10\pmod{17}\). Answer: \(n\equiv10\pmod{17}\).
Comment. First the common divisor is severely restricted, then attainability is checked.
Example 6. Powers with Two Bases
This prepares for problems where one has to introduce an inverse element.
Problem. Let \(a>b>0\) and \( \gcd(a,b)=1 \). Prove that \( \gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)} \).
Let \(g=\gcd(m,n)\). The right-hand side divides both expressions. Conversely, let \(d\) be a common divisor. Since \( \gcd(b,d)=1 \), \(b\) is invertible modulo \(d\). From \(a^m\equiv b^m\) and \(a^n\equiv b^n\), we obtain \((ab^{-1})^m\equiv1\) and \((ab^{-1})^n\equiv1\pmod d\). Hence \((ab^{-1})^g\equiv1\pmod d\), so \(a^g\equiv b^g\pmod d\), and \(d\mid a^g-b^g\).
Comment. The hidden step is that division by \(b\) is allowed only after coprimality is checked.
Example 7. GCD of Neighbouring Factorials
This shows how a linear combination gives a small number.
Problem. Prove that \( \gcd(n!+1,(n+1)!+1)=1 \).
Let \(d\) divide both numbers. Then \(d\mid (n+1)!+1-(n+1)(n!+1)=-n\). Hence \(d\mid n\). But \(d\mid n!+1\) and \(d\mid n\) imply \(d\mid n!\), so \(d\mid1\). Therefore \(d=1\).
Comment. The combination is chosen to eliminate the factorial.
Example 8. A Strong Prime-Divisor Argument
An olympiad-style example: instead of computing the gcd, we analyse a possible prime divisor.
Problem. Let \( \gcd(a,b)=1 \). Find \( \gcd(a^2+b^2,a^3+b^3) \).
Consider an odd prime \(p\) dividing both numbers. Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). Then \(t^2\equiv-1\) and \(t^3\equiv-1\pmod p\). Dividing the second congruence by the first gives \(t\equiv1\pmod p\), but then \(1\equiv-1\pmod p\), impossible for odd \(p\). Thus there are no odd prime divisors. Now check \(2\): if \(a,b\) are both odd, both expressions are even and \(a^2+b^2\equiv2\pmod4\), so the gcd is \(2\). If one of \(a,b\) is even, both expressions are odd, so the gcd is \(1\).
Comment. This trains prime-divisor analysis and modular inverses.
Chapter
Quadratic Residues and Modular Obstructions
Key Idea
Quadratic residues help prove impossibility. Instead of checking all integers, we examine which residues squares can have modulo a small number, then choose a modulus where the two sides land in incompatible residue sets.
Basic Facts
Squares modulo \(4\) are only \(0,1\); modulo \(8\), only \(0,1,4\); modulo \(3\), only \(0,1\); modulo \(5\), only \(0,1,4\). If an odd prime \(p\) divides \(a^2+1\), then \(p=2\) or \(p\equiv1\pmod4\). If \(p\equiv3\pmod4\) and \(p\mid x^2+y^2\), then \(p\mid x\) and \(p\mid y\).
When to Use This Method
Use this method when an equation contains squares, sums of squares, expressions \(a^2+1\), \(a^2+b^2\), \(a^2+ab+b^2\), or when the goal is to prove that no solution exists. It is especially useful before harder Diophantine equations.
How to Recognise the Method
If the right-hand side has the form \(4k+3\), try modulo \(4\). If \(8k+7\) appears, try modulo \(8\). If \(a^2+1\) appears, think of \(-1\) being a square. If \(a^2+ab+b^2\) appears, multiplying by an inverse often produces an element of order \(3\).
Typical Mistakes
Do not conclude from one modulus before the full residue set has been checked. Do not divide by \(b\) modulo \(p\) until \(p\nmid b\) is proved. In descent problems, one must show that the smaller triple is still integral.
Mini-checklist
1. What residues can squares take? 2. Which modulus reveals the contradiction? 3. Can a prime divisor be considered? 4. Is division by a variable modulo a prime allowed? 5. If a common divisor forces all variables to be divisible, does it create infinite descent?
Example 1. Squares Modulo \(8\)
Basic technique: build the residue table for squares.
Problem. Prove that the square of an integer modulo \(8\) is \(0\), \(1\), or \(4\).
It is enough to check residues \(0,1,\ldots,7\). Their squares give \(0,1,4,1,0,1,4,1\). Hence the set of square residues modulo \(8\) is \(\{0,1,4\}\).
Comment. This table will be used in problems on sums of squares.
Example 2. Impossibility Modulo \(4\)
This shows the most common obstruction for a sum of two squares.
Problem. Prove that the equation \(x^2+y^2=4z+3\) has no integer solutions.
A square modulo \(4\) is \(0\) or \(1\). Therefore a sum of two squares modulo \(4\) can only be \(0,1,2\). The right-hand side is \(3\pmod4\), impossible.
Comment. Modulo \(4\) is chosen because the right-hand side visibly has residue \(3\).
Example 3. A Quadratic Congruence with a Parameter
This teaches solving a small congruence by a table.
Problem. Find all \(n\) such that \(7\mid n^2+n+1\).
Checking residues \(n\pmod7\), the values of \(n^2+n+1\) are \(1,3,0,6,0,3,1\). Hence \(n\equiv2\) or \(n\equiv4\pmod7\).
Comment. A table is acceptable when the modulus is small.
Example 4. Why \(-1\) Is Not Always a Square
This connects quadratic residues with prime divisors.
Problem. Let an odd prime \(p\mid a^2+1\). Prove that \(p\equiv1\pmod4\).
If \(p\mid a\), then \(p\mid1\), impossible. Thus \(a\not\equiv0\pmod p\). From \(a^2\equiv-1\pmod p\), we get \(a^4\equiv1\), but \(a^2\not\equiv1\). Therefore the order of \(a\) modulo \(p\) is \(4\). The order divides \(p-1\), so \(4\mid p-1\).
Comment. This is a first look at the connection between residues and modular order.
Example 5. A Sum of Three Squares
This shows that sums of allowed residues also have restrictions.
Problem. Prove that \(x^2+y^2+z^2=8t+7\) has no integer solutions.
Modulo \(8\), each square is \(0,1\), or \(4\). A sum of three residues from \(\{0,1,4\}\) cannot be \(7\). The right-hand side is \(7\pmod8\), contradiction.
Comment. This is not the full three-square theorem, only the useful olympiad obstruction.
Example 6. Primes \(3\pmod4\)
A key technique for sums of two squares.
Problem. Let \(p\equiv3\pmod4\) be prime and \(p\mid x^2+y^2\). Prove that \(p\mid x\) and \(p\mid y\).
If \(p\nmid y\), then \(xy^{-1}\) exists modulo \(p\), and \(x^2+y^2\equiv0\) gives \((xy^{-1})^2\equiv-1\pmod p\). Thus \(-1\) is a square modulo \(p\), which is possible only for \(p\equiv1\pmod4\), a contradiction. Hence \(p\mid y\), and then the original divisibility gives \(p\mid x\).
Comment. Important template: first show division is allowed; otherwise part of the conclusion is already true.
Example 7. The Form \(a^2+ab+b^2\)
This shows the order \(3\) analogue.
Problem. Let \(p\ne3\) be prime, \( \gcd(a,b)=1 \), and \(p\mid a^2+ab+b^2\). Prove that \(p\equiv1\pmod3\).
Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). Then \(t^2+t+1\equiv0\). Multiplying by \(t-1\), we obtain \(t^3-1\equiv0\). Also \(t\not\equiv1\), otherwise \(3\equiv0\pmod p\), impossible for \(p\ne3\). Thus the order of \(t\) is \(3\), so \(3\mid p-1\).
Comment. This is an important bridge to cubic residues and orders.
Example 8. Infinite Descent
An olympiad consequence of a modular obstruction.
Problem. Prove that the equation \(x^2+y^2=3z^2\) has only the solution \(x=y=z=0\) in integers.
Modulo \(3\), squares are \(0\) or \(1\). If \(x^2+y^2\) is divisible by \(3\), both squares must be divisible by \(3\), hence \(3\mid x\) and \(3\mid y\). Then \(9\mid x^2+y^2=3z^2\), so \(3\mid z\). Dividing \(x,y,z\) by \(3\), we get a smaller solution. A nonzero solution would create infinite descent, impossible. Thus no nonzero solution exists.
Comment. It is important to prove divisibility of all three variables, not only two.
Chapter
Multiplicative Order
Key Idea
The order of \(a\) modulo \(m\) is the length of the power cycle \(a,a^2,a^3,\ldots\) until \(1\) first appears. If \( \gcd(a,m)=1 \), order turns huge powers into small residues and gives restrictions on prime divisors.
Basic Facts
If \(d=\operatorname{ord}_m(a)\), then \(a^k\equiv1\pmod m\) if and only if \(d\mid k\). For a prime \(p\), the order of every nonzero residue modulo \(p\) divides \(p-1\). If \(p\mid a^n-1\), then \( \operatorname{ord}_p(a)\mid n \). If \(p\mid a^n+1\), then the order divides \(2n\), but not \(n\).
When to Use This Method
Use order when a problem contains large powers, divisibility \(p\mid a^n\pm1\), last digits, residue cycles, or restrictions on possible prime divisors.
How to Recognise the Method
Expressions \(a^n\equiv1\), \(a^n\equiv-1\), \(p\mid a^n-1\), \(p\mid a^n+1\) almost always point to order. If the exponent is huge, first find the cycle length, then reduce the exponent modulo that length.
Typical Mistakes
Order is defined only when \( \gcd(a,m)=1 \). Do not claim the order is \(p-1\) when you only know it divides \(p-1\). In problems with \(a^n+1\), one must separately prove that the order does not divide \(n\).
Mini-checklist
1. Are the base and modulus coprime? 2. What is the smallest exponent giving \(1\)? 3. Does the order divide the needed exponent? 4. If a prime \(p\) appears, what follows from \(d\mid p-1\)? 5. Has the case \(p=2\) been checked separately?
Example 1. First Order
This shows the definition on a small modulus.
Problem. Find \( \operatorname{ord}_7(2) \).
Compute powers: \(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\equiv1\pmod7\). The value \(1\) did not appear earlier, so the order is \(3\).
Comment. The order is the first exponent giving \(1\), not just any exponent.
Example 2. A Large Power Through a Cycle
This teaches reducing the exponent modulo the order.
Problem. Find the remainder of \(2^{100}\) modulo \(7\).
From the previous example, \(2^3\equiv1\pmod7\). Since \(100\equiv1\pmod3\), we get \(2^{100}\equiv2^1\equiv2\pmod7\).
Comment. Once the order is known, large powers become short.
Example 3. Order Modulo a Prime
This shows that the order divides \(p-1\).
Problem. Find \( \operatorname{ord}_{11}(3) \).
We have \(3^1\equiv3\), \(3^2\equiv9\), \(3^3\equiv27\equiv5\), \(3^4\equiv15\equiv4\), \(3^5\equiv12\equiv1\pmod{11}\). Thus the order is \(5\), and it indeed divides \(10\).
Comment. This illustrates the fact \(d\mid p-1\).
Example 4. A Divisor of \(a^n-1\)
This shows how order restricts a prime divisor.
Problem. Let a prime \(p\mid 2^m-1\). Prove that \( \operatorname{ord}_p(2)\mid m \) and \( \operatorname{ord}_p(2)\mid p-1 \).
From \(p\mid2^m-1\), we get \(2^m\equiv1\pmod p\), so the order of \(2\) modulo \(p\) divides \(m\). Since \(p\) is prime and \(2\not\equiv0\pmod p\), the order also divides \(p-1\).
Comment. This often gives restrictions on \(p\).
Example 5. A Divisor of \(a^n+1\)
This teaches not forgetting the condition 'does not divide \(n\)'.
Problem. Let \(p\) be an odd prime divisor of \(a^n+1\), with \(p\nmid a\). What can be said about the order of \(a\) modulo \(p\)?
We have \(a^n\equiv-1\pmod p\). Then \(a^{2n}\equiv1\), so the order divides \(2n\). But the order does not divide \(n\), otherwise \(a^n\equiv1\), contradicting \(a^n\equiv-1\) for odd \(p\).
Comment. This is one of the main templates for problems on \(a^n+1\).
Example 6. Prime Divisors of Fermat Type
This prepares for strong problems.
Problem. Let a prime \(q\mid 2^{16}+1\). Prove that \(q\equiv1\pmod{32}\).
If \(q=2\), then \(2^{16}+1\) is odd, so \(q\ne2\). From \(2^{16}\equiv-1\pmod q\), we get \(2^{32}\equiv1\), but \(2^{16}\not\equiv1\). The order of \(2\) modulo \(q\) is \(32\), hence \(32\mid q-1\).
Comment. The exponent \(16=2^4\) forces the order to be exactly \(32\).
Example 7. All Primes from One Condition
This shows how Fermat shortens a problem.
Problem. Find all primes \(p\) such that \(p\mid2^p+1\).
For \(p=2\), \(2^2+1=5\), not divisible by \(2\). For odd \(p\), Fermat's little theorem gives \(2^p\equiv2\pmod p\). Then the condition gives \(2^p+1\equiv3\equiv0\pmod p\), so \(p=3\). Check: \(2^3+1=9\) is divisible by \(3\).
Comment. Order is not strictly necessary here, but the cycle idea is the same.
Example 8. Fermat Numbers Are Pairwise Coprime
An olympiad example using order and the sign \(-1\).
Problem. Prove that the numbers \(F_n=2^{2^n}+1\) are pairwise coprime.
Let \(m
Comment. The same residue cannot be both \(1\) and \(-1\) modulo an odd number.
Chapter
Wilson, Fermat and Euler in Problems
Key Idea
Fermat, Euler, and Wilson are not isolated facts to memorise; they are tools for turning large powers and factorials into small residues. In olympiad problems, the key is knowing which theorem applies and why the hypotheses hold.
Basic Facts
Fermat's little theorem: if \(p\) is prime and \(p\nmid a\), then \(a^{p-1}\equiv1\pmod p\). In the form \(a^p\equiv a\pmod p\), it holds for all integers \(a\). Euler's theorem: if \(\gcd(a,n)=1\), then \(a^{\varphi(n)}\equiv1\pmod n\). Wilson's theorem: \(p\) is prime if and only if \((p-1)!\equiv-1\pmod p\).
When to Use This Method
Use Fermat for powers modulo a prime. Use Euler for powers modulo a composite modulus when coprimality holds. Use Wilson for factorials modulo a prime, especially when \((p-1)!\), \((p-2)!\), or the product of all nonzero residues appears.
How to Recognise the Method
If the exponent resembles \(p-1\), \(p\), or a multiple of \(p-1\), try Fermat. If the modulus is composite and the base is coprime to it, look for \(\varphi(n)\). If a factorial almost reaches a prime \(p\), try Wilson.
Typical Mistakes
Do not apply Euler's theorem without checking \(\gcd(a,n)=1\). Do not replace \(\varphi(n)\) by \(n-1\) when \(n\) is not prime. In Wilson's theorem, primality of the modulus is essential: for composite \(n\), the congruence usually fails.
Mini-checklist
1. Is the modulus prime or composite? 2. Is the base coprime to the modulus? 3. Which exponent can be reduced: \(p-1\) or \(\varphi(n)\)? 4. Can the factorial be replaced using Wilson? 5. Has the small case \(p=2\) been checked?
Example 1. Fermat in One Line
This teaches reducing the exponent modulo \(p-1\).
Problem. Find \(2^{2026}\pmod{11}\).
Since \(11\) is prime and \(2^{10}\equiv1\pmod{11}\), reduce the exponent: \(2026\equiv6\pmod{10}\). Thus \(2^{2026}\equiv2^6=64\equiv9\pmod{11}\).
Comment. Coprimality is obvious here: \(11\nmid2\).
Example 2. Euler Instead of Fermat
This shows work with a composite modulus.
Problem. Find \(2^{100}\pmod9\).
We have \(\varphi(9)=6\) and \(\gcd(2,9)=1\). Hence \(2^6\equiv1\pmod9\). Since \(100\equiv4\pmod6\), we get \(2^{100}\equiv2^4=16\equiv7\pmod9\).
Comment. Euler requires the base and modulus to be coprime.
Example 3. An Inverse Through Fermat
This shows how to find an inverse residue.
Problem. Find the inverse of \(5\) modulo \(17\).
By Fermat, \(5^{16}\equiv1\pmod{17}\), so \(5^{15}\) is the inverse of \(5\). But directly, \(5\cdot7=35\equiv1\pmod{17}\). Answer: \(7\).
Comment. The theorem gives existence and a general method, but a small modulus can be computed directly.
Example 4. Wilson for a Full Factorial
First application of Wilson's theorem.
Problem. Find the residue of \(10!\) modulo \(11\).
Since \(11\) is prime, Wilson's theorem gives \(10!\equiv-1\equiv10\pmod{11}\).
Comment. A factorial almost up to a prime points immediately to Wilson.
Example 5. An Incomplete Factorial
This teaches removing the last factors from Wilson.
Problem. Find \(8!\pmod{11}\).
By Wilson, \(10!\equiv-1\pmod{11}\). But \(10!=10\cdot9\cdot8!\equiv(-1)(-2)8!\equiv2\cdot8!\pmod{11}\). Hence \(2\cdot8!\equiv-1\equiv10\), so \(8!\equiv5\pmod{11}\).
Comment. Incomplete factorials are often recovered from the full one.
Example 6. The Form \(a^p-a\)
This shows the universal form of Fermat.
Problem. Prove that \(p\mid a^p-a\) for every prime \(p\) and every integer \(a\).
If \(p\mid a\), the claim is obvious. If \(p\nmid a\), Fermat gives \(a^{p-1}\equiv1\pmod p\). Multiplying by \(a\), we get \(a^p\equiv a\pmod p\).
Comment. This form is convenient when \(a\) may be divisible by \(p\).
Example 7. Wilson and Primality
This shows how Wilson recognises primes.
Problem. Check the congruence \(6!\equiv-1\pmod7\).
Since \(7\) is prime, Wilson gives \(6!\equiv-1\pmod7\). Indeed, \(720=7\cdot102+6\), so \(6\equiv-1\pmod7\).
Comment. For a composite modulus, this conclusion is not allowed.
Example 8. A Mixed Problem
This combines Euler and residues.
Problem. Find the last two digits of \(3^{80}\).
Work modulo \(100\). Since \(\gcd(3,100)=1\) and \(\varphi(100)=40\), \(3^{40}\equiv1\pmod{100}\). Therefore \(3^{80}\equiv1\pmod{100}\). The last two digits are \(01\).
Comment. For modulus \(100\), Fermat modulo a prime is not enough.
Chapter
p-adic Valuations
Key Idea
\(v_p(n)\) is the exponent of the prime \(p\) in the factorisation of \(n\). Instead of asking whether a number is divisible, we ask how many times it is divisible by \(p\). This turns problems about prime powers, factorials, and binomial coefficients into exact computations.
Basic Facts
If \(p\) is prime, then \(v_p(ab)=v_p(a)+v_p(b)\), and \(v_p(a^k)=k v_p(a)\). For factorials we use Legendre's formula: \(v_p(n!)=\lfloor n/p \rfloor+\lfloor n/p^2 \rfloor+\lfloor n/p^3 \rfloor+\cdots\). The number of trailing zeros of \(n!\) in decimal notation is \(v_5(n!)\), because there are more factors \(2\) than factors \(5\).
When to Use This Method
Use valuations when the problem asks for the largest \(k\) such that \(p^k\mid N\), or when factorials, products of consecutive integers, binomial coefficients, trailing zeros, or divisibility by a composite number \(2^a3^b5^c\) appear.
How to Recognise the Method
Phrases such as largest power, number of zeros, divisible by \(m^k\), or find the exponent of a prime almost always point to \(v_p\). If the number is composite, factor it into primes and take the minimum of the resulting restrictions.
Typical Mistakes
Do not count only multiples of \(p\): multiples of \(p^2\) contribute extra. For decimal zeros, the limiting factor is the number of fives, not twos. For \(m^k\mid N\), where \(m\) is composite, every prime divisor of \(m\) must be considered.
Mini-checklist
1. Which prime \(p\) matters? 2. Should the modulus be factored? 3. For a factorial, has Legendre's formula included all powers of \(p\)? 4. For a composite base, has the minimum been taken? 5. Is the found exponent truly maximal?
Example 1. First Computation of \(v_p\)
This teaches reading a factorisation.
Problem. Find \(v_2(72)\) and \(v_3(72)\).
We have \(72=2^3\cdot3^2\). Therefore \(v_2(72)=3\), and \(v_3(72)=2\).
Comment. This is not the number of divisors, but the exponent of a specific prime.
Example 2. Legendre's Formula
This shows how to count the exponent of a prime in a factorial.
Problem. Find \(v_3(100!)\).
By Legendre's formula, \(v_3(100!)=\lfloor100/3\rfloor+\lfloor100/9\rfloor+\lfloor100/27\rfloor+\lfloor100/81\rfloor=33+11+3+1=48\).
Comment. Multiples of \(9\) and \(27\) contribute extra factors of \(3\).
Example 3. Decimal Zeros
This connects valuations with decimal notation.
Problem. How many zeros are at the end of \(100!\)?
The number of zeros equals the number of factors \(10=2\cdot5\). There are more twos than fives in a factorial, so count fives: \(v_5(100!)=20+4=24\). Answer: \(24\).
Comment. For decimal notation, fives are almost always the limiting factor.
Example 4. Divisibility by a Composite Power
This teaches taking the minimum over prime divisors.
Problem. Find the largest \(k\) such that \(12^k\mid100!\).
Since \(12=2^2\cdot3\), we need \(2k\le v_2(100!)\) and \(k\le v_3(100!)\). Now \(v_2(100!)=50+25+12+6+3+1=97\), and \(v_3(100!)=48\). Hence \(k\le48\) from twos and \(k\le48\) from threes. Answer: \(48\).
Comment. Always factor a composite base.
Example 5. A Binomial Coefficient
This shows valuation for a quotient of factorials.
Problem. Find \(v_2\left(\binom{16}{6}\right)\).
Use \(\binom{16}{6}=16!/(6!10!)\). Then \(v_2(16!)=8+4+2+1=15\), \(v_2(6!)=3+1=4\), \(v_2(10!)=5+2+1=8\). Thus \(v_2\left(\binom{16}{6}\right)=15-4-8=3\).
Comment. For binomial coefficients, exponents are subtracted.
Example 6. Zeros in Another Base
This shows that the base need not be decimal.
Problem. How many zeros are at the end of \(100!\) in base \(12\)?
The base is \(12=2^2\cdot3\). We need the maximum \(k\) such that \(12^k\mid100!\). From above, \(v_2(100!)=97\), \(v_3(100!)=48\). Hence \(k=\min(\lfloor97/2\rfloor,48)=48\).
Comment. This is the same as \(12^k\mid100!\), but in a different form.
Example 7. Why \(2^n\nmid n!\)
This prepares for proof problems.
Problem. Prove that for every \(n\ge1\), the number \(n!\) is not divisible by \(2^n\).
By Legendre's formula, \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Each term is strictly less than the corresponding term of the geometric sum \(n/2+n/4+\cdots=n\). Therefore \(v_2(n!)
Comment. Estimating the sum of floors is often easier than finding the exact value.
Example 8. A Product of Consecutive Integers
Olympiad idea: prove divisibility through \(v_p\).
Problem. Prove that the product of any \(n\) consecutive integers is divisible by \(n!\).
Let the product be \(A=(m+1)(m+2)\cdots(m+n)\). For every prime \(p\), we prove \(v_p(A)\ge v_p(n!)\). Among \(n\) consecutive integers, at least \(\lfloor n/p\rfloor\) are divisible by \(p\), at least \(\lfloor n/p^2\rfloor\) are divisible by \(p^2\), and so on. Hence \(v_p(A)\ge\sum_i\lfloor n/p^i\rfloor=v_p(n!)\). This holds for every prime \(p\), so \(n!\mid A\).
Comment. This proof is equivalent to the integrality of a binomial coefficient.
Chapter
LTE: Lifting the Exponent
Key Idea
LTE, lifting the exponent, gives the exact exponent of a prime \(p\) in a difference of powers. It is especially powerful when \(p\mid a-b\) or \(p\mid a+b\), and the expression has the form \(a^n-b^n\).
Basic Facts
Basic form: if \(p\) is an odd prime, \(p\mid a-b\), and \(p\nmid ab\), then \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)\). If \(p\) is odd, \(p\mid a+b\), \(n\) is even, and \(p\nmid ab\), then \(v_p(a^n-b^n)=v_p(a+b)+v_p(n)\). For \(p=2\): if \(a,b\) are odd and \(n\) is even, then \(v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+v_2(n)-1\).
When to Use This Method
Use LTE when \(a^n-b^n\), transformed \(a^n+b^n\), large exponents, conditions \(p^k\mid a^n-b^n\), or requests to find all \(n\) with a sufficiently large prime exponent appear.
How to Recognise the Method
Check whether the prime \(p\) divides \(a-b\) or \(a+b\). If it does, ordinary factorisation often gives only the first step, while LTE gives the exact exponent immediately.
Typical Mistakes
Do not apply the odd-prime formula to \(p=2\). In the \(p\mid a+b\) case for \(a^n-b^n\), the exponent \(n\) must be even. Also check \(p\nmid a\) and \(p\nmid b\); otherwise the formula may fail.
Mini-checklist
1. Which prime \(p\) is counted? 2. Does it divide \(a-b\) or \(a+b\)? 3. Is the exponent even when using \(a+b\)? 4. Does \(p\) avoid the bases? 5. Has the condition \(p^k\mid\) been converted into an inequality for \(v_p\)?
Example 1. Classical Difference
First direct application of LTE.
Problem. Find \(v_3(10^{2025}-1)\).
Since \(3\mid10-1\), LTE gives \(v_3(10^{2025}-1)=v_3(9)+v_3(2025)=2+4=6\).
Comment. Without LTE, the factorisation would be very long.
Example 2. A Divisor of \(a+1\)
This shows the case \(p\mid a+b\).
Problem. Find \(v_3(2^{100}-1)\).
Here \(3\mid2+1\), and the exponent \(100\) is even. Hence \(v_3(2^{100}-1)=v_3(2+1)+v_3(100)=1+0=1\).
Comment. The exponent being even is essential.
Example 3. The Case \(p=2\)
A separate formula for twos.
Problem. Find \(v_2(3^{100}-1)\).
For odd \(3\) and \(1\), with even \(100\): \(v_2(3^{100}-1)=v_2(3-1)+v_2(3+1)+v_2(100)-1=1+2+2-1=4\).
Comment. The formula for \(2\) differs from the odd-prime case.
Example 4. A Condition on \(n\)
This shows how LTE solves divisibility.
Problem. Find all \(n\) such that \(7^3\mid8^n-1\).
Since \(7\mid8-1\), \(v_7(8^n-1)=v_7(7)+v_7(n)=1+v_7(n)\). We need \(1+v_7(n)\ge3\), so \(v_7(n)\ge2\). Answer: \(49\mid n\).
Comment. A prime-power condition became a condition on \(n\).
Example 5. A Composite Power
This shows the transition from \(p^k\) to \(v_p\).
Problem. Find the largest \(k\) such that \(9^k\mid10^{2025}-1\).
From Example 1, \(v_3(10^{2025}-1)=6\). Since \(9^k=3^{2k}\), we need \(2k\le6\). Answer: \(k=3\).
Comment. First count the prime exponent, then account for the composite base.
Example 6. A Formula with a Parameter
This prepares for answers involving \(v_p(n)\).
Problem. Find \(v_5(11^n-1)\).
Since \(5\mid11-1\), LTE gives \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).
Comment. The answer depends on the exponent \(n\).
Example 7. Solving an Inequality
This teaches finding all \(n\).
Problem. Find all \(n\) such that \(7^n\mid8^n-1\).
By LTE, \(v_7(8^n-1)=1+v_7(n)\). We need \(1+v_7(n)\ge n\). For \(n=1\), it holds. For \(n\ge2\), \(v_7(n)\le \log_7 n
Comment. The last step compares the growth of \(n\) and \(v_7(n)\).
Example 8. Powers of Two in \(3^{2^m}-1\)
An olympiad template for \(p=2\).
Problem. Prove that for \(m\ge1\), \(v_2(3^{2^m}-1)=m+2\).
Apply the formula for \(2\): \(v_2(3^{2^m}-1)=v_2(3-1)+v_2(3+1)+v_2(2^m)-1=1+2+m-1=m+2\).
Comment. This is a very common subproblem in stronger examples.
Chapter
Diophantine Equations I: Factorisation and Bounds
Key Idea
In first Diophantine problems, the goal is not to guess solutions but to turn the equation into a finite search. This is usually done by factorisation, size bounds, or a divisibility condition that sharply restricts possible values.
A typical move is to complete a product. For instance, from \(xy+ax+by=c\) we add \(ab\) and get \((x+b)(y+a)=c+ab\). Then only the divisors of a fixed number remain.
Basic Facts
1. If \(uv=N\), where \(u,v\) are positive integers, then there are only finitely many choices: it is enough to inspect the divisors of \(N\).
2. Difference of squares: \(x^2-y^2=(x-y)(x+y)\). The factors \(x-y\) and \(x+y\) have the same parity.
3. For equations with fractions, multiply by the common denominator and complete a product: from \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) we obtain \((x-n)(y-n)=n^2\).
4. If \(a\mid f(n)\), where \(a\) depends on \(n\), it is often useful to reduce \(n\) modulo \(a\) or subtract a suitable multiple.
5. Bounds start the search: if \(x\le y\le z\), then \(\frac{3}{x}\ge \frac{1}{x}+\frac{1}{y}+\frac{1}{z}\).
When To Use This Method
The method is especially useful when a problem contains a product \(xy\), a difference of squares, fractions of the form \(\frac{1}{x}\), a divisibility condition, or a request to find all integer solutions. It also works well with positive variables: then an ordering such as \(x\le y\le z\) gives upper bounds.
How To Recognise The Method
Look for expressions that are almost products: \(xy+ax+by\), \(x^2-y^2\), \(xy-nx-ny\), \(x^2+2x-y^2\). If moving terms gives an “almost factorisation”, try adding and subtracting one constant.
If no direct factorisation is visible, make one variable the main one: express \(y\), obtain a divisibility condition, or treat the equation as a quadratic with an integer discriminant.
Typical Mistakes
Do not forget positivity and parity restrictions. In a difference of squares, the factors cannot be chosen independently: \(x-y\) and \(x+y\) must have the same parity.
In fraction problems, do not divide by a variable without noting that it is nonzero. In “find all” problems, every candidate obtained from a divisor search must be checked in the original condition.
Mini-Checklist
1. Have all terms been moved so that a product can be seen?
2. Can one add a constant and obtain \((x+a)(y+b)\)?
3. Are there parity, ordering, or positivity restrictions?
4. If divisibility appears, can the expression be reduced modulo the divisor?
5. After checking divisors, have all candidates been verified?
Example 1. Completing A Product
This example shows the basic move: turn mixed terms into a product of two brackets.
Problem. Find all positive integer solutions of \(xy+3x+2y=29\).
Add \(6\) to both sides:
\[xy+3x+2y+6=35,\quad (x+2)(y+3)=35.\]
Since \(x,y>0\), we have \(x+2\ge 3\), \(y+3\ge 4\). The factorisations of \(35\) give \((5,7)\) and \((7,5)\). Hence \((x,y)=(3,4)\) and \((5,2)\).
Comment. The constant \(6\) appears as the product of the coefficients of \(x\) and \(y\).
Example 2. Fractions Become Divisors
Equations with \(\frac{1}{x}\) often become divisor problems after multiplying by the common denominator.
Problem. Find all positive integer pairs \((x,y)\) such that \(\frac{1}{x}+\frac{1}{y}=\frac{1}{7}\).
Multiply by \(7xy\): \(7x+7y=xy\). Thus
\[xy-7x-7y=0,\quad (x-7)(y-7)=49.\]
So \(x=7+d\), \(y=7+\frac{49}{d}\), where \(d\mid 49\). The ordered pairs are \((8,56)\), \((14,14)\), \((56,8)\).
Example 3. Difference Of Squares
Here one must remember that \(x-y\) and \(x+y\) have the same parity.
Problem. Find all positive \(x>y\) such that \(x^2-y^2=56\).
We write \((x-y)(x+y)=56\). The two factors have the same parity, so both must be even. The suitable factor pairs are \((2,28)\) and \((4,14)\). They give \(x=15,y=13\) and \(x=9,y=5\).
Example 4. Divisibility With A Variable Divisor
If the divisor contains \(n\), reduce \(n\) to a convenient residue modulo that divisor.
Problem. Find all positive \(n\) such that \(n+4\mid n^2+5\).
Modulo \(n+4\), we have \(n\equiv -4\), so \(n^2+5\equiv 16+5=21\). Therefore \(n+4\mid 21\). Since \(n+4>4\), we get \(n+4=7\) or \(21\). Hence \(n=3\) and \(n=17\), and both work.
Example 5. A Hidden Product After Multiplication
Sometimes factorisation appears only after multiplying by the product of the variables.
Problem. Find all positive \(x,y\) if \(\frac{1}{x}+\frac{1}{y}+\frac{2}{xy}=\frac{1}{5}\).
Multiply by \(5xy\): \(5x+5y+10=xy\). Hence
\[xy-5x-5y=10,\quad (x-5)(y-5)=35.\]
Checking the divisors of \(35\), we obtain \((x,y)=(6,40),(10,12),(12,10),(40,6)\).
Example 6. A Bound Before A Search
Before factorising, it is often necessary to know which values are possible at all.
Problem. Find all \(x\le y\le z\) such that \(\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1\).
Since \(x\le y\le z\), we have \(\frac{3}{x}\ge 1\), so \(x\le 3\). If \(x=1\), the remaining two fractions would have to sum to \(0\). If \(x=2\), then \(\frac{1}{y}+\frac{1}{z}=\frac{1}{2}\), so \((y-2)(z-2)=4\), giving \((y,z)=(3,6),(4,4)\). If \(x=3\), then \(\frac{1}{y}+\frac{1}{z}=\frac{2}{3}\), and with \(y\ge 3\) only \(y=z=3\) works. The answer is \((2,3,6),(2,4,4),(3,3,3)\).
Example 7. A Geometric Formula As A Diophantine Equation
Even a problem about Pythagorean triples can be solved by simple factorisation when the perimeter is fixed.
Problem. Find right triangles with integer sides and perimeter \(40\).
Let the legs be \(x,y\), and let the hypotenuse be \(40-x-y\). Then
\[x^2+y^2=(40-x-y)^2.\]
After simplification, \(xy-40x-40y+800=0\), so \((x-40)(y-40)=800\). Since \(x,y<40\), put \(a=40-x\), \(b=40-y\). Then \(ab=800\), and the hypotenuse is \(a+b-40\). The suitable choice is \(a=32,b=25\) and its swap, giving the sides \(8,15,17\).
Example 8. A Construction With Intervals
In stronger problems, factorisation can be combined with the idea of covering all primes by a suitable block of consecutive integers.
Problem. For even \(m>2\), construct \(m\) consecutive integers whose product is divisible by every prime \(p\le 2m+1\).
If \(m+1\) is composite, take \(m+2,m+3,\ldots,2m+1\). Every prime \(p\le m\) divides the product of any \(m\) consecutive integers, and every prime from \(m+2\) to \(2m+1\) appears as one of the factors. The number \(m+1\) does not need to be covered as a prime.
If \(m+1\) is prime, take \(m+3,m+4,\ldots,2m+2\). Primes \(p\le m\) are again covered by a block of length \(m\); the prime \(m+1\) divides \(2m+2\); and \(m+2\) is even and greater than \(2\), so it is not prime.
Chapter
Diophantine Equations II: Descent and Vieta Jumping
Key Idea
Infinite descent proves impossibility as follows: if a solution exists, then a smaller solution of the same type exists. Repeating this step would give an infinite decreasing sequence of positive integers, which is impossible.
Vieta jumping is descent for a quadratic equation. If an equation is symmetric in \(x,y\), fix \(x\) and view it as a quadratic in \(y\). The second root is often a positive integer smaller than the original one.
Basic Facts
1. If in a minimal solution all variables are divisible by \(d>1\), then division by \(d\) gives a smaller solution, a contradiction.
2. If \(y\) is a root of \(Y^2-mxY+x^2+c=0\), then the second root is \(mx-y\), and the product of the roots is \(x^2+c\).
3. For a Vieta jump to be valid, one must check three things: the second root is an integer, positive, and genuinely smaller.
4. In problems with \(x^2+y^2\), primes \(p\equiv 3\pmod 4\) are often useful: if \(p\mid x^2+y^2\), then usually \(p\mid x\) and \(p\mid y\).
When To Use This Method
Try descent when a congruence shows that all variables share a common divisor. Try Vieta jumping when the equation resembles \(x^2+y^2+c=mxy\) or another symmetric quadratic equation in one variable.
How To Recognise The Method
Signs of descent: a request to prove that no solutions exist, a homogeneous equation, powers, a prime \(p\equiv 3\pmod 4\), or a situation where every solution seems to have a common factor.
Signs of Vieta jumping: the equation is symmetric, contains quadratic terms, and after fixing one variable the second root has a simple expression.
Typical Mistakes
It is not enough to say “we get a smaller solution”: one must specify which positive quantity decreases. In Vieta jumping, the positivity of the second root is often forgotten.
Another common mistake is dividing a non-homogeneous equation and assuming the same equation remains without checking it.
Mini-Checklist
1. What is being minimised: sum, maximum, or one variable?
2. Why does a solution produce a new integer solution?
3. Why is the new solution positive?
4. Why is it smaller?
5. Which base cases stop the descent?
Example 1. Classical Descent
The idea is to build a smaller solution from a solution.
Problem. Prove that \(x^2=2y^2\) has no solutions in positive integers.
Assume a solution exists and choose one with minimal \(x+y\). From \(x^2=2y^2\), \(x\) is even: \(x=2u\). Then \(4u^2=2y^2\), so \(y^2=2u^2\), hence \(y\) is even: \(y=2v\). We get \(u^2=2v^2\), a smaller positive solution. Contradiction.
Example 2. Descent Modulo \(3\)
Squares modulo \(3\) are \(0\) or \(1\).
Problem. Prove that \(x^2+y^2=3z^2\) has no nonzero integer solutions.
Modulo \(3\), \(x^2+y^2\equiv 0\). This is possible only if \(x\equiv y\equiv 0\pmod 3\). Then the left side is divisible by \(9\), so \(3z^2\) is divisible by \(9\), hence \(z\) is divisible by \(3\). Dividing all variables by \(3\), we get a smaller solution. Infinite descent is impossible.
Example 3. The Second Root
Vieta jumping starts with the fact that one root is already known.
Problem. Let \(x,y\) be positive integers and \(x^2+y^2+1=4xy\). Prove that this is impossible.
Choose a solution with minimal sum and assume \(x\le y\). View the equation as a quadratic in \(y\): \(Y^2-4xY+x^2+1=0\). The second root is \(y'=4x-y\), and the product of the roots is \(x^2+1\), so \(y'=\frac{x^2+1}{y}>0\) and is an integer. Since \(y\ge x\), \(y'\le x+\frac{1}{x}\), so \(y'\le x\). Equality \(y'=x\) is impossible, since then \(y=3x\) and the equation gives \(2x^2=1\). Thus \(0
Example 4. An Equation With Real Solutions
Vieta jumping does not always prove impossibility; sometimes it describes all solutions.
Problem. Describe the solutions of \(x^2+y^2+1=3xy\).
Assume \(x\le y\). The second root in \(y\) is \(y'=3x-y=\frac{x^2+1}{y}\). If \(x>1\), then \(0
Example 5. A Jump In Markov's Equation
For three variables, jump in the largest variable.
Problem. If \(x^2+y^2+z^2=3xyz\), show that replacing \(z\) by \(z'=3xy-z\) gives another solution.
View the equation as a quadratic in \(z\): \(Z^2-3xyZ+x^2+y^2=0\). The sum of the roots is \(3xy\), so the second root is \(z'=3xy-z\). By Vieta's formulas, it is an integer and satisfies the same equation with \(x,y\).
Example 6. Primes \(3 \pmod 4\)
Such a prime cannot divide a sum of two squares only halfway.
Problem. Let \(p\equiv 3\pmod 4\) be prime and \(p\mid x^2+y^2\). Prove that \(p\mid x\) and \(p\mid y\).
If, say, \(p\nmid y\), then \(y\) has an inverse modulo \(p\), and \((xy^{-1})^2\equiv -1\pmod p\). Raise both sides to the power \(\frac{p-1}{2}\). The left side becomes \(1\), while the right side is \((-1)^{(p-1)/2}=-1\), because \(p\equiv 3\pmod 4\). Contradiction. Hence \(p\mid y\), and then the divisibility gives \(p\mid x\).
Example 7. Powers And Descent
If the equation is homogeneous, division by a common factor preserves its form.
Problem. Prove that \(x^4+y^4=3z^4\) has no nonzero integer solutions.
A fourth power modulo \(3\) is \(0\) or \(1\). From \(x^4+y^4\equiv 0\pmod 3\), both \(x\) and \(y\) are divisible by \(3\). Then the left side is divisible by \(81\), so \(3z^4\) is divisible by \(81\), and \(z\) is divisible by \(3\). Dividing \(x,y,z\) by \(3\), we obtain a smaller solution of the same equation. Impossible.
Example 8. Base Cases
In descent, the starting solutions must not be lost.
Problem. Describe positive solutions of \(x^2+y^2+3=4xy\).
For \(x=1\), we get \((y-2)^2=0\), so \((1,2)\) is a base solution. For \(x\le y\) and \(x\ge 4\), the second root \(y'=4x-y=\frac{x^2+3}{y}\) is positive and smaller than \(x\). The cases \(x=2,3\) are checked separately: \(x=2\) gives \(y=1\) or \(7\), while \(x=3\) gives no integer \(y\). Hence all solutions are built from \((1,2)\) by reversing the jump: the sequence \(1,2,7,26,\ldots\), where \(a_{n+1}=4a_n-a_{n-1}\), gives all neighbouring pairs.
Chapter
Chinese Remainder Theorem and Construction
Key Idea
The Chinese Remainder Theorem turns several local conditions into one integer. In olympiad problems it is not only a way to “solve a system”, but also a language for constructions: we prescribe residues so that desired divisibilities become automatic.
The main principle is: if the moduli are pairwise coprime, then the system \(x\equiv r_i\pmod {m_i}\) is solvable and has a unique solution modulo \(M=m_1m_2\cdots m_k\).
Basic Facts
1. If \(\gcd(m,n)=1\), then \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) has a unique solution modulo \(mn\).
2. If the moduli are not coprime, \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) is solvable if and only if \(\gcd(m,n)\mid a-b\).
3. For pairwise coprime moduli, the number of solutions can be multiplied: for example, the number of solutions of \(x^2\equiv 1\pmod {mn}\) equals the product of the numbers of solutions modulo \(m\) and modulo \(n\).
4. In constructions, one often chooses primes \(p_i\) and imposes \(N+i\equiv 0\pmod {p_i}\). Then each \(N+i\) has a prescribed divisor.
When To Use This Method
Use CRT when a problem asks you to construct a number with several residues, prove existence of infinitely many integers, test compatibility of conditions, or organise divisibility of several expressions \(N+a_i\).
How To Recognise The Method
Signals include: “find a number with residues...”, “construct \(n\) so that \(n+i\) is divisible by...”, “prove that infinitely many exist”, “system of congruences”, and “simultaneously modulo several moduli”.
Typical Mistakes
Do not apply the standard CRT form without checking coprimality. If the moduli share a divisor, the residues must be compatible.
In compositeness constructions, it is not enough to get \(p_i\mid N+i\): one must also ensure \(N+i>p_i\), otherwise the number may equal its assigned divisor.
Mini-Checklist
1. Which moduli are involved, and are they pairwise coprime?
2. If the moduli are not coprime, are the residues compatible?
3. Modulo what number is the solution unique?
4. If a composite number is being constructed, is it larger than its assigned divisor?
5. Is one number needed or infinitely many? For infinitely many, add the period \(M\).
Example 1. Two Coprime Moduli
A basic CRT computation is best done by hand to see the period.
Problem. Find all \(x\) such that \(x\equiv 2\pmod 5\) and \(x\equiv 3\pmod 7\).
Let \(x=5t+2\). Then \(5t+2\equiv 3\pmod 7\), so \(5t\equiv 1\pmod 7\). Since \(5^{-1}\equiv 3\pmod 7\), \(t\equiv 3\pmod 7\). Hence \(x=5(7s+3)+2=35s+17\). The answer is \(x\equiv 17\pmod {35}\).
Example 2. Compatible Non-Coprime Residues
If the moduli are not coprime, first check the common divisor.
Problem. Does \(x\equiv 2\pmod 6\), \(x\equiv 5\pmod 9\) have solutions?
The common divisor is \(3\). The difference of residues is \(5-2=3\), divisible by \(3\), so the system is compatible. Let \(x=6t+2\). Then \(6t+2\equiv 5\pmod 9\), so \(6t\equiv 3\pmod 9\), or \(2t\equiv 1\pmod 3\). Thus \(t\equiv 2\pmod 3\), and \(x\equiv 14\pmod {18}\).
Example 3. Prescribed Divisors
CRT conveniently constructs numbers with prescribed divisors.
Problem. Construct \(N\) such that \(N+1\) is divisible by \(3\), \(N+2\) by \(5\), and \(N+3\) by \(7\).
We need \(N\equiv -1\pmod 3\), \(N\equiv -2\pmod 5\), \(N\equiv -3\pmod 7\), or \(N\equiv 2\pmod 3\), \(N\equiv 3\pmod 5\), \(N\equiv 4\pmod 7\). Solving successively gives \(N\equiv 53\pmod {105}\). For example, \(N=53\).
Example 4. A Block of Composite Numbers
For a number to be composite, its prescribed divisor must be smaller than the number itself.
Problem. Prove that there exist \(6\) consecutive composite integers.
Take \(N=7!-1\). Then \(N+2,N+3,\ldots,N+7\) are divisible by \(2,3,\ldots,7\), respectively. They are all larger than their assigned divisors, so they are composite. This gives a block of \(6\) consecutive composite integers.
Example 5. Counting Via CRT
When the moduli are coprime, solutions modulo different moduli can be combined independently.
Problem. How many solutions does \(x^2\equiv 1\pmod {105}\) have?
Since \(105=3\cdot 5\cdot 7\), solve \(x^2\equiv 1\) modulo \(3,5,7\). For each odd prime modulus there are two solutions: \(x\equiv \pm 1\). Therefore the total number of solutions modulo \(105\) is \(2\cdot 2\cdot 2=8\).
Example 6. A Linear Expression
Sometimes one must first translate a condition on an expression into a condition on \(n\).
Problem. Find all \(n\) such that \(2n+1\equiv 0\pmod 5\) and \(3n-1\equiv 0\pmod 7\).
The first congruence gives \(2n\equiv -1\equiv 4\pmod 5\), so \(n\equiv 2\pmod 5\). The second gives \(3n\equiv 1\pmod 7\), so \(n\equiv 5\pmod 7\). Solving the system, we get \(n\equiv 12\pmod {35}\).
Example 7. Proving Compatibility
The theorem for two non-coprime moduli often avoids unnecessary search.
Problem. Prove that \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) is solvable if and only if \(\gcd(m,n)\mid a-b\).
If a solution \(x\) exists, then \(x-a\) is divisible by \(m\), and \(x-b\) is divisible by \(n\). Hence \(a-b=(x-b)-(x-a)\) is divisible by \(d=\gcd(m,n)\). Conversely, suppose \(d\mid a-b\). Write \(m=dm_1\), \(n=dn_1\), where \(\gcd(m_1,n_1)=1\). We need \(x=a+mt\) such that \(a+mt\equiv b\pmod n\), or \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Since \(m_1\) is invertible modulo \(n_1\), such \(t\) exists.
Example 8. Infinitely Many Constructions
After one solution is found, add the common period.
Problem. Prove that there are infinitely many \(N\) such that \(N,N+2,N+6\) are all composite.
Impose \(N\equiv 0\pmod 5\), \(N+2\equiv 0\pmod 7\), \(N+6\equiv 0\pmod {11}\). The moduli are coprime, so a solution exists modulo \(385\), and every number \(N+385t\) has the same divisibility properties. For all sufficiently large \(t\), each number is greater than its assigned divisor, hence all three are composite. There are infinitely many such \(t\).
Chapter
Arithmetic Functions
Key Idea
Arithmetic functions translate the prime factorisation of a number into computable quantities: the number of divisors \(\tau(n)\), the sum of divisors \(\sigma(n)\), Euler's function \(\varphi(n)\), and the number of distinct prime divisors \(\omega(n)\).
The olympiad strength of these functions is that they often turn a problem about \(n\) into a problem about the exponents in \(n=p_1^{a_1}\cdots p_r^{a_r}\).
Basic Facts
If \(n=p_1^{a_1}\cdots p_r^{a_r}\), then \(\tau(n)=(a_1+1)\cdots(a_r+1)\).
\[\sigma(n)=\prod_{i=1}^{r}\frac{p_i^{a_i+1}-1}{p_i-1}.\]
\[\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).\]
The functions \(\tau,\sigma,\varphi\) are multiplicative: if \(\gcd(a,b)=1\), then \(f(ab)=f(a)f(b)\) for each of them.
A classical identity is \(\sum_{d\mid n}\varphi(d)=n\).
When To Use This Method
Use arithmetic functions when a problem mentions the number of divisors, the sum of divisors, coprimality with \(n\), perfect or abundant numbers, or asks to find all \(n\) satisfying conditions such as \(\varphi(n)=cn\), \(\tau(n)=k\), or oddness of \(\sigma(n)\).
How To Recognise The Method
If a condition depends only on divisors or prime factors, write the canonical factorisation of \(n\). If \(\varphi(n)/n\) appears, look at the set of prime divisors rather than the exponents.
Typical Mistakes
Do not confuse multiplicativity with complete multiplicativity: usually \(f(ab)=f(a)f(b)\) is true only when \(\gcd(a,b)=1\).
For \(\sigma(n)\), remember that \(\sigma(p^a)=1+p+\cdots+p^a\), not just \(p^a+1\). For \(\varphi(n)\), prime exponents affect \(n\), but the ratio \(n/\varphi(n)\) depends only on the distinct primes.
Mini-Checklist
1. Is \(n\) written as a product of prime powers?
2. Is a formula for \(\tau\), \(\sigma\), or \(\varphi\) needed?
3. Can multiplicativity be used?
4. In a “find all” problem, which prime factors can occur at all?
5. Have the small cases \(n=1,2\) been checked?
Example 1. Computation From Factorisation
First factor the number into prime powers.
Problem. Find \(\tau(360)\), \(\sigma(360)\), \(\varphi(360)\).
\(360=2^3\cdot 3^2\cdot 5\). Thus \(\tau(360)=4\cdot 3\cdot 2=24\). Also \(\sigma(360)=(1+2+4+8)(1+3+9)(1+5)=15\cdot 13\cdot 6=1170\). Finally, \(\varphi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=96\).
Example 2. Multiplicativity of \(\tau\)
A divisor of a product of coprime numbers splits uniquely into two divisors.
Problem. Prove that if \(\gcd(a,b)=1\), then \(\tau(ab)=\tau(a)\tau(b)\).
Every divisor \(d\mid ab\) can be written uniquely as \(d=d_1d_2\), where \(d_1\mid a\), \(d_2\mid b\). Conversely, every such pair gives a divisor of \(ab\). Therefore the number of divisors equals the number of pairs \((d_1,d_2)\), namely \(\tau(a)\tau(b)\).
Example 3. The Sum of \(\varphi\)
The identity \(\sum_{d\mid n}\varphi(d)=n\) is best understood through reduced fractions.
Problem. Prove that \(\sum_{d\mid n}\varphi(d)=n\).
Partition the numbers \(1,2,\ldots,n\) by \(d=\frac{n}{\gcd(k,n)}\). Then \(d\mid n\), and after dividing by \(\gcd(k,n)\), the number \(k\) gives a residue coprime to \(d\). For a fixed \(d\), there are exactly \(\varphi(d)\) such numbers \(k\). All \(n\) numbers are counted, so the sum is \(n\).
Example 4. When \(\varphi(n)=n/2\)
The ratio \(n/\varphi(n)\) depends only on distinct prime divisors.
Problem. Find all \(n\) such that \(\varphi(n)=\frac{n}{2}\).
The condition is equivalent to \(\frac{n}{\varphi(n)}=2\). But \(\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}\). If an odd prime \(p\mid n\), the product gets a factor with odd numerator and even denominator, and it is not equal to \(2\). The only possible prime divisor is \(2\). Hence \(n=2^a\), \(a\ge 1\), and all such \(n\) work.
Example 5. Odd Number of Divisors
Divisors usually pair as \(d\) and \(n/d\).
Problem. Prove that \(\tau(n)\) is odd if and only if \(n\) is a square.
If \(d\ne n/d\), the divisors \(d\) and \(n/d\) form a pair. An unpaired divisor can occur only when \(d=n/d\), that is \(d^2=n\). Therefore an odd number of divisors occurs exactly for squares.
Example 6. All Numbers With 12 Divisors
The problem reduces to factoring \(12\) into factors \(a_i+1\).
Problem. Describe all \(n\) such that \(\tau(n)=12\).
If \(n=\prod p_i^{a_i}\), then \(\prod(a_i+1)=12\). The possible exponent types are \(11\); \(5,1\); \(3,2\); \(2,1,1\). Hence \(n\) has one of the forms \(p^{11}\), \(p^5q\), \(p^3q^2\), \(p^2qr\), where \(p,q,r\) are distinct primes.
Example 7. Sum of Coprime Residues
Residues coprime to \(n\) pair as \(a\) and \(n-a\).
Problem. Prove that for \(n>1\), the sum of positive integers \(a\le n\) coprime to \(n\) is \(\frac{n\varphi(n)}{2}\).
If \(\gcd(a,n)=1\), then \(\gcd(n-a,n)=1\). The pair \(a\) and \(n-a\) has sum \(n\). There is no self-paired residue: \(a=n-a\) would give \(2a=n\), but then \(\gcd(a,n)>1\) for \(n>2\), and \(n=2\) is checked directly. There are \(\varphi(n)\) residues, so the sum is \(\frac{n\varphi(n)}{2}\).
Example 8. Composite Numbers and \(\sigma\)
Sometimes several obvious divisors are enough.
Problem. Prove that if \(n\) is composite, then \(\sigma(n)>n+\sqrt{n}\).
Let \(d\) be the smallest divisor of \(n\) greater than \(1\). Then \(d\le \sqrt{n}\), and \(\frac{n}{d}\ge \sqrt{n}\). The numbers \(1,n,d,\frac{n}{d}\) are divisors of \(n\). Hence \(\sigma(n)\ge n+1+d+\frac{n}{d}>n+\sqrt{n}\).
Chapter
Digits, Bases and Decimal Periods
Key Idea
The digits of a number are coefficients of powers of the base. If the base is replaced by a convenient residue, the decimal or base-\(b\) representation becomes a congruence: modulo \(b-1\) the base is \(1\), modulo \(b+1\) it is \(-1\), and modulo \(10^k-1\) a block of \(k\) digits behaves like one digit.
Decimal periods have the same nature: if \((n,10)=1\), then the period length of a fraction with denominator \(n\) is the order of \(10\) modulo \(n\).
Basic Facts
- If \(N=\overline{a_ra_{r-1}\ldots a_0}_b\), then \(N=a_rb^r+\cdots+a_1b+a_0\).
- \(N\equiv a_0+a_1+\cdots+a_r \pmod{b-1}\).
- \(N\equiv a_0-a_1+a_2-\cdots+(-1)^r a_r \pmod{b+1}\).
- The last \(k\) decimal digits determine the number modulo \(10^k\).
- If \((n,10)=1\), the period of \(\frac{a}{n}\) is the least \(h>0\) such that \(10^h\equiv1\pmod n\).
- The repunit \(R_m=11\ldots1=\frac{10^m-1}{9}\) often reduces a problem to divisibility of \(10^m-1\).
When to Use This Method
Use it when the problem involves digit sums, last digits, several last digits, palindromes, repeated blocks, base-\(b\) notation, decimal periods, or numbers of the form \(111\ldots111\).
How to Recognise the Method
Look for these signals: the representation of a number matters more than its size; the number is split into blocks; divisibility of a repeated-digit number is requested; a fraction is written as \(0.\overline{a_1a_2\ldots a_r}\); one must find a period or construct final digits of a square.
Typical Mistakes
- Confusing the number \(\overline{abc}\) with the product \(abc\).
- Forgetting that digit blocks may have leading zeros.
- Using decimal periods without checking \((n,10)=1\).
- Dividing a congruence by \(9\) when the modulus is not coprime to \(9\).
- Treating a digit-sum rule as a proof without writing the congruence for powers of the base.
Mini-Checklist
- Write the number as a sum of digits times powers of the base.
- Choose the modulus: \(b-1\), \(b+1\), \(10^k\), \(10^k-1\), or the period denominator.
- Replace the base by a convenient residue.
- For a decimal period, find the order of \(10\) modulo the denominator.
- For last-digit constructions, use the Chinese remainder theorem.
Example 1. Digit Sum as a Congruence
The basic technique is to derive the divisibility rule instead of memorising it.
Problem. Let \(N=\overline{a_ra_{r-1}\ldots a_0}_{10}\). Prove that \(N\equiv a_0+a_1+\cdots+a_r\pmod9\).
We have \(N=a_r10^r+\cdots+a_1\cdot10+a_0\). Since \(10\equiv1\pmod9\), we get \(10^i\equiv1\pmod9\) for all \(i\). Hence \(N\equiv a_r+\cdots+a_1+a_0\pmod9\).
Comment. In olympiad problems, the real tool is the congruence \(10\equiv1\), not the memorised school rule.
Example 2. Divisibility by 11
Here the base is replaced by \(-1\).
Problem. Prove that \(N=\overline{a_ra_{r-1}\ldots a_0}_{10}\) is divisible by \(11\) if and only if \(a_0-a_1+a_2-\cdots+(-1)^r a_r\) is divisible by \(11\).
Since \(10\equiv-1\pmod{11}\), we have \(10^i\equiv(-1)^i\pmod{11}\). Substituting this into the decimal expansion gives the required congruence.
Comment. The alternating sum is not a digit trick; it is simply the substitution \(10\equiv-1\).
Example 3. Divisibility of Repunits
Repunits are best written as \(\frac{10^n-1}{9}\).
Problem. Prove that \(R_m\mid R_n\), where \(R_t=\frac{10^t-1}{9}\), if and only if \(m\mid n\).
If \(m\mid n\), then \(10^m-1\mid10^n-1\), so \(R_m\mid R_n\).
Conversely, suppose \(R_m\mid R_n\). Then \(10^m-1=9R_m\) divides \(9R_n=10^n-1\). Write \(n=qm+r\), \(0\le r
Comment. This example unlocks many problems about numbers \(111\ldots111\).
Example 4. When a Repunit Can Be Prime
The first hidden observation is that a composite exponent gives a factorisation.
Problem. Suppose the number consisting of \(k\) ones is prime. Prove that \(k\) is prime.
If \(k=ab\), where \(a,b>1\), then
\[R_k=1+10+\cdots+10^{ab-1}=R_a\left(1+10^a+10^{2a}+\cdots+10^{a(b-1)}\right).\]
Both factors are greater than \(1\), so \(R_k\) is composite. Hence \(k\) cannot be composite.
Comment. We do not prove the converse: prime \(k\) does not imply prime \(R_k\).
Example 5. Period as an Order
This is the standard passage from decimal notation to a congruence.
Problem. Let \((n,10)=1\). Prove that the period length of \(\frac{a}{n}\) is the least \(h>0\) such that \(10^h\equiv1\pmod n\).
In long division, each shift of the decimal point multiplies the current remainder by \(10\) modulo \(n\). A period of length \(h\) means that after \(h\) steps the remainder returns to the same value: \(a10^h\equiv a\pmod n\). After reducing the fraction, this is equivalent to \(10^h\equiv1\pmod n\).
Comment. In problems it is usually better to speak about the order of \(10\) than about the visible period digits.
Example 6. Periods of \(1/7\), \(1/13\), \(1/37\)
This example shows how periods are found through powers of \(10\).
Problem. Find the period lengths of \(\frac17\), \(\frac1{13}\), and \(\frac1{37}\).
For \(7\): \(10\equiv3\), \(10^2\equiv2\), \(10^3\equiv6\), and \(10^6\equiv1\pmod7\); no smaller positive exponent works, so the period is \(6\).
For \(13\): \(10^3\equiv-1\pmod{13}\), hence \(10^6\equiv1\), and no smaller exponent gives \(1\); the period is \(6\).
For \(37\): \(10^3=1000\equiv1\pmod{37}\), while \(10\not\equiv1\) and \(10^2\not\equiv1\), so the period is \(3\).
Comment. The period of a fraction is an order computation, not a decimal expansion computation.
Example 7. Last Digits via CRT
Problems about final digits often split into moduli \(2^k\) and \(5^k\).
Problem. Find all residues \(x\pmod{100}\) such that \(x^2\equiv x\pmod{100}\).
The condition is \(x(x-1)\equiv0\pmod{100}\). Since \(100=4\cdot25\), we need \(x\equiv0\) or \(1\pmod4\), and \(x\equiv0\) or \(1\pmod{25}\). The four combinations give \(0\), \(1\), \(25\), and \(76\) modulo \(100\).
Comment. This is how numbers arise whose square ends in the same digits.
Example 8. Blocks of \(k\) Digits
This tool is needed in stronger digit-sum problems.
Problem. Suppose \(M\) is divisible by \(10^k-1\). Prove that the sum of its decimal digits is at least \(9k\).
Split \(M\) from right to left into blocks of \(k\) digits and add the blocks as ordinary integers. The result \(T\) is congruent to \(M\) modulo \(10^k-1\), because \(10^k\equiv1\pmod{10^k-1}\). Also, the digit sum of \(T\) is not greater than the digit sum of \(M\).
Repeating this operation, we eventually get a positive number below \(10^k\), still divisible by \(10^k-1\). It must be \(10^k-1\), whose digit sum is \(9k\). Therefore the original digit sum was at least \(9k\).
Comment. This is typical: a simple block idea becomes a strong estimate.
Chapter
Polynomials, Sequences and Number Theory
Key Idea
A polynomial with integer coefficients behaves well modulo \(m\): from \(a\equiv b\pmod m\) it follows that \(f(a)\equiv f(b)\pmod m\). Therefore divisibility problems about polynomial values often reduce to one value, usually \(f(0)\).
Sequences modulo \(m\) have only finitely many states. For recurrences this gives periodicity or eventual periodicity; if the transition is reversible, the periodicity is pure.
Basic Facts
- For \(f\in\mathbb Z[x]\), \(a-b\mid f(a)-f(b)\).
- If \(n\mid f(n)\) for all \(n\), then \(f(0)\) is usually the key value.
- The finite difference \(\Delta f(n)=f(n+1)-f(n)\) lowers the degree by \(1\).
- The polynomials \(\binom{x}{k}\) take integer values at integer \(x\), even though their coefficients may be fractional.
- The pair \((u_n,u_{n+1})\) of a recurrence modulo \(m\) has only finitely many possible values.
- For Fibonacci numbers, the identity \(F_{r+s}=F_{r-1}F_s+F_rF_{s+1}\) is often decisive.
When to Use This Method
Use it when the statement contains values \(f(n)\), divisibility for all \(n\), differences \(f(a)-f(b)\), sums of powers, recurrence sequences, periodicity modulo \(m\), or Fibonacci numbers.
How to Recognise the Method
Look for phrases such as “for all integers \(n\)”, “polynomial with integer coefficients”, “the sequence is defined recursively”, or “prove that some term is divisible by \(m\)”. Often the right move is not to compute values, but to compare states modulo \(m\).
Typical Mistakes
- Assuming that every integer-valued polynomial has integer coefficients.
- Checking divisibility for a few \(n\) without proving periodicity.
- Confusing periodicity of the sequence itself with periodicity of its residues.
- Using Fibonacci identities without fixing the indexing.
- Forgetting that a recurrence transition may be non-invertible modulo \(m\).
Mini-Checklist
- For a polynomial, first check \(f(a)\equiv f(b)\).
- If \(n\mid f(n)\), compare \(n\) with \(0\).
- For sums and powers, try finite differences.
- For recurrences, write down the state, such as \((u_n,u_{n+1})\).
- For Fibonacci numbers, use the Euclidean idea: \(F_m\) and \(F_n\) behave like their indices \(m\) and \(n\).
Example 1. Polynomial Values Modulo a Divisor
A basic fact that replaces many computations.
Problem. Let \(f\in\mathbb Z[x]\). Prove that \(a-b\mid f(a)-f(b)\).
It is enough to check a monomial: \(a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})\). A linear combination of such differences with integer coefficients is also divisible by \(a-b\). Hence \(a-b\mid f(a)-f(b)\).
Comment. This is the main bridge between polynomials and number theory.
Example 2. Divisibility of \(a^n-b^n\)
The classical factorisation is a special case of the polynomial principle.
Problem. Prove that \(a-b\mid a^n-b^n\) and \(a+b\mid a^{2r+1}+b^{2r+1}\).
The first statement is the difference of powers. For the second, set \(x=a\), \(y=-b\). Then \(a^{2r+1}+b^{2r+1}=a^{2r+1}-(-b)^{2r+1}\), which is divisible by \(a-(-b)=a+b\).
Comment. Changing a sign often turns the second formula into the first.
Example 3. The Condition \(n\mid f(n)\)
A typical problem where \(f(0)\) is the key.
Problem. Find the condition on \(f\in\mathbb Z[x]\) under which \(n\mid f(n)\) for all \(n\ge1\).
Since \(n-0\mid f(n)-f(0)\), we have \(f(n)\equiv f(0)\pmod n\). Therefore \(n\mid f(n)\) for all \(n\) if and only if \(n\mid f(0)\) for all \(n\). This is possible only when \(f(0)=0\). Conversely, if \(f(0)=0\), then \(n\mid f(n)-f(0)=f(n)\).
Comment. Many problems of this kind become one-line arguments after the right congruence.
Example 4. Finite Differences
Differences turn degree \(d\) into degree \(d-1\).
Problem. Let \(S_k(n)=1^k+2^k+\cdots+n^k\). Explain why \(S_k(n)\) is a polynomial in \(n\) of degree \(k+1\).
By the binomial theorem, \((t+1)^{k+1}-t^{k+1}\) equals \((k+1)t^k\) plus a polynomial of smaller degree. Summing over \(t=1,\ldots,n\), the left side telescopes to \((n+1)^{k+1}-1\), while the right side contains \((k+1)S_k(n)\) plus already known sums of lower powers. Induction on \(k\) shows that \(S_k(n)\) is a polynomial of degree \(k+1\).
Comment. The idea matters more than the explicit formula.
Example 5. Integer-Valued but Not Integer-Coefficient
Not all integer values come from integer coefficients.
Problem. Prove that \(P(n)=\frac{n(n-1)}2\) is an integer for every integer \(n\), although not all coefficients of \(P\) are integers.
The product of two consecutive integers is even, so \(\frac{n(n-1)}2\in\mathbb Z\). But the coefficient of \(n^2\) is \(\frac12\), so \(P\notin\mathbb Z[x]\).
Comment. This example prevents the dangerous automatic replacement of “integer-valued” by “integer-coefficient”.
Example 6. Fibonacci Periodicity Modulo \(m\)
Periodicity comes from finitely many states.
Problem. Prove that the Fibonacci sequence is periodic modulo every \(m\).
Consider the pairs \((F_n,F_{n+1})\) modulo \(m\). There are at most \(m^2\) such pairs, so two of them coincide. The transition \((x,y)\mapsto(y,x+y)\) is reversible: from \((y,x+y)\) we recover \((x,y)\). Therefore the repeated pair gives a pure period starting from \((0,1)\).
Comment. The reversibility of the transition matters: it removes the preperiod.
Example 7. Divisibility of Fibonacci Numbers
Indices often inherit divisibility.
Problem. Prove that if \(d\mid n\), then \(F_d\mid F_n\).
Use the identity \(F_{r+s}=F_{r-1}F_s+F_rF_{s+1}\). It implies that if \(F_d\mid F_r\), then \(F_d\mid F_{r+d}\), because \(F_{r+d}=F_{d-1}F_r+F_dF_{r+1}\). Starting with \(r=d\), induction gives \(F_d\mid F_{td}\) for all \(t\).
Comment. This prepares for \(\gcd(F_m,F_n)=F_{\gcd(m,n)}\).
Example 8. Infinitely Many Composite Terms
Sometimes one modulus and one residue class of indices are enough.
Problem. Prove that among the numbers \(2^{2^n}+3\), infinitely many are composite.
Work modulo \(19\). Since \(2^4\equiv16\equiv-3\pmod{19}\), we want \(2^n\equiv4\pmod{18}\), because the order of \(2\) modulo \(19\) divides \(18\). The sequence \(2^n\pmod{18}\) has period \(6\), and \(2^n\equiv4\pmod{18}\) when \(n\equiv2\pmod6\). Thus for all \(n\equiv2\pmod6\), the number \(2^{2^n}+3\) is divisible by \(19\). For \(n>2\), it is greater than \(19\), hence composite.
Comment. This is an example of a “period of the index inside an exponent”.