Number Theory: The order of a modulo p

Definition of Order

The order of an integer a modulo a prime p is the smallest positive integer k such that a^k is congruent to 1 modulo p.
This concept in number theory is crucial for understanding topics like cryptography and mathematical problems involving complexity and algorithm efficiency.

According to Fermat’s Little Theorem, if p is a prime number, and a is an integer not divisible by p, then a^(p-1) is congruent to 1 modulo p.
This theorem can be used to derive the order of a modulo p: if the smallest value of k for which a^k is congruent to 1 mod p is n, and if p-1 is divisible by n, then n is the order of a modulo p.

The order of an integer modulo a prime number has several important properties for mathematical computations and proofs.
Fundamental to understanding these properties is Euler’s Totient Theorem, defining φ(n) as the number of positive integers less than n and relatively prime to n.
The order of any element a in the group of units mod p divides φ(p), where φ is Euler’s totient function.
If k is the order of a modulo p, then a^n is congruent to 1 modulo p if and only if k divides n.

The concept of order modulo p has key implications in Cryptography, particularly in RSA encryption, a public-key encryption technology.
It’s also critical for Complexity Theory as it appears in the complexity analysis of various algorithms.
For example, in computing large powers of a number, repeated-squaring can be combined with the concept of order modulo p to produce an algorithm that calculates these large powers in logarithmic time.