Kapitola 1 ZAKLADMPOJMY
§ 1 ■ OKRUHY, TELESA
V tomto paragrafu uvedeme základní algebraické'pojmy a jejich vlastnosti v takovém rozsahu, jaký búde potrebný v dalším textu. V prípadř, ze půjde o vlastnost známou z úvodního kurzu algebry, budeme se odkazovat na skripta L. Skuly [9.J,
Okruhem budeme všude v dalším vždy rozumět komutativní okruh s jedničkou, což je tedy množina s dvishia binárními operacemi (sčítaním, násobením), obvykle označovaná'
R = (#,+,.) nebo jen strucne'/J, při cemz : 1- (/?,+) je komutativní (abelovska) grupa
2.  (R,.)  je komutativní pologrupa s jedničkou lft
3. násobeni je distributivní vzhledem k sčítání, t.j. a. (ii + c) = c.Ď + a.c ,
pro lib. a,b,c E/i,
Nejjednoduššími príklady okruhu jsou :
a) množiny Z,Q, R, K s operacemi obyčejného sčítania násobeni cisel
b)  množina G = [a + bi  I   a,b e Z ) s operacemi obyčejného sčítaní a násobení cisel. Tento okruh nazývame okruhem Gaussových celých cisel.   ■
q) okruhy Z    = (Z   ,+ ,.) zbytkových trid modulo m
d) jednoprvkový okruh R = [0R ), který se nazývá triviální okruh. V tomto prípade obe operace splývají a je 0R = \R (jinak je vždycky 0R #' lft!!). Tento okruh budeme většinou z našich úvah vylučovat, t. zn. budeme uvazovat pouze netriviální okruhy.
1'říklad 1.1 : Na množine Z X Z. definujeme operace + a .  takto :
(x,.y) + U V.) = (Ar+.v',j'+y')
,            pro lib. .v,i,' y j>' £ Z
{x,y) .   (x ,y) « (.v. x .y. y )
II
\
■zime
kde symboly + , . na pravé strane značí obyčejné sčítání a násobení cis?!. Dostáváme takto okruh   ZXZ » (Z X Z , -^ .), jehoz jedničkou je zřejmé prvek (1,1).
Príklad 1.2 : Nechť R je okruh a nechť n je pevné přirozené tislo. Kartézský
souím RXÍi  X.....XR ( h - krát) označme R". Dále, symbolem R<R"'
označme mnoňnu visech zobrazení z R" doií.t.j.                       ,...    .• '.t;.
R<«"l =   (<plip : R" -* R )■
Na mnoňné R<K   I definujeme operace + a . takto : přó tp.i//   e RIR   ' polózYi
(V+ <f0 <.>-,...... '„) = > (r,.....r.„) +* f (r,, ."'/ľ;' >„ ý" '°l - *^ ■■! ?
pro lib. (r,, ...ir )€/?"
(*>• *)(/,,.....rJ-Wn.....rJ • ŕfrj-----• r»>                   "
kde symboly •+, .   na pravé strane značí sčítaní, resp. násobení v okruhu /? . Je
ihned vidét, že    (y> + \jj), (y> .\j/)  6 K(n  ! a dále, ze jsou splnený axiomy okruhu.
Tedy  (i?(R  ',  +,.) je okruh, jehoz jedničkou je zrejme zobrazení t definovane:
i v:'..'; o - i»-
Ve specielním prípade pro  n  =   1   dostávame takto okruh R* =(flR,+,. ), jehoz prvky jsou tedy zobrazení z  K" do R. Tento okruh budeme nazývat oA:ru/i funkcí (na I? ).
Definice : Nechť R  je okruh,  prvek  r S R  se nazýva  dělitel  nuly v  R,  jestliže  r 4*  0  a existuje  s e R, s * 0  fafc, ze  r.s  =  0.  Netriviálni okruh, který neobsahuje dělitele nuly, se nazýva  obor   integrity.
Příkladem oboru integrity jsou výše zmíněné okruhy  Z, Q, K, K, G,   resp. okruh zbytkových tříd  Z    v prípade,  ze  m  je prvočíslo (viz [9], str. 58)." Naopak, triviálni okruh, okruh ZXZ  a okruh funkcí RR   nejsou obory integrity.' Následující veta pak udává' jinou charakterizaci oboru integrity.
VSta 1.1 : Neeltf R  je netriviální okruh.   Pak  R  je oborem integrity práve když v  R   platí zákon o krácení (t.j.   a, b, c  e fl,  a.-ŕ.O,   a.b ,=  a,c «*  b - c)
ID ů k a z   :   1. nechť R   je obor integrity; je-li  a.b - a.c ,   a ■-£ 0,  pak u. (í) -   c) = 0,   t. zn. podle predpokladu musí byt   b - c = 0, neboli   b = c .
II. nechť v  R   platí zákon o krácení; nechť a, b  S R   ,  al= 0,  a.b = 0. Pak ale Ize psat :   a.b   = 0 = a.0, t. zn.   podle zákona o krácení je   b ■ 0   a tedy /i  je obor integrity.]
Definice: Necht" R je okruh. Prvek e S R; k ntmuí existuje prvek inverzní (vzhledem k operaci násobení), se. nazýva jednotka okruhu R . Množinu všech jednotek okruhu  R   budeme označovat symbolem  J (R) ■
Zrejme jednička   1      je vždy jednotkou okruhu  R .   t. zn.  J(R) je neprázdna' množina, pri cemz obecné ma okruh víte jednotek. Např. okruh  Z  ma prívŕ2 jednotky (a sice cisla   _ I), resp. okruh   G celých Gaussoyých čísel má"4 jednotky (čísla, — I, * í), resp. v okruzích  Q, R, K je ka£dý nenulový prvek jednotkou, atd.
Definice:   Okruh  R  ,  jehoz množina nenulových prvků R- {O R) je grupou vzhledem k operaci násobení, se nazýva   teleso.
Poznámka : vzhledem k tomu, ze operace násobení je .všude v tomto textu komutativní, nem nutne používat terminu komutativní teleso nebo pole, jak se nekdy z důvodu rozlišení dela. Z definice dále vyplýva', ze teleso musi být vifdy alespoň dvouprvkově (neboť R - [0R ) je grupa, t. zn. nepra'zdna množina) a ze kařdý nenulový prvek je jednotkou. Příkladem téles jsou např. Q, R, K, pri ienizto zdaleka nejsou všechny číselne množiny, ktere jsou tělesem vzhledem k operacím obyčejného sčítania,násobení, jak ukážeme dale. Na druhé strane, okruh Z , okruh funkcí RR a okruh  Z X  Z  zrejme nejsou telesa.
Definice : Nechť R =  (R, +, . ) je okruh. Je-li podmnožina  S C Ji   vzhledem k operacím  +, .  okruhem (resp. tělesem),  pak S se nazývá p o do k r u h (resp.    p o d t e l e s o  )   okruhu  R   a  R   se pak nazývá nado k ruh okruhu  (resp.   telesa)  S.   Je-li navíc R   tělesem, pak říkáme,, ze S-je p o d o k r u h e m  (resp.   p o d t e I e s e m )  tele s a R ,  pri cemz R   v tomto prípade nazývame  nadtelesem   okruhu  (resp.   t e 1 e s a ) S.
Je-li S podokruhem okruhu  R  a platili   's ■ 1„ > pak  S nazývame u n i I á r n im  p o d o k r u h e m  o k r u h u  R .
Napríklad,   okruh  Z je unitárním podokruhem okruhu   G   ,   resp. okruh  Z je podokruhem telesa   R,   resp. teleso  Q  je podtelesem telesa  K.   Je-li  R   teleso
-   8
a uvázíme-li v okruhu funkcí  R<*   podmnožinu F všech konstantních zobrazení (t.j. zobrazení tvaru   f(x) - c , pro každé   x£K,   kde   c€R   je p<jvný prvek), pák  F  je zřejmé podtélesem okruhu funkcí  RR . Nakonec si jesté ukažme, že podokruh obecné nemusí být unitárním podokruhem daného okruhu. Například v okruhu   ZXZ (viz příklad 1.1.) je  S = {(x, 0) | x e Z) podokruhem. Při tom však je:                                                                                            -.»«.. • ;-.-.
ls=  (1,0) * (1,1) -   12XZ a tedy podokruh  S   není unitárním podokruhem okruhu ZXZ.
Definice :  Nechť R  je okruh (resp. teleso); nechť existuje přirozené  ks vlastnosti : (1)                     k.x   = je   +  x  + , . . .  +  x  =   0R   .   pro každé.,,x- S.iJ
k- krát                                                   ;,:.,.i„
Pak nejmenší takové' k se nazýva  charakter isti ka  okruhu  (resp. telesa)  R.   Říkáme pak,   ze okruh (resp. teleso) R  je charakteristiky    k . Jestliže zadné přirozené k  s vlastnosti  (1)  neexistuje, pak nkame, ze okruh (resp. teleso)  R  je charakteristiky  O .
V našem prípade, kdy  R   má jedničku   \R ,  lze urcit charakteristiku  R., pouze vyšetřováním vlastností   1R.   jak ukazuje následující veta.
Veta 1.2:   Nechť R   je okruh (resp. teleso). Existuje-U přirozené  k  takové, ze   k.l      =   0R ,   pak nejmenšítakové k je charakteristikou okruhu (resp. ňlesa) R.   NeéxistujeAi žádné takové k,  pak okruh (resp. teleso) R  je charakteristiky  O.
(D úkaz   :   nechť  k je nejmenší přirozené číslo s vlastností  :   k. 1_J= 0R . Pak pro libovolný prvek r 6 R je fcr - r..+ r + . . . + r =  lx.r t,,L\R.:^* . . + \R.r  =   Cls + ls+. • ■ •+ 1RV. r  =   (k.\H).r =   0R,r  =   0R   «.odkud plyne tvrzeni.]
Vidíme tedy napr., ze triviální okruh je charakteristiky   1   ,    okruh Zm zbytkových tříd modulo   m    je charakteristiky   m   ,  okruh funkci  RR je Stejné charakteristiky jako je okruh R   a všechny ostatní vysé zmiňované okruhy nebo telesa, tj.  Z, G. Q. K. K,   ZXZ  jsou charakteristiky   O .
Definice :   Nechť R   =   (/?,+,.) ,  R' = (R1,   ®, o ) jsou okruhy (resp. telesa).   Zobrazení <p :   R -> R'  se nazývá' h o m o m o r f i z m u s  okru h u (resp.   telesa   )  R   do  okruhu  (resp.   telesa  )  R' ,  jtitliie pro libovolné  a,b  €  R  platí;
<p  (a + b)   =  <p (a)  a>  tfj>)    ,    y> (a-b)   " >p («) • <p (é) . Je-li navíc zobrazení ip   injektivní, pak hovofíme o  izomorfizmu  R  do R' nebo léí o   vnoření R   do  R'.   Je-li  ^  bíjektivní, pak hovoříme o   izomorfizmu   R   na  R' a říkáme, ze R   a_ R'  jsou   Izomorfní.
Poznámka :   v dalším budeme obvykle operace sčítaní, resp. násobení v  R a  R'   označovat stejnými symboly. Nemůže dojít k nedorozumení, protože ze způsobu zápisu je patrne,   žďa ' jde o operaci v R' nebo v Ä'.' Základní vlastnosti homomorfizmu jsou probrány v   [9)i uvedme si nyní pouze tuto vetu :
Veta 1.3 :  Nečhť R, R' jsou okruhy; nechť if ■: R -* R' je hpmomorflzmus okruhu   R   do  R' .  Pak. <p (R) je podokruhem v R' .
[D u k a z   :  je  <f (R)   =    { x' € R' I  existuje x £ R   tak, že y)(x) = x'} S K' Zrejme je  <p (R)  i=  $   a je to množina uzavřená  vzhledem k odeťítánía násobe-nív i?'.  Navíc »sO») je jedničkou <p (R). (Obecne však nikoliv jedničkou R'W). Tedy ifi (R) je podokruhem okruhu  R'.] .
Poznámka :  je-li  *p : R -*  R'   vnorením  R do R', pak zrejmé R   a  \p (R) jsou z algebraického hlediska stejrie (mají stejné'vlastnosti). Muzenie tedy ztotožnit prvky % .R. % jim odpovídajícími prvky (t.j. jejich obrazy pri  i/>) ye  <f(R)   a o-kruh/?   muzeme pak povazovat za podokruh okruhu  R.
Definice:  Každý podokruh (resp. podteleso) telesa K komplexních čísel nazývame  číselným  okruhem  (resp.   c í s e I n. y m   t e Je s.e m ).
Vidíme tedy, že Z, resp. G jsou číselné" okruhy ; Q, resp. R, resp. K jsou číselná'' telesa. Dalíí príklady číselných okruhu a tries jsou uvedeny ve cvičení 1. Je zřejmé^ že každý netriviální číselný okruh je oborem integrity a je charakteristiky O. Zvláítní postavení mezi číselnými tělesy má teleso Q, které je mezi, nimi   "nejmenš?", přesněji řečeno, je obsazeno v každém číselném telese.    Z obec-
■néjSího hlediska tuto situaci popisuje následující víta.
Vétn 1.4:   Nechť R   je ttlešo charakteristiky   O- Pak existuje pod teleso  S IŽIesa   R   ,   které je izomorfní s t&le.scm    Q    racionálních íísel. [Důkaz   i   viz [9],  důkaz V. 2.2.42.]
Ňa základe poznámky za V.l .3. muzemc tedy slrucnK fikat, ťe káídé tSleso charakteristiky   0   obsahuje tfcíeso   Q   racionálních Čísel.
12,:   DELITEĽNOSŤ V OKRUHU A V OBORU INTEGRITY,.
S pojmem dělitelnosti se můžeme setkat JÍŽ na střední Öcole plŕl vyšetřováni dělitelnosti v oboru celých Jíísel. Nyní ukážeme, jak lze tyto otázky studovat obecněji v oboru integrity nebo dokonce v libovolném okruhu.                            '-•'
Definice: Nechť R je okruh, nechť a.b e R. Jestliže existuje prvek r B R takový, Že h.r - a, pak říkáme, ze b d Ulf a (nebo tel, íe prvék a je d e í t í é l n ý prvkem b) a píšeme : b \a. V opacnéth pf'ípadí říkáme, Že b n e d í1 i a (nebo též, Že a n e n í d é l i t e i ň y b ) a píšeme : b \ a . Relaci    1    nazýváme relací dělitelnosti na  R.
Poznámka :  je-li a =  0 , pak zřejmé  b 10  pro každý prvek, b S R-(stačí totií položit   r = 0 ).   Na druhé straní, je-li   b = Ü, pak  0  1«  jediní"V připadl ze a  =  0.  Často se budeme při studiu dělitelnosti omezovat pouze na nenulové prvky z    R   .
Víta 2.1 :  Nechŕ' R  je okruh; pak platí :                                   V "•-* :■>'■■
1.   relace dělitelnosti na  R  je reflexivní a transitivní
2.  jsou-li a,.....a'., b e R  pevné prvky, pro níí   b I a,  (i ■ I, . . , k)  a jsou-
li    a,,.....tk   e  R   libovolné, pak :
k                                               .        '
b I S rtrH, = n,»i + ■•• + «,»,
-   11   -
[D ů k a z   :   1.  zřejmé' pró libovolná  a e R  je: \.a  =  ä,  t. zn. a ľa Děle, je-ll  c Iď,  b la,  pak podle definice existují r,s' e R   tak, Že   :   '"' c.r = b,   b.s  - a .  Po dosazení Je pak :   c. (r.s)  =  a-, h zn.  cla.
2. je-li  b la( , pak existuje  ;-( 6 R   tak, íc  b.r, = ä;'*■••• ( i'<* 1.....k) a tedy :                                                                                     ;"
X au   '=   £ Ir«  =   b. £ r.u. , t. zn.    b I  2 a.u,   .    1
Poznámka : pomocí dělitelnosti lze rovntó charakterizovat pojem jednotky v R   , definovaný v předchozím paragrafu. Zrejme prvek  ě e" R  je jednotkou okruhu  R    práve kdyí  e I» ln ;  navíc součin  e-... -ek Je jednotkou v R , přiví kdyrkařdé ,e( (ŕ = I,,.......-., ,k) je jednotkou v R . Odtud pak JiŽ lehce
plyne, äíe množina, AR)  všech jednotek v R   tvoří (vzhledem k operaci násobe-nív R ) grupu.
. Definice:  Nechť R je okruh.  Jestliže pro a,b £ R  existuje jednotka e  e J(R) tak, Že platí:  a = b,e,  pak ľíkďme, Že prvek a je  a s o'c i. o , -ván  s p r v k e m   b ,   a pííeme : a \ b .  Jelikož relace    "w je symetrická (jak bitde ukázáno nííé), budeme obvykle fikat, ze p r v k y a., b j so u, a -s o c I o v a n y (VR).                                                                                -■'    '
Veta 2.2 :  Necht" R  je okruh; pak relace asociovanosti    "ú je relaci ekvivalence na mnozinÜ R.
[D.ů.k a z :   reflexivita :  a = a . 1 , t. zn, a "v a  pro libovolné' a  £ R . symetrie :   nechf a "v b , t. zn. existuje e G J(R)  tak, ze a = b.e. Ale  e"' 6 J(R)  a po vynásobení tímto prvkem dostávame :   ft = a.c'1, t, zn.  b "\> a .
transitlvlta :   nechi a ^ b, b ^ c , t. zn, existují'«,,«4 e. ./(fl) tak, fe a = 6;c, ,  b = c.Ej ,  t. zn. dosazením :  a = c. (e2.c,), pri.cumZ ere, e y (Ä-) .Tedy  fl.-vc. ]■       .
Poznámka:  z předchozí vity plyne, ze relace asociovanosti  "V  vytvarfna /í jistý lozkíad.  Tfídy tohoto rozkladu jsou tvorený vídy navzájem asociovanými.
-   12   -
prvky.  Prvek   0R   sam o sobe vždy vytváří jednu takovou třídu. Dale pak.všechny jednotky okruhu  R   tvorí dalsí trídu tohoto rozkladu, neboť jsou asociovány s prvkem   1R . Je-ti specielní R   tělesem, pak všechny nenuloví prvky jsou navzájem asociovány (nebof jsou to jednotky) a tedy rozklad, příslušný relaci  ^   má   praví dvé výíe zmiňované ťrídy  {Oj   aß-   [0 } .   Z hlediska dělitelnosti je proto těleso pro nás nezajímavé a v dalších vatách se omezíme na situaci, š níz se budeme nejcasteji setkávat, t. zn. na prípad, že   R  je oborem integrity.
VÍta 2.3:   Nechř R   je obor integrity;  a,b  e R .   Pak platí:
a "v b         *>     a \b  .   b \a .
[Důkaz   :'  " •» "  je-li  ú   "v b   ,  pak existuje jednotka  é  S; 7(K)  ták, £e  a =   b.e .   Odtud pak    f>.= .a.c~'     '.  Tedy je  alb.' b ha\      ' ~-    ':■% ■ " f*. "   necht alb  ,   b \ a .  Je-li a = 0 , pak musí byt A«-b = 0   a tedy  a 'v b .    Nechf tedy  a ¥= 0 .   Pak existují prvky  r,r 6 R   tak,  že a.r -  b .   b.r' = a , t. zn. po dosazeni :   a ( r.r )  -  a   = a.l ,  odkud podle V. 1.1.je r.r' = 1   a tedy  r,r'£iJ(R). Potom vsak je a "V b . \
V^ta 2.4.:   Nechť R   je obor integrity ;   nechť a, b, a\ b''..€ R.   Pak
1.  pro kaídou jednotku  e S J(R) a kaídý prvek  r e. R  platí :  e I r
2.  je-li  a 'v a ,   b' "V  b .   pak  a I b  praví kdyl   a'\ b' ■ [D ü k a z   :   ad 1 : platí  r  = l.r  =   e. (e'1 .r) , t. zn.  e I r .
ad 2 -.nechř a' -v a , fc' "v b, alb . Pak užitím V.2.3. lze psát : a' 1 a, alb, i> I b' odkud vzhledem k transitivite relace dělitelnosti i dostaváme :   a'\b' ■. Opačná implikace se dôkaze analogicky.: j
Poznámka :   z předchozích dvou vet vidíme, že každý prvek daného oboru integrity  R    je vždy dáitelný všemi jednotkami z R  a Víemi s ním asociovanými prvky. Zavedeme proto následující definici.                                               .,
Definice: Nechř R je obor integrity, nechř r e R. Pak všechny jednotky z ; R a všechny prvky asociované s r se nazývají nevlastní dělitelé prvku   r .   Ostatní dělitelé prvku   r (pokud existují) se nazývají v l a s t n ť d e  ■
-   13   -
Hielt'.'                                                                                         .
Nechŕ p £ R je nenulový prvek, který není jednotkou v R . Pak prvek p se nazývá r e d u c i b i J n f (resp. i r e d u c i b i l n í i y R , jestliže ma (resp. nemá) vlastní dělitele v  R.
Poznámka : jinými slovy řečeno, prvek p BR je ireducibilní v R , jestliže jej nelze napsat jako součin dvou prvků z R , z nichž žádný není jednotkou, ani není s prvkem p asociován. Z definice dále vidíme, ze v telese (kde každý nenulový prvek je jednotkou) nemá vyšetřování reducibility a ireducibility smysl.
Veta 2.5: Nechf R je obor integrity; nechř p , o e R a platí p "V o . Pak : prvek p je ireducibilní v  R   pravé když prvek  q  je ireducibilní v R.        .
[Důkaz  :   ze symetrie relace    "v  plyne, že stačí dokázat pouze jednu implikaci.   Necht tedy  p   je ireducibilní v R   a dale nechť    e S  J (R) je jednotka v  R   taková,  že  p   =  q.e .  Odtud plyne, že  q  =ŕ 0 ,  q fá J (R). Dale sporem : je-li    q   reducibilní, pak   q   =  a.b , kde a.b jt' J(R) ;  a, b   nejsou asociovány s  o.  Pak ale  p   = q.e  =  (e.a).b, pri   cemz  e.a, b  <é J(R)    a  zrejmé' e.a, b   nejsou asociovaný s  p.  Pak p  je reducibilní,   coľ. jespor.  Tedy    q     je ireducibilní. ]
Příklad 2.1 :   Okruh. Z   cel/ch čísel má dví jednotky,   a sice  i 1, t. zn. k danému číslu   c E Z jsou asociovány pouze   - c . Tedy cislo  pS Z je ireduči-bilním prvkem v Z    práve tehdy, když    p  =ŕ  0 , p   =ŕ+ 1.  a jeho jedinými děliteli jsou čísla  + 1,   +p .   Stračne ŕeceno,  p  je ireducibilním prvkem v  Z  pravé když absolutní hodnota z čísla p je prvočíslo.
Definice: Nechť R je obor integrity, nechť M je neprázdni podmnožina R Pak prvek t SR se nazýva společný dělitel množiny M v R , jestliže je t\m ' pro každý prvek   m S M.  Píšeme pak :   ti M.
Prvek   d S  R   se nazýva' n e j v e t s ( s p o l e c n y   dělitel  množiny  M   v  R   ,   je-li :
."   -
14
(f)    d \M
(li)   pro  s£ R   s vlastností s\M   je  íl d .
V pripadli, ie M je konečná množina, napi.  M - [a. a,, :. . , u   j,  pafc hovorme o společném děliteli (resp. největším společném délttelt) prvků  a{, g«,, . . , an v K .
Poznámka :  z předchozí definice obecne neplyne existence nejyistíího společného dělitele množiny  Aí    (aŕuz konečne nebo nekonečne).  Na druhé Sttanej o jednoznačnosti největšího společného dělitele lze zcela obecne.vyslqyit tuto vetu.;
Veta 2.6 :  Nechť R  je obor integrity a nechť existuje největší společný dělitel d mtioíiny M v R. Pak D = (reJ!|rMl]/e množina vSech největších špóléěňých dělitelů mnoiiny M v R.
[ D B k a z :   1. necht" q B R je nejvetžl spoleiný délitel množiny M . Prvek d však splňuje : d | M , t. zn. podle definice je d \ q . Analogicky je q | d, neboť d je podle predpokladu největší společný délitel M . Tedy : d\q , q\d a podle
V.2.3. je q^d , t. zn. q€D .
II. nechf q £ D ;  pak existuje jednotka  e é J(R) tak, zé q = d.e .
Ale z toho, že  d je nejvetíí společný dělitel M   bezprostredne" plyne, že d. e  =  q
je také' největší společný délitel množiny   M   v R .   ]

6
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, 0 <   r < | ň |, 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     tp{n) vyjadřuje počet přirozených čísel menších nebo rovných číslu «,
*          1
nesoudělných s n. Nechť n =   p/a' . ... /?*"*, pak   platí     (p(n) = n . M (1------). Je-li n
J       Pi
prvočíslo, pak (p(n) = n -1.
Kongruence:   a, b e Z, m e N, m > 2. Platí a = b <=>    m\ {a -b). Čteme: Číslo n 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 kongntencí:
1)  p prvočíslo, pak   a s b (mod p") =>    a = ft (mod p)
Platí-li kongruence podle modulu, který je mocninou prvočísla, platí i podle modulu rovného tomuto prvočíslu.
2) a = b (mod/;?i),;' = 1,2.....k =>    a = b (mod NSN(w/,...,»34))
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.) «i = bi (mod m),;' = l,...,k =>     ^Tŕ/, = ^ft( (mod m),     [Jö/ = f~[ft, (mod m).
1=1                /-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 = b + x (mod m), a .y = b . y (mod 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)ffi|z=>    a + z = b (mod m)
Celé číslo, které je násobkem modulu, lze přičíst pouze k jedné straně kongruence.
6) a" b Ď" (mod m)
Obě strany kongruence lze umocnit na libovolný přirozený exponent.
T)d\a a d\b a  NSDW m)=l =>    - ■ - (mod/w)
d        d
Obě strany kongruence lze vydělit celým číslem nesoudělným s modulem.
8) ac = be (mod mc)
Obě strany kongruence i modul lze vynásobit týmž celým kladným číslem.
n\    \                \ u            I                 a      b 1     a m \
9)e|flA   e\b a   e|c=>     — = — (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 =b (mod m) a   d I 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 nezjedná.
Eulerova věta: m e N, m > 1, a e Z, NSD(tí, m) = 1, pak a^m) = 1 (mod m).
Je-li specielně p prvočíslo, které není dělitelem čísla a, pak platí ď    = 1 (mod p) (tzv. malá
Fermatova věta).