0
$\begingroup$

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.

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

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}!$

$\endgroup$
  • $\begingroup$ In fact it is not necessary for $g$ to be a primitive root; any element will do. $\endgroup$ – fkraiem Jun 21 '16 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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