A question arising from Fermat's little theorem. For a prime number $p$ and a natural numbers $a$ not divisible by $p$, let $i(p,a)$ be the smallest of the natural number $i$ such that
$$a^i\equiv 1\mod p.$$ We know from Fermat's little theorem that $i(p,a)|(p-1)$
How to determine the function $i(p,a)$?
 A: In general there isnt a clean form for this.All we know is that $i(p,a)\mid p-1$.Although you can find $i(p,a)$ in $O(\log(p))$ time.Check this Is there a better way of finding the order of a number modulo $n$? once
A: While it can be hard to determine the exact values, we know quite a bit:

*

*$i(a,p)$ and $i(-a,p)$ are related because $(-1)^{2n}=1$ and $(-1)^{2n+1}=-1$ so odd exponents lead the powers to be additive inverses ( meaning $-1$ for one will map to $1$ for the other if it occurs), and even exponents lead to the same remainder class ( meaning $-1$ is in the same place for both if it occurs). This plus $(-1)^2=1$ is enough to show that they either by have same order, or a factor of two difference.

*$i(a,p)$ and $i(a^{-1},p)$ are the same, because each factor of $a$ cancels a factor of $a^{-1}$ so they are multiplicative inverses for any exponent . It just so happens that $1^{-1}=1$ .

*$i(a^x,p)$ is related to to $i(a,p)$ because $(a^x)(a^x)=a^{x+x}$ so $x$'s "additive order" modulo $i(a,p)$ is $i(a^x,p)$

*we also get $i(a,p)\mid p-1$ by Fermat's little theorem and $1^n=1$ .

Here's an example of getting the orders of all non trivial remainder classes (we know $1^1\equiv (-1)^2\equiv 1$):

*

*$2^7\equiv 1\pmod {127}$ since $7$ is prime ( therefore coprime to other exponents $7\nmid x$) , this implies the orders of all powers of $2$ is $7$ , as it can't be halved, for additive inverses of powers of $2$ it must double to $14$.( So we've dealt with $2,4,8,16,32,63,64,95,111,119,123,125$ all with just 3 facts.

*$3^{126}\equiv 1\pmod {127}$ ( aka $3$ is a primitive root, so every remainder class is congruent a power) $9$ and it's multiplicative inverse have order $63$ (while $9$'s additive inverse has order $126$ ), $27$ and it's multiplicative inverse have order $42$( while a bit of calculation will show you it's additive inverse has order $21$), ... Anyways you can use the powers of $3$ to basically calculate their orders.

