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.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ $b = g^{(n-1)/e}$. $\endgroup$– fkraiemCommented Jun 21, 2016 at 10:11
-
3$\begingroup$ Well, or $b=1$, I suppose... $\endgroup$– fkraiemCommented Jun 21, 2016 at 10:12
-
1$\begingroup$ fkraiem, can you explain how did you arrived at that formula ? thank you $\endgroup$– user36264Commented Jun 21, 2016 at 10:53
-
2$\begingroup$ Or $b = n+1$ :-) $\endgroup$– ponchoCommented Jun 21, 2016 at 13:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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}!$
answered Jun 21, 2016 at 11:06
-
$\begingroup$ In fact it is not necessary for $g$ to be a primitive root; any element will do. $\endgroup$– fkraiemCommented Jun 21, 2016 at 13:19