Theorems and related
Contents
Basic theorems
Fundamental theorem of arithmetic
Every positive integer n ≥ 2 can be written uniquely (up to the order) as product of primes.
Lagrange's theorem
Let G be a finite group and let H be a subgroup of G. Let card(X) be the cardinality of X. Then card(H)|card(G).
Corollary: let G be a finite group with neutral element e. Then acard(G) = e for every a ∈ G.
Euler's totient function
Euler's totient function Φ : Z+ → Z+ is defined as the cardinality of Z*n: Φ(n) = card(Z*n).
Number n is prime
Recall
- Zp = { 0, 1, ..., p-1 } hence card(Zp) = p
- Z*p = { 1, ..., p-1 } hence card(Z*p) = p-1
Fermat's little theorem: for every prime p, integer a and p ∤ a then ap-1 ≡ 1 mod p. So any integer a raised to the power of the group's cardinality equals 1 mod p.
Number n is composite
So n can be factored into some primes.
In this case Fermat's little theorem can be generalised to Euler's theorem, which states the following.
For all integers n ≥ 2 and all a with gcd(a,n) = 1 holds that aΦ(n) ≡ 1 mod n. As Euler's totient function was defined as Z*n: Φ(n) = card(Z*n) this obviously matches.
e-th root of a group element theorem
Let G be some finite, multiplicative group and let e ∈ Z such that gcd(e, card(G)) = 1. The e-th root of y ∈ G, namely x ∈ G satisfying xe = y, is given by x = yd, where d is the multiplicative inverse of e modulo card(G).
Stated otherwise, y = xe means x is the e-th root of y. And obviously y = xe = yde = y1.