Even without knowledge that we are working in the multiplicative group of integers modulo n, we can show that "a" actually has an order by noting that the powers of "a" can only take a finite number of different values modulo "n", so according to the pigeonhole principle there must be two powers, say "s" and "t" and without loss of generality "s" > "t", such that "a""s" ≡ "a""t" (mod "n"). Since "a" and "n" are coprime, this implies that "a" has an inverse element "a"−1 and we can multiply both sides of the congruence with "a"−"t", yielding "a""s"−"t" ≡ 1 (mod "n").