Modulo Arithmetic/Examples/Solutions to x^2 = x Modulo 6

From ProofWiki
Jump to navigation Jump to search

Example of Modulo Arithmetic

The equation:

$x^2 = x \pmod 6$

has solutions:

\(\displaystyle x\) \(=\) \(\displaystyle 0\)
\(\displaystyle x\) \(=\) \(\displaystyle 1\)
\(\displaystyle x\) \(=\) \(\displaystyle 3\)
\(\displaystyle x\) \(=\) \(\displaystyle 4\)


Proof

The Cayley table for multiplication modulo $6$ can be presented as:

$\begin{array} {r|rrrrrr} \times_6 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$

The squares $x^2$ of each $x$ can be found on the main diagonal, where each element of $\Z_6$ can be inspected.


Checking each of these, we have:

\(\displaystyle 0^2\) \(=\) \(\displaystyle 0\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 0\) \(\displaystyle \pmod 6\)
\(\displaystyle 1^2\) \(=\) \(\displaystyle 1\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 1\) \(\displaystyle \pmod 6\)
\(\displaystyle 2^2\) \(=\) \(\displaystyle 4\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 4\) \(\displaystyle \pmod 6\)
\(\displaystyle 3^2\) \(=\) \(\displaystyle 9\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 3\) \(\displaystyle \pmod 6\)
\(\displaystyle 4^2\) \(=\) \(\displaystyle 16\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 4\) \(\displaystyle \pmod 6\)
\(\displaystyle 5^2\) \(=\) \(\displaystyle 25\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 1\) \(\displaystyle \pmod 6\)

$\blacksquare$


Sources