# What is the order of $p_{1}^{x} \bmod{n}$ where $p_1$ is a prime factor of $n$ [closed]

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)$$?

• Something is way off. Multiplicative order of an integer $a$ (or a residue class) modulo $n$ is defined only when $\gcd(a,n)=1$. Commented Jun 30 at 10:00
• 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$. Commented Jun 30 at 10:01
• 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 Commented Jun 30 at 10:17
• @calculatormathematical yes in this instance its $phi(7) =6$ but its not always the case. So what is the general formula? Commented Jun 30 at 10:20
• 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$. Commented Jun 30 at 10:21

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)$$.
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.
• 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? Commented Jun 30 at 11:41
• 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. Commented Jun 30 at 13:54