MA 366: KONGRUENS

John Rognes

§2.2: Eulers ϕ-funksjon

Definisjon. For et naturlig tall n, la ϕ(n) være antallet heltall mellom 1 og n som er relativt primiske til n.

ϕ(n) = #{k ∈ ℕ | 1 ≤ k ≤ n, (k, n) = 1} .

Eksempel. For n = 24 er ϕ(24) = 8, siden 1, 5, 7, 11, 13, 17, 19 og 23 er heltallene mellom 1 og 24 som er relativt primiske til 24.

Lemma. For p et primtall er ϕ(p) = p − 1. Mer generelt er da

ϕ(p^{e}) = p^{e} − p^{e−1} = p^{e−1}(p − 1) = p^{e}(1 − 1/p) .

Bevis. Med n = p^{e} og 1 ≤ k ≤ n er (k, n) = 1 hvis og bare hvis p ∤ k. Det er p^{e−1} heltall mellom 1 og p^{e} som er delelige med p, så ϕ(p^{e}) = p^{e} − p^{e−1}. □

Proposisjon 2.2.4. ∑_{d|n} ϕ(d) = n.

Bevis. Betrakt de rasjonale tallene 1/n, 2/n, …, (n − 1)/n og n/n, og skriv hvert av dem på redusert form, som en brøk av relativt primiske heltall. Nevnerne vil da være divisorer i n. Hvis d er en slik divisor vil nøyaktig de ϕ(d) brøkene k/d med 1 ≤ k ≤ d og (k, d) = 1 forekomme med nevner lik d. Ved å samle brøkene med samme nevner, og summere antallet brøker med slik nevner hver for seg følger proposisjonen. □

Eksempel. Når n = 24 er brøkene 1/24, 1/12, 1/8, 1/6, 5/24, 1/4, 7/24, 1/3, 3/8, 5/12, 11/24, 1/2, 13/24, 7/12, 5/8, 2/3, 17/24, 3/4, 5/6, 7/8, 11/12, 23/24 og 1/1. Så ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(6) = 2, ϕ(8) = 4, ϕ(12) = 4 og ϕ(24) = 8, mens 1 + 1 + 2 + 2 + 2 + 4 + 4 + 8 = 24.

§3.3: Kongruensregning modulo m

Vi har sett på likningen

ax ≡ b (mod m) ,

med a og b hele tall, m et naturlig tall og x et ukjent helt tall. Hvis x er en løsning og x ≡ y (mod m), så er y også en løsning. Vi regner slike løsninger x og y som ekvivalente, og regner dem bare en gang når vi teller antall løsninger til den gitte likningen.

Vi har vist:

Typeset by AMS-TEX

Proposisjon 3.3.1. Kongruensen ax ≡ b (mod m) har en løsning hvis og bare hvis d | b, der d = (a, m). I så fall er det nøyaktig d løsninger. Hvis x_{0} er en løsning er de andre løsningene x_{k} = x_{0} + (k/d)m for 0 < k < d.

Korollar 1. Hvis (a, m) = 1 har ax ≡ b (mod m) en entydig løsning.

Bevis. Her er d = (a, m) = 1 per antagelse, som alltid deler b. □

Korollar 2. Hvis p er et primtall og p ∤ a så har ax ≡ b (mod p) en entydig løsning.

Bevis. Her er d = (a, p) = 1 fordi p ∤ a. □

Disse resultatene kan reformuleres som utsagn om den kommutative ringen ℤ/m.

Proposisjon 3.3.2. Et element ā ∈ ℤ/m er en enhet hvis og bare hvis (a, m) = 1. Det er nøyaktig ϕ(m) enheter i ℤ/m.

Ringen ℤ/m er en kropp hvis og bare hvis m er et primtall. Ellers har ℤ/m nulldivisorer.

Bevis. Et element ā ∈ ℤ/m er en enhet hvis og bare hvis likningen āx = ¯1 har en løsning, som er ekvivalent med kongruenslikningen ax ≡ 1 (mod m). Denne har en løsning hvis og bare hvis d = (a, m) deler b = 1, dvs. hvis og bare hvis a og m er relativt primiske.

