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

$x$ | $x^2$ | $x^2 + x + 1$ |
---|---|---|

0 | 0 | $0 + 0 + 1 = 1$ |

1 | 1 | $1 + 1 + 1 = 3$ |

2 | 4 | $2 + 4 + 1 = 7 \equiv 2$ |

3 | 4 | $3 + 4 + 1 = 8 \equiv 3$ |

4 | 1 | $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