# 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.

## Fermat’s Little Theorem and Order

• 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.

## Properties of the Order of an Element

• 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.

## Applications and Implications of the Order Modulo p

• 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.