Antallet enheter i ℤ/m er derfor lik antallet heltall mellom 1 og m som er relativt primiske til m, dvs. ϕ(m).

Hvis m = p er et primtall og ā ≠ ¯0 i ℤ/p så er (a, p) = 1 og likningen āx = ¯1 har en løsning, så alle elementer ≠ 0 i ℤ/p har en invers. Altså er ℤ/p en kropp.

Hvis m = m_{1}m_{2} ikke er et primtall, med m_{1}, m_{2} ≥ 2, så er m̄_{1} ≠ ¯0 en nulldivisor i ℤ/m siden m̄_{2} ≠ ¯0 med m̄_{1}m̄_{2} = \overline{m_{1}m_{2}} = m̄ = ¯0. Altså er ℤ/m ikke en kropp. □

Definisjon–Lemma. La U(ℤ/m) = (ℤ/m)^{∗} være gruppen av enheter i ℤ/m. Gruppeoperasjonen er multiplikasjonen i ringen ℤ/m, og skrives multiplikativt. Da er (ℤ/m)^{∗} en abelsk gruppe med ϕ(m) elementer.

Korollar 1 (Eulers teorem). Hvis (a, m) = 1 er a^{ϕ(m)} ≡ 1 (mod m).

Bevis. Når (a, m) = 1 er ā en enhet i ℤ/m, dvs. et element i gruppen (ℤ/m)^{∗} med ϕ(m) elementer. Ordenen til undergruppen generert av ā deler ordenen til (ℤ/m)^{∗}, så ā^{ϕ(m)} = ¯1, dvs. a^{ϕ(m)} ≡ 1 (mod m). □

Eksempel. Med m = 24 er ϕ(m) = 8, så for (a, 24) = 1 er a^{8} ≡ 1 (mod 24). Men i dette tilfellet gjelder den sterkere kongruensen a^{2} ≡ 1 (mod 24) for alle (a, 24) = 1. Hvorfor ? Jo, gruppen (ℤ/24)^{∗} = {1, 5, 7, 11, 13, 17, 19, 23} ≅ ℤ/2 × ℤ/2 × ℤ/2 har orden 8 men eksponent 2.

Korollar 1’. Hvis (ℤ/m)^{∗} har eksponent e(m), og (a, m) = 1, så er a^{e(m)} ≡ 1 (mod m).

Vi skal se senere at for m en odde primtallspotens er (ℤ/m)^{∗} en syklisk gruppe, så dens eksponent e(m) er lik dens orden ϕ(m). Eulers resultat er derfor optimalt for m en odde primtallspotens.

Korollar 2 (Fermats lille teorem). Hvis p er et primtall og p ∤ a er a^{p−1} ≡ 1 (mod p).

Bevis. Dette er tilfellet m = p av Eulers teorem, siden ϕ(p) = p − 1 og (a, p) = 1 er ekvivalent med p ∤ a. □

Korollar 2’. Hvis p er et primtall er a^{p} ≡ a (mod p) for alle heltall a.

Bevis. Hvis p | a vil p | a^{p} så a^{p} ≡ 0 ≡ a (mod p). Hvis ikke er a^{p−1} ≡ 1 (mod p) ved Korollar 2, og resultatet følger ved å multiplisere denne kongruensen med a. □

§3.4: Det kinesiske restteoremet

Hvis m kan faktoriseres som et produkt av forskjellige primtall, dvs. ikke er en primtallspotens, så kan kongruens modulo m reduseres til et system av enklere kongruenser.

Hypotese. I hele dette avsnittet la m = m_{1} · . . . · m_{t}, der (m_{i}, m_{j}) = 1 for alle i ≠ j. Så tallene m_{1}, …, m_{t} er parvis relativt primiske og m er deres produkt.

