# Roots over Z/pZ

Printable View

• Jan 20th 2010, 04:47 AM
Bacterius
Roots over Z/pZ
Hello there,
my book is asking to do the following problem :

Quote:

Given $x^a \equiv x \pmod{n}$, design an algorithm to find $x$ in polynomial time know $a$ and $n$, and given that the modulus $n$ is composite.
Isn't there a typo in the last word, because I know about ways to take roots over $\mathbb{Z}/p\mathbb{Z}$ when $p$ is a prime, which is not the case here, and as I looked over the internet, it seems a "hard" problem to take roots if $p$ is a composite ?

And also, if I know that $x^a \equiv x \pmod{n}$, then the following must be true : $x^{a - 1} \equiv 1 \pmod{n}$, by dividing both sides by $x$. However, if I take an example, say $n = 21$, $x = 7$ and $a = 3$, we have $7^3 \equiv 7 \pmod{21}$ alright, but $7^2 \equiv 7 \pmod{21}$ and is not equal to one, however $2 = 3 - 1$. Anyone know what I messed up here ?
• Jan 20th 2010, 07:25 AM
Dinkydoe
We can multiply residu-classes, not "allways" divide them:
We can only divide classes when we're working in the group $(\mathbb{Z}/n\mathbb{Z})^*$.

In your example you used n = 21, and 7|21. Observe that $3\cdot 7 \equiv 9\cdot 7 \equiv 0$ mod 21. But it's not true that $7\equiv 0$ mod 21.

You're getting into trouble when you're using elements that divide n.
The conclusion is: $x^a \equiv x$ mod $n \Leftrightarrow x^{a-1}\equiv 1$ mod n iff gcd(x,n) = 1.

We can draw the following conclusion:

$x^a\equiv x$ mod $n \Leftrightarrow x(x^{a-1}-1)\equiv 0$ mod n.

Hence we have the following cases:

Let $x\in \mathbb{Z}/n\mathbb{Z}$
1. x is a root if: $x\equiv 0$ mod n.
2. if $\phi(n)|a-1$ then all $x\in (\mathbb{Z}/n\mathbb{Z})^*$ are roots, ie. all $x\in \mathbb{Z}/n\mathbb{Z}$ with gcd(x,n) = 1. And x with gcd(x,n) $\neq 1$ can be roots.
3. $a-1|\phi(n)$. Then only elements from the group $(\mathbb{Z}/n\mathbb{Z})^*$ that have order $a-1$ are roots. And x with gcd(x,n) $\neq 1$ can be roots.
4. If neither $a-1|\phi(n)$ or $\phi(n)|a-1$ then only x, with gcd(x,n) $\neq 1$ can be roots.

I hope you know the Euler totient function a little. For more about the euler totient function: Euler's totient function - Wikipedia, the free encyclopedia

Finding roots for all $x\in \mathbb{Z}/n\mathbb{Z}$ with gcd(x,n) $\neq 1$ is indeed a hard problem.