euler's totient

Work in Progress

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

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