# Given a prime exponent e and a prime number n, find b, where b^e = 1 mod n

Can anyone help me with the following problem. Given a prime exponent $e$ and a prime number $n$, find $b$, where $b^e \equiv 1 \bmod n \land b > 1$. For example, $b^5 \equiv 1 \bmod 11$ how to find $b$ ? Can anyone describe me the steps please.

• $b = g^{(n-1)/e}$. – fkraiem Jun 21 '16 at 10:11
• Well, or $b=1$, I suppose... – fkraiem Jun 21 '16 at 10:12
• fkraiem, can you explain how did you arrived at that formula ? thank you – user36264 Jun 21 '16 at 10:53
• Or $b = n+1$ :-) – poncho Jun 21 '16 at 13:52

If $n$ is prime, $\mathbb{Z}_n^{*}$ has a primitive root $g$ and order $n-1$. So if $e$ divides $n-1$ you have $(g^{\frac{n-1}{e}})^e=1$. For $n=11$ you have e.g. the primitive root $g=2$ and therefore with $$b\equiv 2^{10/5}\equiv 2^2 \equiv 4 \pmod {11}$$ you compute $$b^5 \equiv 4^5 \equiv 1024 \equiv 1 \pmod {11}.$$
With the remaining primitive roots $g=6,7,8$ you get other solutions $b\equiv 6^2 \equiv 3 \pmod {11},$ $b\equiv 7^2 \equiv 5 \pmod {11},$ and $b\equiv 8^2 \equiv 9 \pmod {11}.$
But be aware that your problem may have no solution: in your example there is no $b\not \equiv 1$ with $b^3\equiv 1 \pmod {11}!$
• In fact it is not necessary for $g$ to be a primitive root; any element will do. – fkraiem Jun 21 '16 at 13:19