I'm trying to solve $x^7 = x$ in $x ∈ Z/14Z$. I tried it in Wolfram Alpha and I know it's true for every $x$ but I don't know why.
Any help appreciated.
I'm trying to solve $x^7 = x$ in $x ∈ Z/14Z$. I tried it in Wolfram Alpha and I know it's true for every $x$ but I don't know why.
Any help appreciated.
Given any group $(G, \ast)$ of finite order $|G|$, we have $g^{|G|} = e_G$ for all $g \in G$ (see Lagrange's Theorem for more details), where $e_G$ is the identity element in the group $(G, \ast)$.
In the case of $G = (\mathbb{Z}/m\mathbb{Z}, \times)$ where $\times$ denotes multiplication $\pmod{m}$, this group $G$ is of order $\phi(m)$, where $\phi(m)$ is the number of positive integers less than or equal to $m$ which are relatively prime to $m$. The function $\phi(m)$ is called the Euler totient function.
Putting these together, we see that $(\mathbb{Z}/7\mathbb{Z}, \times)$ is a group of order $\phi(7) = 6$, and hence $x^6 \equiv1 \pmod{7}$ for all $x \in (\mathbb{Z}/7 \mathbb{Z}, \times) $ as $1 \in \mathbb{Z}/7\mathbb{Z}$ is the multiplicative identity of the group. Multiplying both sides by $x$, we arrive at $x^7 \equiv x $ which is true for all $x \in (\mathbb{Z}/7 \mathbb{Z}, \times)$ and it is true for $x = 0$ as well.
You can make the same justification for $\mathbb{Z}/2 \mathbb{Z}$, and then put your results together using the Chinese Remainder Theorem.
You want to show that $x^7 \equiv x \ \ (14)$. It is enough to show it modulo 2 and modulo 7. The first is trivial to check and the second follows from Fermat's little theorem.