Maths Olympiad Prep

Library / /19 of 73

Number theory Difficulty 5.3 AIME, harder Prove it Brazil

Prove that if 102n+810n+110^{2n} + 8 \cdot 10^n + 1 has a prime factor of the form 60k+760k + 7, kk and nn both positive integers, then nn and kk are both even.

Solution

Let p=60k+7p = 60k + 7 be such a prime. Then 102n+810n+10(modp)    (10n1)210n+1(modp)10^{2n} + 8 \cdot 10^n + 1 \equiv 0 \pmod{p} \iff (10^n - 1)^2 \equiv -10^{n+1} \pmod{p}. Now suppose nn is odd. Then (10n1)21(10(n+1)/2)2(modp)(10^n - 1)^2 \equiv -1 \cdot (10^{(n+1)/2})^2 \pmod{p}, and 1-1 is a quadratic residue. But by the Euler criterion, (1p)=(1)(p1)/2=1\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = -1, a contradiction. So nn is even and, moreover, (10p)=1    (2p)(5p)=1    (2p)=(5p)\left(\frac{-10}{p}\right) = 1 \iff \left(\frac{2}{p}\right)\left(\frac{5}{p}\right) = -1 \iff \left(\frac{2}{p}\right) = -\left(\frac{5}{p}\right).
By the quadratic reciprocity lemma, (5p)(p5)=(1)512p12=1    (5p)=(p5)=(25)=1\left(\frac{5}{p}\right)\left(\frac{p}{5}\right) = (-1)^{\frac{5-1}{2} \cdot \frac{p-1}{2}} = 1 \iff \left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) = \left(\frac{2}{5}\right) = -1. So (2p)=1    (1)p218=1\left(\frac{2}{p}\right) = 1 \iff (-1)^{\frac{p^2-1}{8}} = 1, so p218=(30k+3)(15k+2)\frac{p^2-1}{8} = (30k+3)(15k+2) is even. Since 30k+330k+3 is odd, 15k+215k+2 is even, that is, kk is even.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.