Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I'm not sure where this is heading. –  fred Nov 29 '12 at 15:12
    
I know. But still don't see how this applies. –  fred Nov 29 '12 at 15:21
    
Why does it work for 2 and 7 too ? –  fred Nov 29 '12 at 15:26
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.