Fermat's Little Theorem/Examples/12 Divides n^2-1 if gcd(n, 6)=1

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Fermat's Little Theorem

$12$ divides $n^2 - 1$ if $\gcd \set {n, 6} = 1 \implies 12 \divides n^2 - 1$


Proof

\(\ds \gcd \set {n, 6}\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds \gcd \set {n, 3}\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds 3\) \(\divides\) \(\ds n^2 - 1\)


Then:

\(\ds \gcd \set {n, 6}\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds \gcd \set {n, 1}\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds 2\) \(\divides\) \(\ds n - 1\)
\(\ds \leadsto \ \ \) \(\ds 2\) \(\divides\) \(\ds n + 1\)
\(\ds \leadsto \ \ \) \(\ds 4\) \(\divides\) \(\ds \paren {n + 1} \paren {n - 1}\)
\(\ds \) \(=\) \(\ds n^2 - 1\)


So we have:

\(\ds 3\) \(\divides\) \(\ds n^2 - 1\)
\(\, \ds \land \, \) \(\ds 4\) \(\divides\) \(\ds n^2 - 1\)
\(\ds \leadsto \ \ \) \(\ds 12\) \(\divides\) \(\ds n^2 - 1\)

$\blacksquare$


Sources