Maths Olympiad Prep

Library / /190 of 351

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 19.

Solution

First note that n1(mod19)n \equiv 1 \pmod{19} implies n5+n4+n3+n2+n+16(mod19)n^5 + n^4 + n^3 + n^2 + n + 1 \equiv 6 \pmod{19}. Assume now that n≢1(mod19)n \not\equiv 1 \pmod{19}, i.e. gcd(19,n1)=1\gcd(19, n-1) = 1. Because n61=(n1)(n5+n4+n3+n2+n+1)n^6 - 1 = (n-1)(n^5 + n^4 + n^3 + n^2 + n + 1) we then have
19n5+n4+n3+n2+n+1    n61(mod19). 19 \mid n^5 + n^4 + n^3 + n^2 + n + 1 \iff n^6 \equiv 1 \pmod{19}.
Because 19 is a prime number, the congruence a21(mod19)a^2 \equiv 1 \pmod{19} has exactly two solutions, namely a±1(mod19)a \equiv \pm 1 \pmod{19}. This is so because (a1)(a+1)(a-1)(a+1) can only be divisible by the prime number 19 if one of the two factors is so. This shows that n61(mod19)n^6 \equiv 1 \pmod{19} iff n3±1(mod19)n^3 \equiv \pm 1 \pmod{19}.
To find all such nn we create the following table, in which we first calculated n2(mod19)n^2 \pmod{19} to keep the numbers small.

n (mod 19)0-1±2±3±4±5±6±7±8±9
n2n^2 (mod 19)0149-36-2-875
n3n^3 (mod 19)0-1±8±8±7∓8±7±1∓1±7

This shows that n5+n4+n3+n2+n+1n^5 + n^4 + n^3 + n^2 + n + 1 is divisible by 19 if and only if nn is congruent to 7, 8, 11, 12 or 18 (mod 19).

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.