Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Quick algorithm for computing orders mod n?

Let $l$ be an odd prime number. Let $p$ be a prime number such that $p \neq l$. I'd like to compute efficiently the order of $p$ mod $l$ using a calculator. For example, how can I compute efficiently the order of 2 mod 53? Thanks in advance.

My motivation came from this.

share|cite|improve this question

marked as duplicate by Gerry Myerson, LVK, Old John, William, wentaway Sep 2 '12 at 21:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The order in what group exactly ? – Belgi Jul 23 '12 at 23:23
The multiplicative group of integers mod $l$. Namely $(\mathbb{Z}/l\mathbb{Z})^*$. The order of an integer mod $l$ is standard in elementary number theory. – Makoto Kato Jul 23 '12 at 23:43
It is cheap in general whether $p$ is a quadratic residue of $\ell$. In this case $2$ is a NR of $53$. The order divides $52$. The only interesting possibilities are $13$, $26$, $52$. It cannot be $13$, else $2$ would be a QR. So calculate $2^{26}\pmod{53}$, or maybe $2^{27}$. – André Nicolas Jul 24 '12 at 0:12

1 Answer 1

In your case, and using Legrende's symbol, we get $$\left(\frac{2}{53}\right)=-1$$ since $\,53\neq \pm 1\mod 8\,$ , so $\,2\,$ has a chance to be a primitive root modulo $\,53\,$

Now, and doing operations modulo $\,53\,$ , we get: $$2^6=64=11\,\,,\,11^2=15\,\,,\,11^3=6\Longrightarrow 2^{18}=(2^6)^3=11^3=6\Longrightarrow$$ $$\Longrightarrow2^{26}=2^{18}\cdot 2^8=6\cdot 11\cdot 4=-1\Longrightarrow $$ $\,2\,$ is a primitive root in $\,\left(\Bbb Z/53\Bbb Z\right)^*\,$

share|cite|improve this answer

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