## Never Divides By 5

#### Problem

Given that $x$ is a positive integer prove that $f(x) = x^2 + x + 1$ will never divide by 5.

#### Solution

When $x$ is divided by 5 the possible remainders are 0, 1, 2, 3, and 4. The respective remainders of $x^2$ will be $0, 1, 4, 9 \equiv 4$, and $16 \equiv 1$. This can be seen more clearly in a table.

$\mod 5$
$x$$x^2$$x^2 + x + 1$
00$0 + 0 + 1 = 1$
11$1 + 1 + 1 = 3$
24$2 + 4 + 1 = 7 \equiv 2$
34$3 + 4 + 1 = 8 \equiv 3$
41$4 + 1 + 1 = 6 \equiv 1$

Hence we show that $f(x)$ will never divide by 5.

Show that the result holds even if $x$ is a negative integer.
Investigate which other values of $n$ that will never divide into $f(x)$.

Problem ID: 318 (07 Apr 2007)     Difficulty: 2 Star

Only Show Problem