19
3. Kongruence
Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice
jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná;
projevuje se zejména ve stručných a přehledných zápisech některých i
velmi komplikovaných úvah.
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).
Lemma. 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.
Důkaz. „(1)⇒(3) Jestliže a = q1m + r, b = q2m + r, pak a − b =
(q1 − q2)m.
„(3)⇒(2) Jestliže m | a−b, pak existuje t ∈ Z tak, že m·t = a−b,
tj. a = b + mt.
„(2)⇒(1) Jestliže a = b + mt, pak z vyjádření b = mq + r plyne
a = m(q + t) + r, tedy a i b mají při dělení číslem m týž zbytek r, tj.
a ≡ b (mod m).
3.1. Základní vlastnosti kongruencí. Přímo z definice plyne,
že kongruence podle modulu m je reflexivní (tj. a ≡ a (mod m) platí
pro každé a ∈ Z), symetrická (tj. pro každé a, b ∈ Z z a ≡ b (mod m)
plyne b ≡ a (mod m)) a tranzitivní (tj. pro každé a, b, c ∈ Z z a ≡ b
(mod m) a b ≡ c (mod m) plyne a ≡ c (mod m)) relace, jde tedy
o ekvivalenci. Dokážeme nyní další vlastnosti:
Věta 12. (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.
Důkaz. Je-li a1 ≡ b1 (mod m) a a2 ≡ b2 (mod m), existují
podle lemmatu t1, t2 ∈ Z tak, že a1 = b1 + mt1, a2 =
b2 + mt2. Pak ovšem a1 + a2 = b1 + b2 + m(t1 + t2) a opět
podle lemmatu a1 + a2 ≡ b1 + b2 (mod m). Sečteme-li kongruenci
a + b ≡ c (mod m) s kongruencí −b ≡ −b (mod m),
která zřejmě platí, dostaneme a ≡ c − b (mod m). Sečteme-li
20
kongruenci a ≡ b (mod m) s kongruencí mk ≡ 0 (mod m),
jejíž platnost je zřejmá, dostaneme a + mk ≡ b (mod m).
(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.
Důkaz. Je-li a1 ≡ b1 (mod m) a a2 ≡ b2 (mod m), existují
podle t1, t2 ∈ Z tak, že a1 = b1 + mt1, a2 = b2 + mt2. Pak
ovšem
a1a2 = (b1 + mt1)(b2 + mt2) = b1b2 + m(t1b2 + b1t2 + mt1t2),
odkud podle dostáváme a1a2 ≡ b1b2 (mod m).
Je-li a ≡ b (mod m), dokážeme indukcí vzhledem k přirozenému
číslu n, že platí an
≡ bn
(mod m). Pro n = 1 není co
dokazovat. Platí-li an
≡ bn
(mod m) pro nějaké pevně zvolené
n, vynásobením této kongruence a kongruence a ≡ b (mod m)
dostáváme an
·a ≡ bn
·b (mod m), tedy an+1
≡ bn+1
(mod m),
což je tvrzení pro n + 1. Důkaz indukcí je hotov.
Jestliže vynásobíme kongruenci a ≡ b (mod m) a kongruenci
c ≡ c (mod m), dostaneme ac ≡ bc (mod m).
(3) Obě strany kongruence můžeme vydělit jejich společným
dělitelem, jestliže je tento dělitel nesoudělný s mo-
dulem.
Důkaz. Předpokládejme, že a ≡ b (mod m), a = a1 · d,
b = b1 · d a (m, d) = 1. Podle lemmatu je rozdíl a − b =
(a1−b1)·d dělitelný číslem m. Protože (m, d) = 1, je podle věty
5 číslo a1 − b1 také dělitelné číslem m, odtud podle lemmatu
plyne a1 ≡ b1 (mod m).
(4) Obě strany kongruence i její modul můžeme současně vynásobit
tímtéž přirozeným číslem.
Důkaz. Je-li a ≡ b (mod m), existuje podle lemmatu celé
číslo t tak, že a = b+mt, odkud pro c ∈ N platí ac = bc+mc·t,
odkud opět podle lemmatu plyne ac ≡ bc (mod mc).
(5) Obě strany kongruence i její modul můžeme vydělit jejich společným
kladným dělitelem.
Důkaz. Předpokládejme, že a ≡ b (mod m), a = a1 · d,
b = b1 ·d, m = m1 ·d, kde d ∈ N. Podle lemmatu existuje t ∈ Z
tak, že a = b+mt, tj. a1 ·d = b1 ·d+m1dt, odkud a1 = b1 +m1t,
což podle lemmatu znamená, že a1 ≡ b1 (mod m1).
21
(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.
Důkaz. Jestliže a ≡ b (mod m1), a ≡ b (mod m2), . . ., a ≡
b (mod mk), podle lemmatu je rozdíl a − b společný násobek
čísel m1, m2, . . . , mk a tedy je dělitelný jejich nejmenším
společným násobkem [m1, m2, . . . , mk], odkud plyne a ≡ b
(mod [m1, . . . , mk]).
(7) Jestliže kongruence platí podle modulu m, platí podle libovolného
modulu d, který je dělitelem čísla m.
Důkaz. Jestliže a ≡ b (mod m), je a − b dělitelné m, a
proto také dělitelem d čísla m, odkud a ≡ b (mod d).
(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.
Důkaz. Předpokládejme, že a ≡ b (mod m), b = b1d,
m = m1d. Pak podle lemmatu existuje t ∈ Z tak, že a =
b + mt = b1d + m1dt = (b1 + m1t)d, a tedy d | a.
Poznámka. Některé vlastnosti kongruencí jsme již používali, aniž
bychom si toho povšimli – například příklad ze strany 7 lze přeformulovat
do tvaru „jestliže a ≡ 1 (mod m), b ≡ 1 (mod m), pak také ab ≡ 1
(mod m) , což je speciální případ tvrzení věty 12 (2). Nejde o náhodu.
Libovolné tvrzení používající kongruence můžeme snadno přepsat pomocí
dělitelnosti. Užitečnost kongruencí tedy netkví v tom, že bychom
pomocí nich mohli řešit úlohy, které bez nich řešit nejsme schopni, ale
v tom, že jde o velmi vhodný způsob zápisu. Osvojíme-li si ho, výrazně
tím zjednodušíme jak vyjadřování, tak i některé úvahy. Je to typický
jev: v matematice hraje vhodná symbolika velmi závažnou úlohu.
Příklad. Nalezněte zbytek po dělení čísla 520
číslem 26.
Řešení. Protože 52
= 25 ≡ −1 (mod 26), platí podle věty 12 (2)
520
≡ (−1)10
= 1 (mod 26),
a tedy zbytek po dělení čísla 520
číslem 26 je jedna.
Příklad. Dokažte, že pro libovolné n ∈ N je 37n+2
+ 16n+1
+ 23n
dělitelné sedmi.
Řešení. Platí 37 ≡ 16 ≡ 23 ≡ 2 (mod 7), a tedy podle 12 (2) a
(1) platí
37n+2
+16n+1
+23n
≡ 2n+2
+2n+1
+2n
= 2n
(4+2+1) = 2n
·7 ≡ 0 (mod 7),
což jsme chtěli dokázat.
22
Příklad. Dokažte, že číslo n = (8355
+ 6)18
− 1 je dělitelné číslem
112.
Řešení. Rozložíme 112 = 7 · 16. Protože (7, 16) = 1, stačí ukázat,
že 7 | n a 16 | n. Platí 835 ≡ 2 (mod 7), a tedy podle 12
n ≡ (25
+6)18
−1 = 3818
−1 ≡ 318
−1 = 276
−1 ≡ (−1)6
−1 = 0 (mod 7),
proto 7 | n. Podobně 835 ≡ 3 (mod 16), a tedy
n ≡ (35
+ 6)18
− 1 = (3 · 81 + 6)18
− 1 ≡ (3 · 1 + 6)18
− 1 =
= 918
− 1 = 819
− 1 ≡ 19
− 1 = 0 (mod 16),
proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat.
Příklad. Dokažte, že pro libovolné prvočíslo p a libovolná a, b ∈ Z
platí
ap
+ bp
≡ (a + b)p
(mod p).
Řešení. Podle binomické věty platí
(a + b)p
= ap
+ p
1
ap−1
b + p
2
ap−2
b2
+ · · · + p
p−1
abp−1
+ bp
.
Podle příkladu za větou 6 pro libovolné k ∈ {1, . . ., p−1} platí p
k
≡ 0
(mod p), odkud plyne tvrzení.
Následující tvrzení je další užitečnou vlastností kongruencí:
Lemma. Dokažte, že pro libovolné přirozené číslo m a libovolná
a, b ∈ Z taková, že a ≡ b (mod mn
), kde n ∈ N, platí, že am
= bm
(mod mn+1
).
Důkaz. Platí
am
− bm
= (a − b)(am−1
+ am−2
b + · · · + abm−2
+ bm−1
) (12)
a protože m | mn
, tak podle 12 (7) platí i a ≡ b (mod m). Jsou tedy
všechny sčítance ve druhé závorce v (12) kongruentní s am−1
modulo
m, a tedy
am−1
+ am−2
b + · · · + abm−2
+ bm−1
≡ m · am−1
≡ 0 (mod m),
proto je am−1
+am−2
+· · ·+abm−2
+bm−1
dělitelné m. Z a ≡ b (mod mn
)
plyne, že mn
dělí a − b, a tedy mn+1
dělí jejich součin, což vzhledem
k (12) vede k závěru, že am
≡ bm
(mod mn+1
).
3.2. Aritmetické funkce. Aritmetickou funkcí zde rozumíme funkci,
jejímž definičním oborem je množina přirozených čísel.
Definice. Rozložme přirozené číslo n na prvočísla: n = pα1
1 · · · pαk
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.
Příklad. µ(4) = µ(22
) = 0, µ(6) = µ(2·3) = (−1)2
, µ(2) = µ(3) =
−1.
23
Dokážeme nyní několik důležitých vlastností Möbiovy funkce, zejména
tzv. Möbiovu inverzní formuli.
Lemma. Pro n ∈ N \ {1} platí
d|n
µ(d) = 0.
Důkaz. Zapíšeme-li n ve tvaru n = pα1
1 · · ·pαk
k , pak všechny dělitele
d čísla n jsou tvaru d = pβ1
1 · · ·pβk
k , kde 0 ≤ βi ≤ αi pro všechna
i ∈ {1, . . ., k}. Proto
d|n
µ(d) =
(β1,...,βk)∈(N∪{0})k
0≤βi≤αi
µ(pβ1
1 · · · pβk
k ) =
=
(β1,...,βk)∈{0,1}k
µ(pβ1
1 · · · pβk
k )
= k
0
+ k
1
· (−1) + k
2
· (−1)2
+ · · · + k
k
· (−1)k
= 1 + (−1)
k
= 0.
S Möbiovou funkcí úzce souvisí pojem Dirichletův součin:
Definice. Buďte f, g aritmetické funkce. Jejich Dirichletův součin
je definován předpisem
(f ◦ g)(n) =
d|n
f(d) · g n
d
=
d1d2=n
f(d1) · g(d2).
Lemma. Dirichletův součin je asociativní.
Důkaz.
((f ◦ g) ◦ h)(n) =
d1d2d3=n
f(d1) · g(d2) · h(d3) = (f ◦ (g ◦ h))(n)
Příklad. Definujme dvě pomocné funkce I a I předpisem I(1) =
1, I(n) = 0 pro všechna n > 1, resp. I(n) = 1 pro všechna n ∈ N. Pak
pro každou aritmetickou funkci f platí:
f ◦ I = I ◦ f = f
a
(I ◦ f)(n) = (f ◦ I)(n) =
d|n
f(d).
24
Dále platí I ◦ µ = µ ◦ I = I, neboť
(I ◦ µ)(n) =
d|n
I(d)µ(n
d
) =
d|n
I(n
d
)µ(d) =
=
d|n
µ(d) = 0 pro všechna n > 1
podle lemmatu za definicí Möbiovy funkce (pro n = 1 je tvrzení zřejmé).
Věta 13. (Möbiova inverzní formule) Nechť je aritmetická funkce
F definovaná pomocí aritmetické funkce f předpisem F(n) = d|n f(d).
Pak lze funkci f vyjádřit ve tvaru
f(n) =
d|n
µ(n
d
) · F(d).
Důkaz. Vztah F(n) = d|n f(d) lze jiným způsobem zapsat jako
F = f ◦ I. Proto F ◦ µ = (f ◦ I) ◦ µ = f ◦ (I ◦ µ) = f ◦ I = f, což je
tvrzení věty.
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).
Příklad. Multiplikativními funkcemi jsou např. funkce f(n) =
σ(n), f(n) = τ(n), či f(n) = µ(n) nebo, jak brzy dokážeme i tzv.
Eulerova funkce f(n) = ϕ(n).
3.3. Eulerova funkce ϕ.
Definice. Nechť n ∈ N. Definujme Eulerovu funkci ϕ předpisem
ϕ(n) = |{a ∈ N | 0 < a ≤ n, (a, n) = 1}|
Příklad. ϕ(1) = 1, ϕ(5) = 4, ϕ(6) = 2, je-li p prvočíslo, je zřejmě
ϕ(p) = p − 1.
Nyní dokážeme několik důležitých tvrzení o funkci ϕ:
Lemma. Nechť n ∈ N. Pak d|n ϕ(d) = n.
Důkaz. Uvažme n zlomků
1
n
,
2
n
,
3
n
, . . . ,
n − 1
n
,
n
n
.
Zkrátíme-li zlomky na základní tvar a seskupíme podle jmenovatelů,
snadno dostaneme právě uvedené tvrzení.
Věta 14. Nechť n ∈ N, jehož rozklad je tvaru n = pα1
1 · · · pαk
k . Pak
ϕ(n) = n · 1 −
1
p1
· · · 1 −
1
pk
.
25
Důkaz. S využitím předchozího lemmatu a Möbiovy inverzní formule
dostáváme
ϕ(n) =
d|n
µ(d)
n
d
= n −
n
p1
− · · · −
n
pk
+ · · · + (−1)k n
p1 · · · pk
=
= n · 1 −
1
p1
· · · 1 −
1
pk
.
(13)
Poznámka. Předchozí výsledek lze obdržet i bez použití Möbiovy
inverzní formule pomocí principu inkluze a exkluze na základě zjištění
poučtu čísel soudělných s n.
Důsledek. Nechť a, b ∈ N, (a, b) = 1. Pak
ϕ(a · b) = ϕ(a) · ϕ(b).
Důkaz. Zřejmý.
Poznámka. Rovněž toto tvrzení lze odvodit nezávisle na základě
poznatku (n, ab) = 1 ⇐⇒ (n, a) = 1 ∧ (n, b) = 1. Spolu se snadno
odvoditelným výsledkem
ϕ(pα
) = pα
− pα−1
= (p − 1) · pα−1
(14)
pak lze odvodit vztah (13) již třetím způsobem.
Příklad. Vypočtěte ϕ(72).
Řešení. 72 = 23
· 32
=⇒ ϕ(72) = 72 · (1 − 1
2
) · (1 − 1
3
) = 24,
alternativně ϕ(72) = ϕ(8) · ϕ(9) = 4 · 6 = 24.
Příklad. Dokažte, že ∀n ∈ N : ϕ(4n + 2) = ϕ(2n + 1).
Řešení. ϕ(4n + 2) = ϕ(2 · (2n + 1)) = ϕ(2) · ϕ(2n + 1) = ϕ(2n +
1).
3.4. Malá Fermatova věta, Eulerova věta. Tvrzení v tomto
odstavci patří mezi nejdůležitější výsledky teorie čísel.
Věta 15 (Fermatova, Malá Fermatova). Nechť a ∈ Z, p prvočíslo,
p ∤ a. Pak
ap−1
≡ 1 (mod p). (15)
Důkaz. Tvrzení vyplyne jako snadný důsledek Eulerovy věty 16.
Důsledek. Nechť a ∈ Z, p prvočíslo. Pak
ap
≡ a (mod p).
Důkaz. Pokud p | a, pak jsou obě strany kongruentní s 0 mod p,
jinak tvrzení snadno plyne vynásobením obou stran kongruence (15)
číslem a.
26
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.
Poznámka. Snadno lze vidět, že jsou-li a, b ∈ Z, a ≡ b (mod m),
a (a, m) = 1, pak i (b, m) = 1.
Lemma. Nechť x1, x2, . . ., xϕ(m) tvoří redukovanou soustavu zbytků
modulo m. Je-li a ∈ Z, (a, m) = 1 pak i čísla a · x1, . . . , a · xϕ(m) tvoří
redukovanou soustavu zbytků modulo m.
Důkaz. Protože (a, m) = 1 a (xi, m) = 1, platí (a · xi, m) = 1.
Kdyby pro nějaká i, j platilo a · xi ≡ a · xj (mod m), po vydělení
obou stran kongruence číslem a nesoudělným s m dostaneme xi ≡ xj
(mod m).
Věta 16 (Eulerova). Nechť a ∈ Z, m ∈ N, (a, m) = 1. Pak
aϕ(m)
≡ 1 (mod m). (16)
Důkaz. Buď x1, x2, . . . , xϕ(m) libovolná redukovaná soustava zbytků
modulo m. Podle předchozího lemmatu je i a · x1, . . . , a · xϕ(m) redukovaná
soustava zbytků modulo m. Platí tedy, že pro každé i existuje
j (oba indexy jsou z množiny {1, 2, . . ., ϕ(m)}) tak, že a · xi ≡ xj
(mod m). Vynásobením čísel obou redukovaných soustav zbytků do-
stáváme
(a · x1) · (a · x2) · · ·(a · xϕ(m)) ≡ x1 · x2 · · ·xϕ(m) (mod m).
Po úpravě
aϕ(m)
· x1 · x2 · · · xϕ(m) ≡ x1 · x2 · · · xϕ(m) (mod m)
a protože (x1 · x2 · · ·xϕ(m), m) = 1, můžeme obě strany kongruence
vydělit číslem x1 · x2 · · ·xϕ(m) a dostaneme aϕ(m)
≡ 1 (mod m).
Poznámka. Eulerova věta je rovněž důsledkem Lagrangeovy věty
uplatněným na grupu (Z×
m, ·).
Příklad. Nalezněte všechna prvočísla p, pro která 5p2
+ 1 ≡ 0
(mod p2
).
Řešení. Snadno se přesvědčíme, že p = 5 úloze nevyhovuje. Pro
p = 5 platí (p, 5) = 1, a tedy podle Fermatovy věty 5p−1
≡ 1 (mod p).
Umocněním na p + 1 dostaneme 5p2−1
≡ 1 (mod p), odkud 5p2
≡ 5
(mod p). Z podmínky 5p2
+ 1 ≡ 0 (mod p)2
plyne 5p2
≡ −1 (mod p),
celkem tedy 5 ≡ −1 (mod p), a proto p | 6. Je tedy buď p = 2, nebo
p = 3. Pro p = 2 však 54
+ 1 ≡ 14
+ 1 = 2 ≡ 0 (mod 4). Pro p = 3
dostáváme 59
+ 1 = 56
· 53
+ 1 ≡ 53
+ 1 = 126 ≡ 0 (mod 9), kde
jsme užili důsledek Eulerovy věty 56
≡ 1 (mod 9). Jediným prvočíslem,
vyhovujícím úloze je tedy p = 3.
27
Příklad. Pro liché číslo m > 1 nalezněte zbytek po dělení čísla
2ϕ(m)−1
číslem m.
Řešení. Z Eulerovy věty plyne 2ϕ(m)
≡ 1 ≡ 1+m = 2r (mod m)),
kde r = 1+m
2
je přirozené číslo, 0 < r < m. Podle 12 (3) platí 2ϕ(m)−1
≡
r (mod m), a tedy hledaný zbytek po dělení je r = 1+m
2
.
Tvrzení 3.1. Je-li p prvočíslo, p ≡ 3 (mod 4), pak pro libovolná
celá čísla a, b z kongruence a2
+ b2
≡ 0 (mod p) plyne a ≡ b ≡ 0
(mod p).
Důkaz. Předpokládejme, že pro a, b ∈ Z platí a2
+b2
≡ 0 (mod p).
Jestliže p | a, platí a ≡ 0 (mod p), proto b2
≡ 0 (mod p), tedy p | b2
,
odkud vzhledem k tomu, že p je prvočíslo, dostáváme p | b, a proto
a ≡ b ≡ 0 (mod p), což jsme chtěli dokázat.
Zbývá prošetřit případ, kdy a není dělitelné prvočíslem p. Odtud
dostáváme, že p nedělí ani b (kdyby p | b, dostali bychom p | a2
).
Vynásobíme-li obě strany kongruence a2
≡ −b2
(mod p) číslem bp−3
,
dostaneme podle Fermatovy věty
a2
bp−3
≡ −bp−1
≡ −1 (mod p).
Protože p ≡ 3 (mod 4), je p −3 sudé číslo, a proto p−3
2
∈ N0. Označme
c = ab
p−3
2 .
Pak c není dělitelné p a platí c2
= a2
bp−3
≡ −1 (mod p). Umocníme-li
poslední kongruenci na p−1
2
∈ N, dostaneme
cp−1
≡ (−1)
p−1
2 (mod p).
Protože p ≡ 3 (mod 4), existuje celé číslo t tak, že p = 3+4t. Pak ovšem
p−1
2
= 1 + 2t, což je číslo liché a proto (−1)(p−1)/2
= −1. Podle Fermatovy
věty naopak platí cp−1
≡ 1 (mod p), odkud 1 ≡ −1 (mod p) a
p | 2, spor.
S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem
řád čísla modulo m - jde přitom pouze o jinak nazvaný řád prvku
v grupě invertibilních zbytkových tříd modulo m:
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).
Příklad. Pro libovolné m ∈ N má číslo 1 modulo m řád 1. Číslo
−1 má řád
• 1 pro m = 1 nebo m = 2
• 2 pro m > 2
Příklad. Určete řád čísla 2 modulo 7.
28
Řešení.
21
= 2 ≡ 1 (mod 7)
22
= 4 ≡ 1 (mod 7)
23
= 8 ≡ 1 (mod 7)
Řád čísla 2 modulo 7 je tedy roven 3.
Uveďme nyní několik zásadních tvrzení udávajících možné hodnoty
řádu čísla modulo m:
Lemma. 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.
Důkaz. Umocněním kongruence a ≡ b (mod m) na n-tou dostaneme
an
≡ bn
(mod m), tedy an
≡ 1 (mod m) ⇐⇒ bn
≡ 1 (mod m).
Lemma. 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ůkaz. Protože žádné z čísel a, a2
, a3
, . . . , ars−1
není kongruentní
s 1 modulo m, není ani žádné z čísel ar
, a2r
, a3r
, . . . , a(s−1)r
kongruentní
s 1. Platí ale (ar
)s
≡ 1 (mod m), proto je řád ar
modulo m roven s.
Poznámka. Opak obecně neplatí – z toho, že řád čísla ar
modulo
m je roven s ještě neplyne, že řád čísla a modulo m je r · s.
Př: m = 13
a = 3, a2
= 9 (mod 13), a3
= 27 ≡ 1 (mod 13) ⇒ 3 má řád 3 mod 13.
b = −4, b2
= 16 ≡ 1 (mod 13), b3
= −64 ≡ 1 (mod 13) ⇒ −4 má řád
3 modulo 13.
Přitom (−4)2
= 16 ≡ 3 (mod 13) má stejný řád 3 jako číslo 3, ale číslo
−4 nemá řád 2 · 3.
Přesný popis závislosti řádu na exponentu dávají následující 2 věty:
Věta 17. 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).
Důkaz. Bez újmy na obecnosti lze předpokládat, že t ≥ s. Vydělímeli
číslo t − s číslem r se zbytkem, dostaneme t − s = q · r + z, kde
q, z ∈ N0, 0 ≤ z < r.
„⇐ Protože t ≡ s (mod r), máme z = 0, a tedy at−s
= aqr
=
(ar
)q
≡ 1q
(mod m). Vynásobením obou stran kongruence číslem as
dostaneme tvrzení.
„⇒ Z at
≡ as
(mod m) plyne as
· aqr+z
≡ as
(mod m). Protože je
ar
≡ 1 (mod m), je rovněž aqr+z
≡ az
(mod m). Celkem po vydělení
29
obou stran kongruence číslem as
(které je nesoudělné s modulem), dostáváme
az
≡ 1 (mod m). Protože z < r, plyne z definice řádu, že
z = 0, a tedy r | t − s.
Zřejmým důsledkem předchozí věty a Eulerovy věty je následující
tvrzení (jehož druhá část je přeformulováním Lagrangeovy věty z Algebry
pro naši situaci):
Důsledek. 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)
Důkaz.
(1) stačí v předchozí větě volit t = n, s = r.
(2) zřejmé z (1) díky Eulerově větě volbou n = ϕ(m).
Následující věta je zobecněním předchozího Lemmatu.
Věta 18. 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)
.
Důkaz. Protože r·n
(r,n)
= [r, n], což je zřejmě násobek r, máme
(an
)
r
(r,n) = a[r,n]
≡ 1 (mod m)
(plyne z předchozího Důsledku neboť r | [r, n]). Na druhou stranu, je-li
k ∈ N libovolné takové, že (an
)k
= an·k
≡ 1 (mod m), dostáváme (r
je řád a), že r | n · k a dále z Věty 5 plyne, že r
(n,r)
| n
(n,r)
· k a díky
nesoudělnosti čísel r
(n,r)
a n
(n,r)
dostáváme r
(n,r)
| k. Proto je r
(n,r)
řádem
čísla an
modulo m.