# Linear expression for the elements belonging to the same modulo order

$\newcommand{\ord}{\operatorname{ord}}$

Let $p$ is any prime and $(a,p)=1$

(i)If $\ord_pa=2,$

We know there can be $\phi(2)=1$ element that belongs to order$=2$.

(ii)If $\ord_pa=3,a^3\equiv 1\pmod p\implies a^2+a+1\equiv 0$ as $a≢-1\pmod p$

So, $-(a+1)\equiv a^{-1}$

We know, $\ord_ma=d, \ord_m(a^k)=\frac{d}{(d,k)}$ (Proof @Page#95)

So, $\ord_p(a^{-1})=\ord_pa$

We know there can be $\phi(3)=2$ elements that belongs to order$=3$.

If $a$ is one, $-(a+1)$ is the other.

(iii)If $\ord_pa=4,a^4\equiv 1\pmod p\implies a^2+1\equiv 0$ as $a^2≢1\pmod p$

So, $-a=a^{-1}$

We know there can be $\phi(4)=2$ elements that belongs to order$=4$.

If $a$ is one, $-a$ is the other.

(iii) If $\ord_pa=6$, we have proved, if $a$ is one, $1-a$ is the other.

So, in all cases, we find a linear expression of $a$ for the other element.

My question is how to generalize this for any order with $\pmod p$, then with $\pmod {p^n}$ and $\pmod m$ (where $m,n$ are positive integers).

-
Do you really mean linear expression? That comes about because of because of the smallness of the orders considered. And anyway $a^{-1}$ (for order $4$) does not really qualify as linear. –  André Nicolas Oct 26 '12 at 20:58
@AndréNicolas, by linear,I meant $Aa+B$ where $A,B$ are integer constants. For order $4,$ it's $-a$, not $a^{-1}$. –  lab bhattacharjee Oct 27 '12 at 4:37
For general order $d$, there will be many elements of order $d$. So do you mean a family of integer constants? Your observations about small orders can be extended to $p^n$ or $2p^n$ for odd $p$. –  André Nicolas Oct 27 '12 at 4:45
@AndréNicolas, ya a set of pair of integer constants. So, there is no known standard formula for this, right? But, how to extend the observation for the other orders, whose $\phi>2$ for $p^n$ and $2p^n$? –  lab bhattacharjee Oct 27 '12 at 5:14
I have not seen anything of the kind for general orders, all the standard stuff is in terms of powers of $a$. –  André Nicolas Oct 27 '12 at 5:22