Maths WorkshopMaths problems with full solutions
Exercise 1125Number theory › PrimesL1Added 3 Nov 2026

Coprime remainders

#coprime#remainders#CRT

Statement

Show that among any nn consecutive integers, exactly one is divisible by nn.

Hint

In the sequence a,a+1,…,a+n−1a,a+1,\ldots,a+n-1, the residues mod nn are all distinct.

Show solutionHide solution

Solution

Residues. If a+i≡a+j(modn)a+i\equiv a+j\pmod n with 0≤i<j<n0\le i<j<n, then n∣(j−i)n\mid(j-i), but 0<j−i<n0<j-i<n, impossible. So the residues are 0,1,…,n−10,1,\ldots,n-1 in some order.

Exactly one divisible. Exactly one residue is 00, so exactly one integer in the sequence is divisible by nn.

Conclusion. The statement holds.

Application. Among any nn consecutive integers, one is a multiple of each divisor d∣nd\mid n.