Prinsip: Jika PBB(a, n) = 1, terdapat orde k (di mana a^k ≡ 1 mod n) yang merupakan pembagi dari φ(n). Dalam notasi sumber, k disebut sebagai "φ(n)". Maka a^b ≡ a^{b mod k} mod n.

Prinsip: Karena a^k ≡ 1 mod n, dapat ditulis a^k = 1 + m·n untuk suatu konstanta m. Ekspansi binomial (1 + m·n)^q menghasilkan suku-suku yang semuanya habis dibagi n kecuali suku pertama (yaitu 1), sehingga a^b ≡ a^r mod n.