# Thread: Roots over Z/pZ

1. ## Roots over Z/pZ

Hello there,
my book is asking to do the following problem :

Given $\displaystyle x^a \equiv x \pmod{n}$, design an algorithm to find $\displaystyle x$ in polynomial time know $\displaystyle a$ and $\displaystyle n$, and given that the modulus $\displaystyle n$ is composite.
Isn't there a typo in the last word, because I know about ways to take roots over $\displaystyle \mathbb{Z}/p\mathbb{Z}$ when $\displaystyle 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 $\displaystyle p$ is a composite ?

And also, if I know that $\displaystyle x^a \equiv x \pmod{n}$, then the following must be true : $\displaystyle x^{a - 1} \equiv 1 \pmod{n}$, by dividing both sides by $\displaystyle x$. However, if I take an example, say $\displaystyle n = 21$, $\displaystyle x = 7$ and $\displaystyle a = 3$, we have $\displaystyle 7^3 \equiv 7 \pmod{21}$ alright, but $\displaystyle 7^2 \equiv 7 \pmod{21}$ and is not equal to one, however $\displaystyle 2 = 3 - 1$. Anyone know what I messed up here ?

2. We can multiply residu-classes, not "allways" divide them:
We can only divide classes when we're working in the group $\displaystyle (\mathbb{Z}/n\mathbb{Z})^*$.

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

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

We can draw the following conclusion:

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

Hence we have the following cases:

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