Documentation

Mathlib.RingTheory.ZMod.UnitsCyclic

Cyclicity of the units of ZMod n #

ZMod.isCyclic_units_iff : (ZMod n)ˣ is cyclic iff one of the following mutually exclusive cases happens:

The individual cases are proved by inferInstance and are also directly provided by :

The case of prime numbers is also an instance:

The proofs mostly follow [Ireland and Rosen, A classical introduction to modern number theory, chapter 4] [IR90].

theorem ZMod.exists_one_add_mul_pow_prime_eq {R : Type u_1} [CommSemiring R] {u v : R} {p : } (hp : Nat.Prime p) (hvu : v u) (hpuv : p * u * v u ^ p) (x : R) :
∃ (y : R), (1 + u * x) ^ p = 1 + p * u * (x + v * y)
theorem ZMod.exists_one_add_mul_pow_prime_pow_eq {R : Type u_1} [CommSemiring R] {p : } {u v : R} (hp : Nat.Prime p) (hvu : v u) (hpuv : p * u * v u ^ p) (x : R) (m : ) :
∃ (y : R), (1 + u * x) ^ p ^ m = 1 + p ^ m * u * (x + v * y)
theorem ZMod.orderOf_one_add_mul_prime_pow {p : } (hp : Nat.Prime p) (m : ) (hm0 : m 0) (hpm : m + 2 p * m) (a : ) (ha : ¬p a) (n : ) :
orderOf (1 + p ^ m * a) = p ^ n
theorem ZMod.orderOf_one_add_mul_prime {p : } (hp : Nat.Prime p) (hp2 : p 2) (a : ) (ha : ¬p a) (n : ) :
orderOf (1 + p * a) = p ^ n
theorem ZMod.orderOf_one_add_prime {p : } (hp : Nat.Prime p) (hp2 : p 2) (n : ) :
orderOf (1 + p) = p ^ n
theorem ZMod.isCyclic_units_of_prime_pow (p : ) (hp : Nat.Prime p) (hp2 : p 2) (n : ) :
IsCyclic (ZMod (p ^ n))ˣ

If p is an odd prime, then (ZMod (p ^ n))ˣ is cyclic for all n

theorem ZMod.orderOf_one_add_four_mul (a : ) (ha : Odd a) (n : ) :
orderOf (1 + 4 * a) = 2 ^ n
theorem ZMod.orderOf_five (n : ) :
orderOf 5 = 2 ^ n
theorem ZMod.not_isCyclic_units_of_mul_coprime (m n : ) (hm : Odd m) (hm1 : m 1) (hn : Odd n) (hn1 : n 1) (hmn : m.Coprime n) :
theorem ZMod.isCyclic_units_iff_of_odd {n : } (hn : Odd n) :
IsCyclic (ZMod n)ˣ ∃ (p : ) (m : ), Nat.Prime p Odd p n = p ^ m
theorem ZMod.isCyclic_units_iff (n : ) :
IsCyclic (ZMod n)ˣ n = 0 n = 1 n = 2 n = 4 ∃ (p : ) (m : ), Nat.Prime p Odd p 1 m (n = p ^ m n = 2 * p ^ m)

(ZMod n)ˣ is cyclic iff n is of the form 0, 1, 2, 4, p ^ m, or 2 * p ^ m, where p is an odd prime and 1 ≤ m.