Maths Olympiad Prep

Library / /12 of 520

Number theory Difficulty 6.1 National olympiad Find the answer

Is there an integer nn such that n2+n+1n^2 + n + 1 is divisible by 19551955 ?

Solution

To determine if there exists an integer n n such that n2+n+1 n^2 + n + 1 is divisible by 1955 1955 , we need to check the divisibility of n2+n+1 n^2 + n + 1 by the prime factors of 1955 1955 .

First, factorize 1955 1955 :
1955=5×17×23 1955 = 5 \times 17 \times 23

We need to check if n2+n+1 n^2 + n + 1 can be divisible by each of these prime factors.

1. Check divisibility by 5:
n2+n+10(mod5) n^2 + n + 1 \equiv 0 \pmod{5}
We need to check the possible values of n n modulo 5:
n0(mod5)    n2+n+102+0+11(mod5)n1(mod5)    n2+n+112+1+13(mod5)n2(mod5)    n2+n+122+2+172(mod5)n3(mod5)    n2+n+132+3+1133(mod5)n4(mod5)    n2+n+142+4+1211(mod5) \begin{aligned} n &\equiv 0 \pmod{5} \implies n^2 + n + 1 \equiv 0^2 + 0 + 1 \equiv 1 \pmod{5} \\ n &\equiv 1 \pmod{5} \implies n^2 + n + 1 \equiv 1^2 + 1 + 1 \equiv 3 \pmod{5} \\ n &\equiv 2 \pmod{5} \implies n^2 + n + 1 \equiv 2^2 + 2 + 1 \equiv 7 \equiv 2 \pmod{5} \\ n &\equiv 3 \pmod{5} \implies n^2 + n + 1 \equiv 3^2 + 3 + 1 \equiv 13 \equiv 3 \pmod{5} \\ n &\equiv 4 \pmod{5} \implies n^2 + n + 1 \equiv 4^2 + 4 + 1 \equiv 21 \equiv 1 \pmod{5} \end{aligned}
None of these results are congruent to 0 modulo 5. Therefore, n2+n+1 n^2 + n + 1 is never divisible by 5.

Since n2+n+1 n^2 + n + 1 is not divisible by 5, it cannot be divisible by 1955 1955 because 5 is a factor of 1955.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.