euler's totient
Summary
Common values
Element order lemma
Equivalences for generators and exponents
Content
Euler’s totient
- aka euler’s phi function
- generalized for a number as a multiple of primes
Euler’s theorem
- generalization of fermat’s little theorem
the GCD definition comes from the theorem 2.1.1
Order of an element
- (Definition 2.3.1)
- smallest number of exponentiations to return to the identity element
Order and size of the group
- (Lemma 2.3.2)
- powers repeat every order-many steps, and that cycle length divides the group size
- generalized for any group, but applicable to
and
for
, see that this is sufficient to prove euler’s theorem
the order of an element
Generators
- (Definition 2.3.3)
- aka primitive roots for
- every element in
can be expressed as an exponentiation of the generator
Some residues modulo a prime are generators
- (Theorem 2.3.4)
more specifically, but not provided,
has a generator iff where is an odd prime
Condition for generators
Application
Euler’s totient example
Order of -1
Number of generators of
2 is a generator of
Generators