How do I show a number $o$ for some number $a$ is indeed the smallest number for which $a^o \equiv 1$ (mod $n$) for some number $n$?

Question

If I find a number $o$ that satisfies the above equality, how can I prove this $o$ is indeed the smallest number that satisfies it. I am trying to show the order of $a$ is $o$, but I cannot do this unless I prove:

1) $a^o \equiv 1$ (mod $n$)

2) $o$ is the smallest exponent for which this holds

The first one is relatively easy to prove, the second one is harder. In general, how would one show $o$ is the smallest number for which this holds?

Answer 1

If you have the prime factorization of $o$, it suffices to prove that $a^{o/p}\not\equiv 1\pmod n$ for all primes $p$ dividing $o$.