Integral powers mod $n$

In calculus, you learn to solve (or at least find approximate solutions to) equations of the form $y=a^x$ . Solving for $x$ in terms of $y$ incolves using the logarithm to base $a$ .

We want to do something analogous here. One difference here is that, because the integers are discrete, there are no approximate solutions!

Definition 1.8.1   Let $a\geq 1,n>1$ be relatively prime integers. We say that $a$ has order $k$ modulo $n$ is $k$ if $k$ is the smallest positive integer satisfying $a^k\equiv 1 ({\rm mod} n)$ . The order is denoted ${\rm ord}_n(a)$ .

For example, the order of $a=2$ modulo $n=7$ is $k=3$ since $2^3\equiv 1 ({\rm mod} 7)$ .

One way to think about the material in this section is it is a study of properties of the order function. The order of an integer is not ``easy'' to find in the sense that if $n$ is a large integer then there is no known ``efficient'' algorithm for determining ${\rm ord}_n(a)$ [BS].