Sufficient Condition for 5 to divide n^2+1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let:

\(\ds 5\) \(\nmid\) \(\ds n - 1\)
\(\ds 5\) \(\nmid\) \(\ds n\)
\(\ds 5\) \(\nmid\) \(\ds n + 1\)

where $\nmid$ denotes non-divisibility.


Then:

$5 \divides n^2 + 1$

where $\divides$ denotes divisibility.


Proof

We have that:

\(\ds 5\) \(\nmid\) \(\ds n - 1\)
\(\ds \leadsto \ \ \) \(\ds n - 1\) \(\not \equiv\) \(\ds 0\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds n\) \(\not \equiv\) \(\ds 1\) \(\ds \pmod 5\)


\(\ds 5\) \(\nmid\) \(\ds n\)
\(\ds \leadsto \ \ \) \(\ds n\) \(\not \equiv\) \(\ds 0\) \(\ds \pmod 5\)


\(\ds 5\) \(\nmid\) \(\ds n + 1\)
\(\ds \leadsto \ \ \) \(\ds n + 1\) \(\not \equiv\) \(\ds 0\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds n\) \(\not \equiv\) \(\ds 4\) \(\ds \pmod 5\)


So either:

$n \equiv 2 \pmod 5$

or:

$n \equiv 3 \pmod 5$

and so:

\(\ds n\) \(\equiv\) \(\ds 2\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds n^2\) \(\equiv\) \(\ds 4\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds n^2 + 1\) \(\equiv\) \(\ds 0\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds 5\) \(\divides\) \(\ds n^2 + 1\)

or:

\(\ds n\) \(\equiv\) \(\ds 3\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds n^2\) \(\equiv\) \(\ds 3^2\) \(\ds \pmod 5\)
\(\ds \) \(\equiv\) \(\ds 4\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds n^2 + 1\) \(\equiv\) \(\ds 0\) \(\ds \pmod 5\)
\(\ds \leadsto \ \ \) \(\ds 5\) \(\divides\) \(\ds n^2 + 1\)

$\blacksquare$


Sources