Fermat's Little Theorem/Examples/12 Divides n^2-1 if gcd(n, 6)=1
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
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-2}$ Fermat's Little Theorem: Exercise $2$