Kongruence, rozklad na zbytkové třídy.
Věta: Nechť a, b jsou celá čísla taková, že b * 0. Potom existují celá čísla q, r splňující vztah:
a-bq + r,Q<r<\b\, přičemž toto vyjádření je jednoznačné.
Poznámka: Je nutno si uvědomit, že zbytek r při dělení je vždy nezáporný, a to i při dělení záporným číslem. Např. a = -26, b - 8, q ==• -4, r = 6, protože -26 = 8 . (-4) + 6.
Poznámka; Celá čísla a, b jsou nesoudělná, je-li jejich největší společný dělitel roven jedné. V opačném případě se nazývají soudělná. Největší společný dělitel čísel a, b budeme označovat NSD(a, b), nejmenší kladný společný násobek NSN(a, b).
Eulerova funkce   cp(n) vyjadřuje počet přirozených čísel menších nebo rovných číslu n,
nesoudělných s n. Nechť n =  p*1 . ... p*k, pak   platí    <p(n) = n . |T(1--). Je-li
i-i Pt
n prvočíslo,- pak (pfhj = n — 1.
Kongruence: a, b e Z, m e N, m > 2. Platí a = b <=> m \ (a - b). Čteme: Číslo á je kongruentní s číslem b podle modulu m. Dvě čísla kongruentní podle nějakého modulu m dávají při dělení tímto modulem m týž zbytek. Relace kongruence je ekvivalence na množině všech celých Čísel (je reflexivní, symetrická a tranzitivní).
Vlastnosti kongruencí:
1) p prvočíslo     a = b (mod p") => o = é (mod p)
Platí-li kongruence podle modulu, který je mocninou prvočísla, platí i podle modulu rovného tomuto prvočíslu.
2) b (mod m^), i - 1,2, ...,k => a = b (mod NSN(?wm J)
Platí-li kongruence podle několika modulů, platí i podle modulu rovného nejmenšímu společnému násobku těchto modulů.
k k k k
3) a;s ^ (mod m), i = l,...,k=> ]Ta. = ^i. (modra),   Yíai - ITA   (mod m).
í=]        i=i i=i i=i
Kongruence podle téhož modulu lze sčítat i násobit. Nechť v dalším platí a = b (mod m):
4) a + x s b + x (mod m), a.y = 6. v (mad m)
K oběma stranám kongruence lze přičíst stejné celé číslo a obě strany kongruence lze vynásobit týmž celým číslem. Obecně ale nelze obě strany kongruence dělit týmž celým číslem, např. 24 = 40 (mod 8), ale po vydělení čtyřmi 6 # 10 (mod 8).
5) m \z ■=> a + z = b (raod m)
Celé číslo, které je násobkem modulu, lze přičíst pouze k jedné straně kongruence.
6) a" s b" (mod m)
Obě strany kongruence lze umocnit na libovolný přirozený exponent.
7) d \a a d |b a NSDOJtav) = 1 => ~=- (mod m)
' d d
Obě strany kongruence lze vydělit celým číslem nesoudělným s modulem.
8) ac s bc (mod mc)
Obě strany kongruence i modul lze vynásobit týmž celým kladným číslem.
„x   i      i,      i       o-    b .    , m.
9) e b a <? 16 a e Ic => — = — (mod —)
e    e e
Obě strany kongruence i modul lze vydělit týmž celým kladným číslem různým od nuly.
10) a s b (mod m) a d \m => a = b (mod d)
Platí-li kongruence podle modulu m, platí i podle modulu rovného libovolnému kladnému děliteli čísla m, většímu než jedna.
Eulerova věta: m e N, m> l,a e Z, D(a,m) = 1, pak d^ s 1 (mod m).
Je-li specielně p prvočíslo, které není dělitelem čísla a, pak platí ď~l = 1 (mod p) (tzv. malá
Fermato va věta).
Definice. —
Necht? raje pevné přirozené číslo. Označme:
Cj = {.r £ Z | i dává po dělení číslem m zbytek i} , pro i = 0,1, ... ,m—1
Pak množina Ci se nazývá zbytková třída podle modulu rn. Symbolem Zm ae označí množina všech zbytkových tříd podle modulu rn, tzn. Zm — {Gv, Ci,..., Cm_i} .
Poznámka.
Někdy bude technicky výhodnější přeformulovat definici zbytkové třídy d do ekvivalentního tvaru:
Ci — {isS | i = i (mod m) } ,     pro i = 0,1, ... , m—l.
Ekvivalentnost vyjádření okamžitě plyne z věty      , uvědomíme-li si zřejmý
fakt, že číslo i, kde 0 < i < m—l, dává po dělení číslem m zbytek i.
Z věty o dělení se zbytkem celých čísel plyne, že zbytkových tříd podle modulu m musí být opravdu právě m (neboť zbytek po dělení každého celého čísla číslem m musí podle této věty nabývat právě jedné z hodnot 0,1,..., m— 1). Dále, každá zbytková třída podle modulu rn obsahuje zřejmě nekonečně mnoho celých čísel, lišících se o nějaký celočíselný násobek modulu rn. Pokusíme-li se schematicky zapsat jednotlivé zbytkové třídy podle modulu rn, dostaneme f
Co	= {■••	,    -2rn ,	—rn ,	0 ,	-rn ,	2m ,	... }
	= {■•■	, -2m + 1 ,	—m -f 1 ,	1 ,	rn + 1 ,	2rn + 1 , ,	... }
c2	-	, -2m'+ 2 ,	-rn + 2 ,	2 ,	m + 2 ,	2m + 2 ,	... }
		,   -m - 1 r	-1 ,	m — 1 ,	2rn - 1	, 'irn — 1 ,	
z veta
Nedlí m je pevné přirozené číslo. Pak množina Zm všech zbytkových tříd podle modulu m tvoří rozklad na množině Z všech celých čísel:
Důkaz.
Uvažme nmožinu zbytkových tříd Zm = {Co, Ci, -.., Cm_i} .
dokážeme, že Zm je rozklad na Z.
1. každá »e zbytkových tříd Cť je zřejmě neprázdnou podmnožinou v Z.
2. nechť Q, GS 6 35 B d H C,- 7^ 0. Potom existuje číslo .t 6 Cj n C,-, což znamená, že x dává po delení číslem m zbytek i a současně také zbytek j. Ale z věty o delení celých čísel se zbytkem víme, že zbytek po dělení je určen jednoznačně, tzn. i = j, odkud dostáváme, že C; = Cy .
3. zřejmě platí, že sjednocení C0 U C\ U • •; U Cm-i = Z.
		lad	:o-iJ	P,
1				
V/
q/j
^eJL^   Jc^grua^lo^   cU2q_    yj&xilľ   mocL  ^OO .
^ -  Á- (ivi^X Áan \ ^
^ 2)1 = 64" = M (ctoxL too)
S3.
Go
/^^Mü*Cß,   A^- >J-ctWvw-    ÄxcUiu^    Mc^JlyVVj?. :
,'iH   +^6   +03   = 1   + 2-   +1 (AKotLN-) ,
^ m-M        ^ a      r i#\ ^
Maz 4
8
I O
1 = G (anutcL Ho
1
4
6 = ^g<^s = Ha%
AoíL
(S Cr^1
ô"
-{o
4 Cwnkto)*6
64 s