Maths Olympiad Prep

Library / /13 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 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) | 0 | 1 | 4 | 9 | -3 | 6 | -2 | -8 | 7 | 5 |
| 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 and solution reproduced as published; topic and difficulty added by this site.