Nejmenší společný násobek m dvou celých čísel a, b budeme označovat  .

Říkáme, že dvě přirozená čísla jsou nesoudělná, je-li jejich největším společným dělitelem 1.
Ke kvalitativnímu posunu ve vývoji teorie čísel došlo zavedením pojmu kongruence při práci s pojmem dělitelnosti. Relace nazývaná kongruence je označována symbolem
       
kde n je přirozené číslo.
Dvě celá čísla a, b jsou kongruentní modulo n, mají-li stejný zbytek při dělení číslem n ( je-li jejich rozdíl dělitelný číslem n ):
                  např.

V opačném případě říkáme, že čísla a, b jsou nekongruentní modulo n. Číslo n se nazývá modul kongruence.
Na základě relace kongruence se množina celých čísel rozpadá na třídy prvků se stejným zbytkem při dělení číslem n - tzv. zbytkové třídy modulo n. Třídy označujeme vždy pomocí jednoho prvku - representanta. Třídu, ve které leží číslo a, označujeme ( stručně ).
Např. je-li n=10 máme deset zbytkových tříd:


Pravidla pro práci s kongruencemi připomínají v mnohém pravidla pro práci s celými čísly ( proto
i analogie znaků = a ).

          1)   pro každé     a Z
          2) je-li        , pak    
          3) je-li        a        , pak    
          4) je-li        a současně        , pak platí i    
          5) je-li        a současně        , pak platí i    

Pro dělení kongruencí musí platit podmínka ( postačující ):
          6) je-li        a čísla c,n jsou nesoudělná, pak platí    

Tato jednoduchá pravidla umožňují počítat s kongruencemi efektivně v mnoha situacích. Např. počítání
s mocninami:
           .

Použitím pravidla 5) dostaneme pro a=c, b=d
           .

práce s vyššími mocninami může být ještě efektivnější. Představme si, že máme vypočítat, čemu se rovná
           .

Klasickým způsobem počítání bychom došli k výsledku
           .

což převedením do pětkové soustavy je
           .

K tomuto výsledku je možné se dopracovat i podstatně jednodušším způsobem. Vyjádříme exponent 15 ve dvojkové soustavě, dostaneme
.
tj.              15 = 8 + 4 + 2 + 1
a proto      

Postupným umocňováním dostaneme
.
.
.
.

Takovýmto způsobem dostaneme   , což souhlasí s předcházejícím výsledkem.