Definisjon. La ℤ/m_{1} × ⋯ × ℤ/m_{t} være produktet av ringene ℤ/m_{1}, …, ℤ/m_{t}. Et element i ℤ/m_{1} × ⋯ × ℤ/m_{t} er et t-tuppel (r_{1}, …, r_{t}) med r_{i} ∈ ℤ/m_{i} for alle i. Sum, differens og produkt i ℤ/m_{1} × ⋯ × ℤ/m_{t} er definert komponentvis, dvs. (r_{1}, …, r_{t}) ± (s_{1}, …, s_{t}) = (r_{1} ± s_{1}, …, r_{t} ± s_{t}) og (r_{1}, …, r_{t}) · (s_{1}, …, s_{t}) = (r_{1}s_{1}, …, r_{t}s_{t}). Null- og enhetselementene i produktringen er henholdsvis 0 = (0, …, 0) og 1 = (1, …, 1).

For hver i = 1, …, t er det en ringhomomorfi ψ_{i}: ℤ → ℤ/m_{i} som tar a ∈ ℤ til kongruensklassen ā ∈ ℤ/m_{i}. Produktet av disse definerer en ringhomomorfi ψ_{1} × ⋯ × ψ_{t}: ℤ → ℤ/m_{1} × ⋯ × ℤ/m_{t}. Denne tar idealet (m) ⊂ ℤ til null siden m ≡ 0 (mod m_{i}) for alle i. Derfor faktoriserer ψ_{1} × ⋯ × ψ_{t} gjennom ℤ/m, som følger:

Definisjon. La ringhomomorfien

ψ: ℤ/m → ℤ/m_{1} × ⋯ × ℤ/m_{t}

være gitt ved

ψ(ā) = (ā_{1}, …, ā_{t})

hvor a_{i} ≡ a (mod m_{i}) for alle i. Siden m_{i} | m er dette uavhengig av valget av representant a ∈ ℤ for ā ∈ ℤ/m.

Vi trenger to enkle lemmaer:

Lemma 1. Hvis m_{1} er relativt primisk til m_{i} for alle 2 ≤ i ≤ t, så er m_{1} relativt primisk til produktet m_{2} · . . . · m_{t}.

Bevis. Hvis p er et primtall som deler m_{2} · . . . · m_{t} må p dele m_{i} for en 2 ≤ i ≤ t. Men da kan ikke p dele m_{1} siden (m_{1}, m_{i}) = 1. Altså er m_{1} og m_{2} · . . . · m_{t} relativt primiske. □

Lemma 2. Hvis m_{1} | a, …, m_{t} | a og (m_{i}, m_{j}) = 1 for alle i ≠ j, så vil m_{1}·. . .·m_{t} | a.

Bevis. Dette vises ved induksjon på t. For t = 1 er det klart. Anta at lemmaet gjelder for t − 1 faktorer, så m_{2} · . . . · m_{t} | a. Ved Lemma 1 er m_{1} relativt primisk til m_{2} · . . . · m_{t}, så det finnes heltall x og y med m_{1}x + m_{2} · . . . · m_{t}y = 1. Da er m_{1}xa + m_{2} · . . . · m_{t}ya = a, og m_{1} · . . . · m_{t} deler begge ledd på venstre side. Altså må m_{1} · . . . · m_{t} | a. □

Nå kan vi vise:

Teorem 1’. Anta m = m_{1} · . . . · m_{t} med (m_{i}, m_{j}) = 1 for alle i ≠ j. Da er ψ en isomorfi av ringer:

ψ: ℤ/m ⟶^{≅} ℤ/m_{1} × ⋯ × ℤ/m_{t} .

Bevis. Hva er kjernen til ψ ? Hvis a ∈ ℤ med ψ(ā) = (0, …, 0) må a ≡ 0 (mod m_{i}) for alle i, dvs. m_{i} | a for alle i. Ved Lemma 2 må m = m_{1} · . . . · m_{t} | a, dvs. ā = 0 i ℤ/m. Så ψ er injektiv.

Men ℤ/m har m elementer og ℤ/m_{1} ×⋯×ℤ/m_{t} har m_{1} ·. . .·m_{t} = m elementer, så siden ψ er injektiv har bildet av ψ også m elementer, så ψ er også surjektiv. En bijektiv ringhomomorfi er en ringisomorfi. □

Dette kan reformuleres som:

