I've got this problem:

Determine an integer with (exactly) multiplicative order $22$ mod $1331$

Is there a general way to procede in any case with this kind of exercises? Thank you!

  • 2
    $\begingroup$ You can take advantage of the following facts. The starting point is, of course, that $1331=11^3$. If $g$ is a primitive root modulo $p$, i.e. of order $p-1$ modulo $p$, then $g$ the order of $g$ modulo $p^2$ is either $p-1$ or $p(p-1)$ (the latter being way more common). If $g$ is not of order $p(p-1)$, then it is easy to show that $g+p$ is of order $p(p-1)$ modulo $p^2$. Repeating the step. If $g$ is of order $p(p-1)$ modulo $p^2$, then its order modulo $p^3$ is either $p(p-1)$ or $p^2(p-1)$. In the latter case $g^p$ is of order $p(p-1)$. Finding an element of order $2p$ is then easy. $\endgroup$ – Jyrki Lahtonen Aug 26 '14 at 15:06

Your Answer

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

Browse other questions tagged or ask your own question.