Maths WorkshopMaths problems with full solutions
Exercise 1277Number theory › Divisibility and gcdOlympiadAdded 4 Nov 2026

Long runs of non-squarefree numbers

#Chinese remainder theorem#squarefree numbers

Statement

Prove that for every positive integer nn there exist nn consecutive positive integers, each divisible by the square of an integer greater than 11.

Hint

Choose nn distinct primes p1,…,pnp_1,\dots,p_n and impose x+i≡0(modpi2)x+i\equiv0\pmod{p_i^2} for each ii.

Show solutionHide solution

Solution

Idea. The Chinese remainder theorem lets us prescribe divisibility conditions independently, as long as the moduli are pairwise coprime.

Proof. Take distinct primes p1,…,pnp_1,\dots,p_n. The moduli p12,…,pn2p_1^2,\dots,p_n^2 are pairwise coprime, so by the Chinese remainder theorem there is a positive integer xx with
x≡−i(modpi2)(i=1,…,n).x\equiv-i\pmod{p_i^2}\qquad(i=1,\dots,n).
Then pi2∣x+ip_i^2\mid x+i for each ii, so x+1,x+2,…,x+nx+1,x+2,\dots,x+n are nn consecutive integers each divisible by a square greater than 11.

Example. n=3n=3 with primes 2,3,52,3,5: x≡−1(mod4)x\equiv-1\pmod4, x≡−2(mod9)x\equiv-2\pmod9, x≡−3(mod25)x\equiv-3\pmod{25} gives x=547x=547: 548=4⋅137548=4\cdot137, 549=9⋅61549=9\cdot61, 550=25⋅22550=25\cdot22 ✓.

Remark. So the gaps between consecutive squarefree numbers are unbounded.

Lesson. To find consecutive integers with prescribed divisibility properties, use the Chinese remainder theorem.