Teorem 1 (Det kinesiske restteoremet). Anta m = m_{1}·. . .·m_{t} med (m_{i}, m_{j}) = 1 for alle i ≠ j. La b_{1}, …, b_{t} være heltall, og betrakt kongruensene:

x ≡ b_{1} (mod m_{1}), …, x ≡ b_{t} (mod m_{t}) .

Disse har alltid en løsning x, og to ulike løsninger er kongruente modulo m.

Eksempel. Med m_{1} = 3, m_{2} = 5 og m_{3} = 7 er m = m_{1}m_{2}m_{3} = 105. Likningene x_{1} ≡ 1 (mod 3), x_{1} ≡ 0 (mod 5), x_{1} ≡ 0 (mod 7) har løsningen x_{1} = 70. Likningene x_{2} ≡ 0 (mod 3), x_{2} ≡ 1 (mod 5), x_{2} ≡ 0 (mod 7) har løsningen x_{2} = 21. Likningene x_{3} ≡ 0 (mod 3), x_{3} ≡ 0 (mod 5), x_{3} ≡ 1 (mod 7) har løsningen x_{3} = 15. Generelt har da likningen

x ≡ b_{1} (mod 3), x ≡ b_{2} (mod 5), x ≡ b_{3} (mod 7)

løsningen x = 70b_{1} + 21b_{2} + 15b_{3}. Det finnes en entydig løsning mellom 0 og 104, nemlig resten til dette uttrykket for x ved divisjon med 105.

Proposisjon 3.4.1.

(ℤ/m_{1} × ⋯ × ℤ/m_{t})^{∗} = (ℤ/m_{1})^{∗} × ⋯ × (ℤ/m_{t})^{∗}

som delmengder av ℤ/m_{1} × ⋯ × ℤ/m_{t}.

Bevis. Enhetene i ℤ/m_{1} × ⋯ × ℤ/m_{t} er t-tupler (u_{1}, … u_{t}) med u_{i} ∈ ℤ/m_{i} slik at det finnes et t-tuppel (v_{1}, …, v_{t}) med v_{i} ∈ ℤ/m_{i} slik at u_{i}v_{i} = 1 i ℤ/m_{i} for alle i. Dette er ekvivalent med at u_{i} er en enhet i ℤ/m_{i} for hver i. □

Korollar. Det er en gruppeisomorfi

(ℤ/m)^{∗} ≅ (ℤ/m_{1})^{∗} × ⋯ × (ℤ/m_{t})^{∗}

og ϕ(m) = ϕ(m_{1}) … ϕ(m_{t}).

Bevis. Ringisomorfien ψ restrikterer seg til en gruppeisomorfi

(ℤ/m)^{∗} ≅ (ℤ/m_{1} × ⋯ × ℤ/m_{t})^{∗}

mellom enhetsgruppene. Sammen med Proposisjon 3.4.1 gir dette korollaret. □

Vanligvis faktoriserer vi m som et produkt av primtallspotenser.

Proposisjon. La m = p_{1}^{e_{1}} · . . . · p_{t}^{e_{t}} med p_{i} ≠ p_{j} for i ≠ j. Det er en ringisomorfi

ℤ/m ≅ ℤ/p_{1}^{e_{1}} × ⋯ × ℤ/p_{t}^{e_{t}}

og en gruppeisomorfi

(ℤ/m)^{∗} ≅ (ℤ/p_{1}^{e_{1}})^{∗} × ⋯ × (ℤ/p_{t}^{e_{t}})^{∗} .

Ordenen til disse gruppene er

ϕ(m) = ϕ(p_{1}^{e_{1}}) · . . . · ϕ(p_{t}^{e_{t}}) = m ∏_{i=1}^{t}(1 − 1/p_{i}) .

Bevis. Det eneste som gjenstår er utregningen ϕ(p_{1}^{e_{1}}) · . . . · ϕ(p_{t}^{e_{t}}) = p_{1}^{e_{1}}(1 − 1/p_{1}) · . . . · p_{t}^{e_{t}}(1 − 1/p_{t}) = m ∏_{i=1}^{t}(1 − 1/p_{i}). □

