Theorems and related


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


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.