Sufficient Condition for 5 to divide n^2+1
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
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-2}$ Fermat's Little Theorem: Exercise $6$