Maths Olympiad Prep

Library / /12 of 30

Number theory Difficulty 5.6 AIME, harder Prove it Ireland

Find all integers nn for which n5+n4+n3+n2+n+1n^5 + n^4 + n^3 + n^2 + n + 1 is divisible by 199.

Solution

Note that (n1)(n5+n4+n3+n2+n+1)=n61=(n31)(n3+1)=(n1)(n+1)(n2n+1)(n2+n+1)(n-1)(n^5 + n^4 + n^3 + n^2 + n + 1) = n^6 - 1 = (n^3 - 1)(n^3 + 1) = (n-1)(n+1)(n^2 - n + 1)(n^2 + n + 1), and so
n5+n4+n3+n2+n+1=(n+1)(n2n+1)(n2+n+1). n^5 + n^4 + n^3 + n^2 + n + 1 = (n+1)(n^2 - n + 1)(n^2 + n + 1).
Because 199 is a prime number, this expression is divisible by 199 iff one of the factors n+1n+1, n2n+1n^2-n+1 or n2+n+1n^2+n+1 is divisible by 199. Divisibility of n+1n+1 by 199 is equivalent to n198(mod199)n \equiv 198 \pmod{199}.
To solve the quadratic congruence n2n+10(mod199)n^2 - n + 1 \equiv 0 \pmod{199}, we observe n2n+1n2200n+1(n100)21002+1(mod199)n^2 - n + 1 \equiv n^2 - 200n + 1 \equiv (n - 100)^2 - 100^2 + 1 \pmod{199}. Because 10021=200501=19950+4949(mod199)100^2 - 1 = 200 \cdot 50 - 1 = 199 \cdot 50 + 49 \equiv 49 \pmod{199}, the congruence n2n+10(mod199)n^2 - n + 1 \equiv 0 \pmod{199} is equivalent to (n100)249(mod199)(n - 100)^2 \equiv 49 \pmod{199}. Again, because 199 is a prime, this has exactly two solutions (mod 199) which are determined by n100±7(mod199)n - 100 \equiv \pm 7 \pmod{199}. These two solutions are n107(mod199)n \equiv 107 \pmod{199} and n93(mod199)n \equiv 93 \pmod{199}.
Note now that that (n1)2+(n1)+1=n2n+1(n-1)^2+(n-1)+1 = n^2-n+1, hence n106(mod199)n \equiv 106 \pmod{199} and n92(mod199)n \equiv 92 \pmod{199} are the solutions of n2+n+10(mod199)n^2+n+1 \equiv 0 \pmod{199}.
This shows that n5+n4+n3+n2+n+1n^5+n^4+n^3+n^2+n+1 is divisible by 199 iff nn is congruent to 92, 93, 106, 107 or 198 (mod 199).

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 and solution reproduced as published; topic and difficulty added by this site.