# 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 a^{card(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
- Z
_{p} = { 0, 1, ..., p-1 } hence card(Z_{p}) = 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 a^{p-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 x^{e} = y, is given by x = y^{d}, where d is the multiplicative inverse of e modulo card(G).
Stated otherwise, y = x^{e} means x is the e-th root of y. And obviously y = x^{e} = y^{de} = y^{1}.