Twierdzenie o algorytmie Euklidesa - NWD(a, b) = { a dla b = 0 { NWD(b, a mod b) dla b >= 1

Liczby względnie pierwszych - liczby całkowite, które nie mają innych poza jedynką wspólnych dzielników w rozkładzie na czynniki pierwsze lub, równoważnie, ich największym wspólnym dzielnikiem jest jedność

Funkcja Eulera - φ(n) = {b∊0,…,n-1} : NWD(b, n) = 1}

Kongruencja - Niech X będzie dowolnym zbiorem. Relację R ∊ X x X nazywamy relacją równoważności wtedy i tylko wtedy gdy, jest ona:

Zwrotna: ∀a,m a≡a(mod m)
Symetryczna: ∀a,b,m a≡b(mod m) <=> b≡a(mod m)
Przechodnia: ∀a,b,c,m a≡b(mod m) ^ b≡c(mod m) => a≡c(mod m)

Moduł Kongruencji -

Element odwrotny - Niech @ oznacza działanie dwuargumentowe w zbiorze S. Element x nazywa się elementem odwrotnym do y jeżeli spełnione są dwa warunki: x @ y = e oraz y @ x = e; gdzie e oznacza element neutralny działania @.

Chińskie twierdzenie o resztach - Jeśli liczby całkowite dodatnie n1, n2, n3, ... , nk są parami względnie pierwsze, zaś a1, a2, a3, ... , ak są dowolnymi liczbami całkowitymi, to istnieje taka liczba całkowita a, że:

a ≡ a1(mod n1),
a ≡ a2(mod n2),
...........................
a ≡ ak(mod nk),

Wariacja z powtórzeniami - Ciąg k elementów należących do n-elementowego zbioru S nazywamy k-elementową wariacją z powtórzeniami ze zbioru n-elementowego. Ilość takich wariacji wynosi n^k.

Wariacja bez powtórzeń - Ciąg k różnych elementów należących do n-elementowego zbioru S nazywamy k-elemnentową wariacją bez powtórzeń ze zbioru n-elem. Ilość takich wariacji wynosi n!/(n-k)!

Kombinacja - Zbiór k różnych elementów należących do n-elem zbioru S, w którym porządek elementów jest nieistotny nazywamy k-elem kombinacją zbioru. Ilość takich kombinacji wynosi (n po k) = n!/k!(n-k)! (symbol Newtona).

Permutacja - Ciąg n różnych elementów należących do n-elem zbioru S nazywamy permutacją takiego zbioru. Ilość takich permutacji wynosi n!.

Prawa zliczania (prawo sumy i prawo iloczynu) -

---