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

Printable View

- Feb 7th 2006, 07:09 AMDenMac21Explanation
Can someone explain me why $\displaystyle n^2+n+1$ isn't dividable with 125?

- Feb 7th 2006, 08:52 AMCaptainBlackQuote:

Originally Posted by**DenMac21**

$\displaystyle r\in \{0,1,2,3,4,5,6,7,8,9\}$. You will find $\displaystyle n^2+n+1$

is never divisible by $\displaystyle 5$ and so cannot be divisible by $\displaystyle 125$.

RonL - Feb 7th 2006, 01:55 PMThePerfectHackerQuote:

Originally Posted by**DenMac21**

$\displaystyle n^2+n+1\equiv 0\mod 5$

Noticing that 5 is a prime, look at its discrimanant ($\displaystyle b^2-4ac)$.

The above congruence has a solution if and only if its discrimant is a quadradic residue.

Since $\displaystyle b^2-4ac=-3\equiv 2$.

Apply Euler's Criterion to determine if something is a quadradic residue we get that,

$\displaystyle 2^{\frac{5-1}{2}}\not \equiv 1\mod 5$

Thus, $\displaystyle n^2+n+1$ is never divisible by 5, thus how can it be divisible by $\displaystyle 125=5^3$?

Thus, we have shown it is impossible.

Q.E.D.

To remind you Euler's Criterion states, $\displaystyle a$ is a quadradic residue of $\displaystyle p$ if and only if,

$\displaystyle a^{\frac{p-1}{2}}\equiv 1\mod p$