Explanation

Can someone explain me why $n^2+n+1$ isn't dividable with 125?

Quote:

Originally Posted by DenMac21

Can someone explain me why $n^2+n+1$ isn't dividable with 125?

Consider $n^2+n+1$ modulo $10$ , for $n=10k+r$ with
$r\in \{0,1,2,3,4,5,6,7,8,9\}$ . You will find $n^2+n+1$
is never divisible by $5$ and so cannot be divisible by $125$ .

RonL

Quote:

Originally Posted by DenMac21

Can someone explain me why $n^2+n+1$ isn't dividable with 125?

If,
$n^2+n+1\equiv 0\mod 5$
Noticing that 5 is a prime, look at its discrimanant ( $b^2-4ac)$ .

The above congruence has a solution if and only if its discrimant is a quadradic residue.
Since $b^2-4ac=-3\equiv 2$ .
Apply Euler's Criterion to determine if something is a quadradic residue we get that,
$2^{\frac{5-1}{2}}\not \equiv 1\mod 5$
Thus, $n^2+n+1$ is never divisible by 5, thus how can it be divisible by $125=5^3$ ?
Thus, we have shown it is impossible.
Q.E.D.

To remind you Euler's Criterion states, $a$ is a quadradic residue of $p$ if and only if,
$a^{\frac{p-1}{2}}\equiv 1\mod p$