0
$\begingroup$

I am looking for a formula, algorithm, or even literature on the topic.

Take $21$ for example

$21 = 7 \cdot 3$

What is the order of $3^{x} \bmod 21$?

$3^0 = 1$

$3^1 = 3$

$3^2 = 9$

$3^3 = 6$

$3^4 = 18$

$3^5 = 12 $

$3^6 = 15$

$3^7 = 3$

Therefore the order of $3^x \mod 21$ is $6 (3,9,6,18,12,15)$

Is there a formula or algorithm for solving order$(p,n)$?

$\endgroup$
10
  • 3
    $\begingroup$ Something is way off. Multiplicative order of an integer $a$ (or a residue class) modulo $n$ is defined only when $\gcd(a,n)=1$. $\endgroup$
    – Jyrki Lahtonen
    Commented Jun 30 at 10:00
  • $\begingroup$ To find the order of $p$ in the modul $n$, they need to be coprime. Here there are not coprime. But as $\mathbb{Z}/21\mathbb{Z}\cong \mathbb{Z}/7\mathbb{Z}\times \mathbb{Z}/3\mathbb{Z}$ we get that it repeats after $\varphi(7)=6$. $\endgroup$
    – calculatormathematical
    Commented Jun 30 at 10:01
  • $\begingroup$ Thats the only answer I can find is that they need to be coprime but here we have a group and I want to find its order its clearly well defined with the set I gave 3,9,6... so the fact that multiplicative order is only defined for sets that include 1 is a bit puzzling for me but never the less I am looking to see if there is literature on this topic $\endgroup$
    – zakrea2070
    Commented Jun 30 at 10:17
  • $\begingroup$ @calculatormathematical yes in this instance its $phi(7) =6$ but its not always the case. So what is the general formula? $\endgroup$
    – zakrea2070
    Commented Jun 30 at 10:20
  • $\begingroup$ Please use MathJax. Here is a tutorial. "but here we have a group - no, we don't. We have $3\cdot 7=0$ here modulo $23$, this is a contradiction, because then in a group it would follow that $7=3^{-1}\cdot 3\cdot 7=0$, which is false modulo $23$. Because $7\neq 0$. $\endgroup$
    – Dietrich Burde
    Commented Jun 30 at 10:21

2 Answers 2

Reset to default
2
$\begingroup$

Hint: $\!\bmod n\, $ suppose $p^{\Bbb N}$ has preperiod $j$ and period $k,\,$ i.e. $j,k$ are minimal such that $\,p^{j+k}\equiv p^j.\,$ Then $\,n\mid p^j(p^k-1)\,$ so $\,p^j\mid\mid n\,$ and $\,k\,$ is the order of $p$ modulo $n/p^j,\,$ e.g. in your example the preperiod has length $\, j= 1\,$ and the period has length $\,k = 6 = {\rm ord}_7(3)$.

Generally there is no formula for computing the order. See here for algorithms.

$\endgroup$
-1
$\begingroup$

What you call the "order of $p$ modulo $pn$" will be a divisor of $\varphi(n)$. There is no "formula" that will tell you which divisor it is.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Does it have a proper name other than to say the order of the group as I am aware its not the multiplicative order due to missing 1 (which doesn't make sense to me for the definition to be limited to that). Are you sure there is no formula more specific than a divisor of $phi(n/p)$? Do you have any literature on this topic papers books? $\endgroup$
    – zakrea2070
    Commented Jun 30 at 11:41
  • $\begingroup$ I know of no name for this. It's not the "order" of anything. That the definition "makes no sense to you" may be because you are new to number theory - mathematicians have agreed on the actual definition because it's useful. If you had a formula for the question you ask you would have a formula for the actual order of elements of the group $\mathbb{Z}_p^*$ - a known hard problem. There will be theorems in any book on elementary number theory that address these questions. $\endgroup$
    – Ethan Bolker
    Commented Jun 30 at 13:54
  • $\begingroup$ Interesting, I am mainly asking to see if there is specific information in this regard that is already know as I couldn't find much on this yet (specifically order of numbers that are not coprime). I think the multiplicative order definition should be extended to include the orders of non coprime and there is a very good structure for them. I think its best to write this up formally for it to make any sense. Unfortunately, I don't think the formula for these solves the order in group zp :( $\endgroup$
    – zakrea2070
    Commented Jun 30 at 15:18

Not the answer you're looking for? Browse other questions tagged .