Eksempel. m = 24 = 2^{3}·3, så (ℤ/24)^{∗} ≅ (ℤ/8)^{∗}×(ℤ/3)^{∗} og ϕ(24) = ϕ(2^{3})·ϕ(3) = 2^{2}(2−1)·(3−1) = 8. Her er (ℤ/8)^{∗} = {¯1, ¯3, ¯5, ¯7} ≅ ℤ/2×ℤ/2 en Klein firergruppe, og (ℤ/3)^{∗} = {¯1, ¯2} ≅ ℤ/2.

§4.1 Enhetsgruppen (ℤ/p)^{∗} er syklisk

Ved det kinesiske restteoremet er gruppestrukturen til enhetene i ℤ/m der m er et naturlig tall bestemt av tilfellet der m er en primtallspotens. Vi begynner med tilfellet der m er et primtall.

Lemma 1. La k være en kropp og f(x) ∈ k[x] et polynom av grad n. Da har f(x) høyst n ulike røtter i k.

Bevis. Dette er klart ved induksjon på graden til f(x). □

Proposisjon 4.1.2. Hvis d | p − 1 har likningen x^{d} ≡ 1 (mod p) nøyaktig d ulike løsninger i ℤ/p.

Bevis. La p − 1 = de. Da er

(x^{p−1} − 1) = (x^{d} − 1)g(x)

med g(x) = x^{d(e−1)} + ⋯ + x^{d} + 1. Polynomet x^{p−1} − 1 har (p − 1) ulike røtter i ℤ/p ved Fermats lille teorem, og g(x) har høyst d(e − 1) ulike røtter ved Lemma 1, så x^{d} − 1 har minst (p − 1) − d(e − 1) = d ulike røtter. Ved Lemma 1 igjen har x^{d} − 1 nøyaktig d ulike røtter. □

Teorem 1 (Gauss). La p være et primtall. Enhetsgruppen (ℤ/p)^{∗} er en syklisk gruppe.

Bevis. For d | p−1 la ψ(d) være antall elementer i (ℤ/p)^{∗} av orden lik d, dvs. antall elementer ā ∈ (ℤ/p)^{∗} der d er det minste naturlige tall n slik at a^{n} ≡ 1 (mod p). Ved Proposisjon 4.1.2 er det d elementer i (ℤ/p)^{∗} som oppfyller x^{d} ≡ 1 (mod p), og hver av disse har en orden som deler d. Ved å telle opp får vi ∑_{c|d} ψ(c) = d.

Viser ved induksjon at ψ(d) = ϕ(d) for alle d | p−1. For d = 1 er ψ(1) = 1 = ϕ(1). Anta ved induksjon at ψ(c) = ϕ(c) for alle c | d med c ≠ d. Da er

ψ(d) = d − ∑_{{c|d \atop c≠d}} ψ(c) = d − ∑_{{c|d \atop c≠d}} ϕ(c) = ϕ(d) .

Her har vi brukt Proposisjon 2.2.4.

Altså er ψ(p − 1) = ϕ(p − 1) ≥ 1. Så det finnes et element i (ℤ/p)^{∗} av orden lik (p − 1), som også er ordenen til denne gruppen. Altså er (ℤ/p)^{∗} syklisk. □

Siden (ℤ/p)^{∗} har orden ϕ(p) = p − 1 kan vi skrive (ℤ/p)^{∗} ≅ ℤ/(p − 1). Et valg av en slik isomorfi svarer til et valg av en generator for (ℤ/p)^{∗}. Det er ϕ(p−1) slike valg, siden ℤ/(p − 1) har ϕ(p − 1) ulike generatorer.

Definisjon. Et heltall a kalles en primitiv rot modulo p dersom ā genererer gruppen (ℤ/p)^{∗}. Så a er en primitiv rot modulo p dersom p − 1 er det minste naturlige tall n slik at a^{n} ≡ 1 (mod p).

Eksempel. 2 er en primitiv rot modulo p for p = 3, 5, 11, 13 og 19, men ikke for p = 7 eller 17.

Oslo, 20. februar 2000