Chapter
Theory
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.
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.
Examples
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\).
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\).
Factorisation turns the equation into a divisor list.
Problem. Solve \(xy+2x+y=31\) in positive integers.
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.
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\).
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\).
Last digits are a residue-cycle problem.
Problem. Find the last two digits of \(13^{100}\).
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\).
When proving the existence of a block, a small explicit example is not necessary.
Problem. Prove that there exist \(8\) consecutive composite numbers.
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.
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?
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.
Problems
Prove that \(n^2+n\) is even for every integer \(n\).
Factor out \(n\).
\(n^2+n=n(n+1)\). Of two consecutive integers, one is even, so the product is even.
Find the last digit of \(2^{2026}\).
The last digits of powers of \(2\) cycle as \(2,4,8,6\).
Since \(2026\equiv2\pmod4\), the last digit is \(4\).
Prove that any two consecutive odd numbers are coprime or have GCD \(2\)? Correct the statement and prove the true version.
Two odd numbers cannot be consecutive integers; likely the intended numbers differ by \(2\).
Correct statement: two odd numbers differing by \(2\) are coprime. Let the numbers be \(n\) and \(n+2\), with \(n\) odd. Their common divisor divides \(2\). Since both numbers are odd, the common divisor is not divisible by \(2\). Hence the GCD is \(1\).
Which residues can an integer square have modulo \(3\)?
Check \(0,1,2\).
If \(n\equiv0,1,2\pmod3\), then \(n^2\equiv0,1,1\pmod3\). Only \(0\) and \(1\) are possible.
Find the digit \(x\) if \(72x5\) is divisible by \(9\).
The digit sum must be divisible by \(9\).
The digit sum is \(7+2+x+5=14+x\). We need \(14+x\equiv0\pmod9\). Since \(x\) is a digit, \(x=4\).
Prove that \(24\mid n(n+1)(n+2)(n+3)\) for every integer \(n\).
Prove divisibility by \(8\) and by \(3\).
Among four consecutive integers, one is divisible by \(3\). Also there are two even numbers, one of which is divisible by \(4\), so the product is divisible by \(8\). Since \(8\) and \(3\) are coprime, the product is divisible by \(24\).
Solve \(xy+x+y=47\) in positive integers.
Add \(1\).
We get \((x+1)(y+1)=48\). Factor pairs of \(48\) greater than \(1\) give \((x,y)=(1,23),(2,15),(3,11),(5,7),(7,5),(11,3),(15,2),(23,1)\).
Find \(\gcd(n^2+n+1,n+1)\).
Replace \(n\) by \(-1\) modulo \(n+1\).
Modulo \(n+1\), \(n\equiv-1\). Then \(n^2+n+1\equiv1-1+1=1\). Hence the common divisor divides \(1\), so the GCD is \(1\).
Prove that \(x^2=3y^2\) has no positive integer solutions.
If \(3\mid x^2\), then \(3\mid x\).
From \(x^2=3y^2\), we get \(3\mid x^2\), hence \(3\mid x\). Let \(x=3t\). Then \(9t^2=3y^2\), so \(y^2=3t^2\), hence \(3\mid y\). This gives a smaller solution \((t,\frac{y}{3})\). Repeating gives infinite divisibility by \(3\), impossible for positive integers.
Find all positive integers \(n\) such that \(n+3\mid n^2+2\).
Modulo \(n+3\): \(n\equiv-3\).
We have \(n^2+2\equiv9+2=11\pmod{n+3}\). Hence \(n+3\mid11\). Since \(n\ge1\), \(n+3\ge4\), so \(n+3=11\), \(n=8\). Check works.
Find the last two digits of \(11^{2025}\).
Check the pattern of \(11^k\pmod{100}\).
For \(k=1,\ldots,10\), we get \(11,21,31,\ldots,91,01\), a cycle of length \(10\). Since \(2025\equiv5\pmod{10}\), the last two digits are \(51\).
Solve the system \(n\equiv2\pmod5\), \(n\equiv3\pmod7\).
Let \(n=5k+2\).
Substitute: \(5k+2\equiv3\pmod7\), so \(5k\equiv1\pmod7\). The inverse of \(5\) modulo \(7\) is \(3\), hence \(k\equiv3\pmod7\). Thus \(n=5(7t+3)+2=35t+17\).
Find all \(n\pmod3\) for which \(3\mid n^2+n+1\).
Check residues \(0,1,2\).
For \(n\equiv0\), we get \(1\); for \(n\equiv1\), we get \(3\equiv0\); for \(n\equiv2\), we get \(7\equiv1\pmod3\). Thus only \(n\equiv1\pmod3\) works.
Let an odd prime \(p\) divide \(a^2+1\). Prove that \(p\equiv1\pmod4\).
From \(a^2\equiv-1\pmod p\), it follows that \(a^4\equiv1\pmod p\).
Since \(p\mid a^2+1\), we have \(a^2\equiv-1\pmod p\). Then \(a^4\equiv1\pmod p\), but \(a^2 ot\equiv1\pmod p\). Thus the order of \(a\) modulo \(p\) is \(4\). The order divides \(p-1\), hence \(4\mid p-1\), so \(p\equiv1\pmod4\).
Find all positive integers \(n\) such that \(2n-1\mid n^2+1\).
Multiply by \(4\).
Let \(d=2n-1\). If \(d\mid n^2+1\), then \(d\mid4(n^2+1)\). But \(4(n^2+1)=d^2+2d+5\). Thus \(d\mid5\). Hence \(d=1\) or \(5\), giving \(n=1\) or \(n=3\). Both work.
Find all positive integers \(x>y\) such that \(x^2-y^2=840\).
Set \(x-y=2u\), \(x+y=2v\).
Since \(x-y\) and \(x+y\) have the same parity and their product is \(840\), both factors are even. Let \(x-y=2u\), \(x+y=2v\). Then \(uv=210\), \(u
Prove that \(5\mid2^{4n}-1\) for every positive integer \(n\).
Find \(2^4\pmod5\).
Since \(2^4=16\equiv1\pmod5\), \(2^{4n}=(2^4)^n\equiv1^n\equiv1\pmod5\). Hence \(5\mid2^{4n}-1\).
Let \(\gcd(m,10)=1\). Prove that there exists a number consisting only of digits \(0\) and \(1\) that is divisible by \(m\).
It is enough to construct a number of only ones.
By the pigeonhole principle, among \(R_1,\ldots,R_m\), either one is divisible by \(m\), or two have the same residue. In the second case their difference is \(10^iR_j\) for some \(j\) and is divisible by \(m\). Since \(10^i\) is invertible modulo \(m\), \(m\mid R_j\). The number \(R_j\) consists only of ones, hence only of digits \(0\) and \(1\).
Describe all positive integers with exactly \(6\) positive divisors.
Use \( au(n)=(\alpha_1+1)\cdots(\alpha_s+1)\).
If \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), then \( au(n)=(\alpha_1+1)\cdots(\alpha_s+1)\). We need \(6\). The possibilities are \(6=6\) and \(6=3\cdot2\). Hence \(n=p^5\) or \(n=p^2q\), where \(p,q\) are distinct primes.
Prove that if the square of a positive integer ends in digit \(5\), then its last two digits are \(25\).
A number whose square ends in \(5\) itself ends in \(5\).
Let the number be \(10a+5\). Then \((10a+5)^2=100a^2+100a+25=100a(a+1)+25\). Thus the last two digits of the square are \(25\).
Let \(n\) be an odd positive integer. Prove that \(n\mid1^n+2^n+\cdots+(n-1)^n\).
Group \(a\) with \(n-a\).
For each \(a=1,\ldots,n-1\), the number \(n-a\) also appears. Since \(n\) is odd, \(a^n+(n-a)^n\equiv a^n+(-a)^n=0\pmod n\). All terms split into such pairs, so the whole sum is divisible by \(n\).
Find all primes \(p\) such that \(p\mid2^p+1\).
For an odd prime, use Fermat's little theorem.
For \(p=2\), \(2^2+1=5\), not divisible by \(2\). Let \(p\) be odd. By Fermat's little theorem, \(2^p\equiv2\pmod p\). Then \(2^p+1\equiv3\pmod p\). Thus \(p\mid3\), so \(p=3\). Check: \(3\mid9\).
Prove that there are infinitely many numbers consisting only of digits \(0\) and \(1\) that are divisible by \(2027\).
First build one multiple of ones, then append zeros on the right.
Since \(\gcd(2027,10)=1\), there exists a repunit \(R_s\) divisible by \(2027\). Then for every \(t\ge0\), the number \(R_s\cdot10^t\) is also divisible by \(2027\) and consists of ones followed by zeros. Different \(t\) give infinitely many different numbers.
Prove that for every \(k\ge1\), there exist \(k\) consecutive positive integers, each divisible by the square of some prime.
Choose distinct primes \(p_1,\ldots,p_k\) and impose \(n+i\equiv0\pmod{p_i^2}\).
Choose distinct primes \(p_1,\ldots,p_k\). Consider the system \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). The moduli \(p_i^2\) are pairwise coprime, so CRT gives a solution \(n_0\). Then each \(n_0+i\) is divisible by \(p_i^2\). Adding a sufficiently large multiple of \(p_1^2\cdots p_k^2\) to \(n_0\), we obtain positive consecutive integers.
Ladders