For what $k$ and $n$ we have: $ord_{k}(n) = k-1$?

Question

For what $k$ and $n$ we have: $ord_{k}(n) = k-1$?

$gcd(k, n) = 1$

$ord$ is Multiplicative order.

Are there any dependencies?

Answer 1

Since we have $ord_k(n)\le \phi(k)$ and $\phi(k)\le k-1$, the condition $ord_k(n)=k-1$ implies that $\phi(k)=k-1$. Hence $k$ is a prime. For a prime $p$ we have $n^{p-1}\equiv 1 \bmod p$ by little Fermat, so the order $ord_p(n)$ is a divisor of $p-1$. If $n$ is a primitive root modulo $p$ then we have $ord_p(n)=p-1$. The dependencies here are difficult.

Answer 2

$Ord_k(n) = k-1 \iff k-1 \mid \varphi(k)$ and $k-1 \leq \varphi(k)$. If $k$ is composite this will not hold.

Then $n^{k-1} \equiv 1 \pmod k$ this means that $k$ has to be prime to satisfy both equalities.