Kongruence a aritmetické funkce
Pojem kongruence poprvé zavedl Gauss ve své knize Disquisitiones Arithmeticae, vydané
roku 1801. Jedná se o velmi jednoduchý pojem, který je však v teorii čísel nedocenitelný.
Aritmetické funkce jsou pak převážně aplikací věty ?? o jednoznačném rozkladu na součin
prvočísel. Společně pak mohou vyjádřit i velmi složité myšlenky.
Definice. Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek r, kde
0  r < m, nazývají se a, b kongruentní modulo m (též kongruentní podle modulu m), což
zapisujeme takto:
a  b (mod m).
V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme
a  b (mod m).
Pro vytvoření představy, co to vlastně kongruence je, slouží následující lemma:
Lemma 1. Pro libovolná a, b  Z, m  N jsou následující podmínky ekvivalentní:
1. a  b (mod m),
2. a = b + mt pro vhodné t  Z,
3. m | a - b.
Shrnutí vlastností kongruencí uvádí následující věta:
Věta. (Základní vlastnosti kongruencí)
1. Kongruence podle téhož modulu můžeme sčítat. Libovolný sčítanec můžeme přenést
s opačným znaménkem z jedné strany kongruence na druhou. Na libovolnou stranu
kongruence můžeme přičíst jakýkoliv násobek modulu.
2. Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné
umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným
celým číslem.
3. Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento
dělitel nesoudělný s modulem.
1
4. Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným
číslem.
5. Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělite-
lem.
6. Jestliže kongruence a  b platí podle různých modulů m1, . . . , mk, platí i podle modulu,
kterým je nejmenší společný násobek [m1, . . ., mk] těchto čísel.
7. Jestliže kongruence platí podle modulu m, platí podle libovolného modulu d, který je
dělitelem čísla m.
8. Jestliže je jedna strana kongruence a modul dělitelný nějakým celým číslem, musí být
tímto číslem dělitelná i druhá strana kongruence.
Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených
čísel. V předchozí kapitole jsme se setkali s aritmetickými funkcemi (n) a (n),
nyní uvedeme další, které jsou v teorii čísel důležité.
Definice. Rozložme přirozené číslo n na prvočísla: n = p1
1    pk
k . Hodnotu Möbiovy
funkce (n) definujeme rovnu 0, pokud pro některé i platí i > 1 a rovnu (-1)k
v opačném
případě. Dále definujeme (1) = 1.
Definice. Nechť n  N. Definujme Eulerovu funkci  předpisem
(n) = |{a  N|0 < a  n, (a, n) = 1}|
Pro jednodušší výpočet Eulerovy funkce se používá následující věta.
Věta. Nechť n  N, jehož rozklad je tvaru n = p1
1    pk
k . Pak
(n) = n  1 -
1
p1
   1 -
1
pk
.
Pokud n je mocninou jednoho prvočísla, snadno lze ověřit, že platí
(p
) = p
- p-1
= (p - 1)  p-1
.
Dalším důležitým pojmem je multiplikativní funkce.
Definice. Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci,
která splňuje, že pro všechny dvojice nesoudělných čísel a, b  N platí
f(a  b) = f(a)  f(b).
Eulerova funkce  je funkcí multiplikativní. Pro výpočet kongruencí je velmi důležitá,
je tedy nutné říci proč.
2
Věta. Nechť a, b  N, (a, b) = 1. Pak
(a  b) = (a)  (b).
Věta (Fermatova, Malá Fermatova). Nechť a  Z, p prvočíslo, p  a. Pak
(1) ap-1
 1 (mod p).
Definice. Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních
modulo m (nejčastěji 0, 1, . . ., m - 1).
Redukovaná soustava zbytků modulo m je libovolná (m)-tice čísel nesoudělných s m a po
dvou nekongruentních modulo m.
Věta (Eulerova). Nechť a  Z, m  N, (a, m) = 1. Pak
(2) a(m)
 1 (mod m).
Pro výpočet kongruencí je důležitý takzvaný řád čísla modulo m. Jak uvidíme, má také
úzkou souvislost s Eulerovou funkcí.
Definice. Nechť a  Z, m  N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší
přirozené číslo n splňující
an
 1 (mod m).
Protože pro vyšší čísla by výpočet řádu podle uvedené definice byl zdlouhavý, používají
se k výpočtům následující tvrzení.
Lemma 2. Nechť m  N, a, b  Z, (a, m) = (b, m) = 1. Jestliže a  b (mod m), pak obě
čísla a, b mají stejný řád modulo m.
Lemma 3. Nechť m  N, a  Z, (a, m) = 1. Je-li řád čísla a modulo m roven r  s, (kde
r, s  N), pak řád čísla ar
modulo m je roven s.
Řád čísla slouží i k úpravám kongruencí, nebo k výpočtům, které vedou na jejich použití:
Věta. Nechť m  N, a  Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná
t, s  N  {0} platí
at
 as
(mod m)  t  s (mod r).
Z následující věty je patrná souvislost s Eulerovou funkcí, zmiňovaná dříve.
Věta. Nechť m  N, a  Z, (a, m) = 1. Označme r řád čísla a modulo m.
1. Pro libovolné n  N  {0} platí
an
 1 (mod m)  r | n.
2. r | (m)
Následující věta je zobecněním předchozí věty a lemmatu ??.
Věta. Nechť m, n  N, a  Z, (a, m) = 1. Je-li řád čísla a modulo m roven r  N, je řád
čísla an
modulo m roven r
(n,r)
.
3