Forfatter: Shadowmaker

Nu tænker du nok; Gad vide hvad en gruppe er. Og hvad kan det med grupper bruges til?

Måske tænker du? Skal jeg ikke bare springe det med grupper over, det virker list mystisk, det er nok for svært for mig. Men brug nu 15 minutter på at læse testen, tænk over hvad der står, og så har du styr på hvad en gruppe er.

Det med grupper er egentlig ikke så svært. Det er måske lidt abstrakt, men det er ikke svært. Hvis man arbejder med matematik, så lægger man måske mærke til, at man, i en masse forskellige tilfælde, står over for de samme problemer/udfordringer. Måske lægger man mærke til, at de ting man arbejder med, opfører sig på sammen måde, og at de opgaver man skal løse, kan løses på samme måde, selv om der er tale om helt forskellige ting. Her skal læseren se en masse konkrete eksempler/opgaver for sig, som måske, i første omgang, ikke har noget med hinanden at gøre, men som faktisk kan løses på præcis samme måde. At de kan løses på præcis sammen måde skyldes måske, at det er samme slags problemer, bare i forskellige forklædninger. Matematikeren ser måske dette, og laver så en generel teori der beskriver de forskellige konkrete eksempler, og forklarer hvordan opgaver kan løses. Gruppeteori er noget abstrakt matematik, som kan bruges i en masse konkrete tilfælde.

Måske har jeg hægtet læseren af her, for hvad mener jeg? Hvis du går i gymnasier, så kender du til lineær vækst. Det er noget med y = ax + b. Lineær vækst kan bruges til at beskrive en masse konkrete eksempler. Selve teorien om lineær vækst er en abstrakt teori, der ikke er bundet til eksemplerne. Teorien for lineær vækst kommer fra, at en matematiker, en gang for længe siden, har set en masse fællestræk ved en masse konkrete opgaver. Matematikeren har så lavet en abstraktv teori om ‘ineær vækst’. Den generelle teori om lineær vækst kan så bruges i en masse konkrete eksempler; taletidskort, taxakørsel, …

Eller et mere jordnært eksempel: Når man tager kørekort, så lærer man at køre bil. Man lærer ikke at køre Volvo. Man lærer ikke at køre Opel. Man lærer at køre i den abstrakte størrelse der kaldes for’ bil’. Grunden til at det giver mening, altså det at lære at køre bil, er, at alle biler, mere eller mindre, opfører sig på samme måde. Der er et rat, der er et gear, der er nogle pedaler m.v. Når man har lært at køre ‘bil’, så kan man køre Volvo, så kan man køre Opel, …

Når man har taget kørekort til ‘grupper’, så ved man hvordan man arbejder med grupper, og man ved hvilke regler der gælder for grupper. Når man så møder en konkret gruppe, så kan den generelle teori, som man har lært, bruges til det konkrete tilfælde.

Nok snak. Tilbage til det med grupper.

Vi ved alle hvad der menes med en gruppe mennesker. Men hvad menes der med en gruppe, i matematik?

I matematik er en gruppe ikke anden end en mængde af elementer, og en regneoperation, som opfylder de fire krav:

1 – Mængden af elementer skal være lukket mht. regneoperationen.
2 – Der skal gælde en parentesregel; a + (b + c) = (a + b) + c
3 – Der skal være et neutralt element.
4 – Alle elementer skal have et inverst element.

Lad og sige at vores regneoperation er ‘+’.
Kalder vi elementerne for a, b, c, … så kan de fire krav, til det at være en grupper, skrives

1 – Summen a + b af to elementer a og b skal også være et element i mængden af elementer.
2 – Der skal gælde at a + (b + c) = (a + b) + c.
3 – Der skal være et nul-element 0 (nul).
4 – For hvert element a skal der findes et andet element b, således at a + b = 0 (og b + a = 0).

I nogle grupper er a + b ikke lig b + a, så derfor står der i punkt 4 at der både skal gælde at a + b = 0 og b + a = 0.

Som huskeregel for de krav, der er til det at være en gruppe, kan man bruge ‘CAN I’.

Bogstavet ‘C’ står for ‘Closed’, dvs. lukket. Bogstavet ‘A’ så for ‘Associativ’, som er navnet på parentesreglen. Bogstavet ‘N’ så for ‘Neutralt element’. Bogstavet ‘I’ står for ‘Inverst element’.

Det lyder måske lidt mystisk, og for folk der er vant til at bruge ‘grupper’ er det nok trivielt, men for os andre er det med grupper en noget mystisk ting, som ikke siger de fleste ret meget. Men prøv at huske på ‘CAN I’, og se se på eksemplerne herunder.

C = Closed = Lukket
A = Associativ regel: a + (b + c) = (a + b) + c
N = Neutral element N
I = Alle elementer har et inverst element, summen af de to lig N.

Eksempel 1

Lad og se på mængden af de hele tal. Som regneoperation tager vi ‘plus’, dvs. ‘+’.

Påstanden er nu, at mængden af hele tal, med regneoperationen ‘plus’, er en gruppe.

1 – Lægger vi to hele tal sammen, så får vi et nyt helt tal. Mængden af hele tal, sammen med ‘plus’, er altså lukket.
2 – For hele tal gælder at a + (b + c) = (a + b) + c. F.eks. er 6 + (4 + 3) = (6 + 4) + 3. Det er derfor man ikke skriver parenteser når man skriver 6 + 4 + 3, for det er lige meget i hvilken rækkefølge man lægger tallene sammen. Hvis rækkefølgen betød noget, så skulle man nemlig indsætte parenteser.
3 – Det neutrale element er 0. Når man lægger tallet 0 til et helt tal a, så gælder jo at a + 0 = a og 0 + a = a .
4 – Alle elementer skal have et inverst element. Elementet 7 har f.eks. det inverse element -7. Det skyldes at 7 + (-7) = 7 – 7 = 0.

Eksempel 2

Lad os nu prøve selv at lave en gruppe. Vi siger at der skal være fire elementer i grupper. Lad os kalde de fire elementer for a, b, c og d.

I sidste afsnit så vi på kongruens. Nu skal vi se lidt på restklasser. De to begreber kongruens og restklasser hænger sammen.

Vi ser først på kongruens modulo 5. Vi skriver tallene 0, 1, 2, 3, 4 i første række i en tabel.

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24
25	26	27	28	29
30	31	32	33	34
35	36	37	38	39
40	41	42	43	44
45	46	47	48	49

Når vi skriver at \(2+3=5\), så er lighedstegnet et tegn der fortæller, at summen af tallene 2 og 3 er det samme som tallet 5. Lighedstegnet fortæller altså, at tallet på venstre side er lige så stort som tallet på højre side.

Når vi skriver \(17 \equiv 42\) så står der også hele tal på begge sider. Tallene på de to sider er ikke ens, men de står i den samme søjle i tabellen. På samme måde er \(2+3 \equiv 0\). På venstre sider står der tallet 5, skrevet som en almindelig sum af tallene 2 og 3. Men 5 ligger jo i samme søjle som tallet 0. Derfor er \(2+3 \equiv 0\).

Under tallet 0 i første række står der tallene 5, 10, 15, 20, 25, … Alle disse tal er naturligvis ikke lig med tallet 0. F.eks. er 5 jo ikke lig med 10. Men tallene 5, 10, 15, 20, 25, … er alle kongruente med tallet 0.

\(5 \equiv 0 \:,\: 10 \equiv 0 \:,\: 15 \equiv 0 \:,\: 20 \equiv 0 \:,\: ...  \)

Det er klart, at alle hele tal er kongruente med ét af tallene 0, 1, 2, 3, 4. Tænk nemlig på et tal. Vi kan så fortsætte tabellen øverst i det uendelige, og på et eller andet tidspunkt så vil vi nå frem til det tal du tænker på. Øverst i den søjle hvor dette tal står, finder vi et af tallene 0, 1, 2, 3, 4. Det tal, du tænkte på, er så kongruent med tallet i første række, lodret over dit tal.

Negative tal, som -117, er også kongruent med et af tallene 0, 1, 2, 3, 4. Tabellen skal bare fortsættes i negativ retning, og på et eller andet tidspunkt støder vi på tallet -117.

Et tal som 2177 er også kongruent med ét af tallene 0, 1, 2, 3, 4. Men hvilket? Hvis vi ikke vil udfylde tabellen indtil vi når tallet 2177, hvad gør vi så? Lad os se på en del af tabellen fra før:

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19

Vi kan skrive alle tal der er større end 4 på en anden måde:

0	1	2	3	4
\(1 \cdot 5 + 0\)	\(1 \cdot 5 + 1\)	\(1 \cdot 5 + 2\)	\(1 \cdot 5 + 3\)	\(1 \cdot 5 + 4\)
\(2 \cdot 5 + 0\)	\(2 \cdot 5 + 1\)	\(2 \cdot 5 + 2\)	\(2 \cdot 5 + 3\)	\(2 \cdot 5 + 4\)
\(3 \cdot 5 + 0\)	\(3 \cdot 5 + 1\)	\(3 \cdot 5 + 2\)	\(3 \cdot 5 + 3\)	\(3 \cdot 5 + 4\)

Vi lægger mærke til, at

– alle tal i kolonnen med et 0 øverst kan skrives som et helt tal gange 5.
– alle tal i kolonnen med et 1-tal øverst kan skrives som et helt tal gange 5, plus 1.
– alle tal i kolonnen med et 2-tal øverst kan skrives som et helt tal gange 5, plus 2.
– alle tal i kolonnen med et 3-tal øverst kan skrives som et helt tal gange 5, plus 3.
– alle tal i kolonnen med et 4-tal øverst kan skrives som et helt tal gange 5, plus 4.

Den opmærksomme læser vil måske genkende regnestykkerne i tabellen herover som noget der kommer fra heltalsdivision.

Hvis vi dividerer f.eks. 17 med 5, så går divisionen ikke op, der kommer en rest på 2:

\(17 = 3 \cdot 5 + 2 \)

Det kan illustreres således:

Dermed ser vi at

– alle tal i kolonnen med et 0 øverst giver en rest på 0 ved division med 5.
– alle tal i kolonnen med et 1 øverst giver en rest på 1 ved division med 5.
– alle tal i kolonnen med et 2 øverst giver en rest på 2 ved division med 5.
– alle tal i kolonnen med et 3 øverst giver en rest på 3 ved division med 5.
– alle tal i kolonnen med et 4 øverst giver en rest på 4 ved division med 5.

Her findes forklaringen på begrebet restklasser. Tager man et helt tal, og dividerer det med 5, så får man en rest på 0, 1, 2, 3 eller 4. Resten (ved divisionen) fortæller altså hvilket af tallene 0, 1, 2, 3, 4 som tallet er kongruent med.

Restklassen 0 er de hele tal, så er kongruente med 0. Restklassen 1 er de hele tal, som er kongruente med 1. Restklassen 2 er de hele tal, som er kongruente med 2. Restklassen 3 er de hele tal, som er kongruente med 3. Restklassen 4 er de hele tal, som er kongruente med 4.

En restklasse er altså ikke et tal, men en samling af uendelige mange tal:

\(\bold{0} \;=\; \{... \;,\; -15 \;,\; -10 \;,\; -5 \;,\; 0 \;,\; 5 \;,\; 10 \;,\; 15 \;,\; ...\}\)

\(\bold{1} \;=\; \{... \;,\; -14 \;,\; -9 \;,\; -4 \;,\; 1 \;,\; 6 \;,\; 11 \;,\; 16 \;,\; ...\}\)

\(\bold{2} \;=\; \{... \;,\; -13 \;,\; -8 \;,\; -3 \;,\; 2 \;,\; 7 \;,\; 12 \;,\; 17 \;,\; ...\}\)

\(\bold{3} \;=\; \{... \;,\; -12 \;,\; -7 \;,\; -2 \;,\; 3 \;,\; 8 \;,\; 13 \;,\; 18 \;,\; ...\}\)

\(\bold{4} \;=\; \{... \;,\; -11 \;,\; -6 \;,\; -1 \;,\; 4 \;,\; 9 \;,\; 14 \;,\; 19 \;,\; ...\}\)

Eksempel 1

Lad os finde ud af hvilken restklasse talet 4321 hører til.

Vi dividerer 4321 med 5. Tallet 5 går 864 gange op i 4321, og der er en rest på 1:

\(4321 = 864 \cdot 5 + 1\)

Dermed er \(4321 \equiv 1\), og tallet 4321 hører til restklassen 1.

Eksempel 2

Lad os nu se på kongruens modulo 18.

Antag at vi skal finde du af hvilket af tallene 0, 1, 2, 3, 4, … , 17 som tallet 654321 er kongruent med.

Det er ikke indlysende hvad svaret er. Men lad os dividere 654321 med 18:

\(\frac{654321}{18}=36351.1666667\)

Resultatet fortæller, at 654321 kan skrives som 36351 18’ere, og en rest. Da \(36351 \cdot 18 = 654318\), så mangler vi 3 for at komme helt op til 654321. Vi har altså at

\(654321 = 36351 \cdot 18 + 3\)

Ved divisionen får man en rest på 3, og dermed er 654321 kongruent med 3.

Tallet 654321 hører dermed til restklassen 3 når vi ser på kongruens modulo 18.

Under udarbejdelse….læs ikke videre 🙂

Når man skriver \(\bbbZ_n\), så mener man elementerne 0, 1, 2, 3, 4, … n. Elementerne i \(\bbbz_n\) kan kombineres med addition; ‘+’. Man kan altså lægge elementer sammen i \(\bbbz_n\). Når man har lagt to elementer sammen, så får man et nyt element i

Når man skriver \((\bbbz_n)^*\), så mener man de elementer blandt 0, 1, 2, 3, 4, …, som er primiske med n. Elementerne i \((\bbbz_n)^*\) kan kombineres med multiplikation ‘\(\cdot\)‘. Man kan altså lægge elementer sammen i \((\bbbz_n)^*\),

Vi vi i dette afsnit se på mængden \((\mathbb{Z}_5)^*\), der indeholder de fem elementer 0, 1, 2, 3, 4.

Vi skal se på hvordan man multiplicerer to elementer, dvs. hvordan man ganger to elemeter fra \(\mathbb{Z}_5\) med hinanden. Vi bruger symbolet ‘\(\cdot\)‘ for gange.

Vores legeplads i dette afsnit er altså de fem elementer \({ \:0, \:1 , \:2, \:3, \:4 }\), og vi skal se på regler for hvordan man lægger to elementer sammen og hvordan man ganger to elementer.

Det, at vi har valgt at kalde de fem elemener i \(\mathbb{Z}_5\) for 0, 1, 2, 3, 4 er forpligtende. Skal man addere 1 og 2, så skulle man gerne få 3. Sådan er det med de helt tal. Det vil være forvirrende hvis 1 + 2 = 4.

Vi går lige til sagen. Vi laver en tabel for addition og en tabel for multiplikation:

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

\(\cdot\)	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Den måde tabellerne udfyldes på, er ved at se på det talskema vi har set tidligere:

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

Som almindelige hele tal har vi f.eks. at 2 + 3 = 5. Men 5 er kongruent med 0, så i vores mængde \(\mathbb{Z}_5\) er \(2 + 3 =5 \equiv 0 \), og der ser man i additionstabellen.

På samme måde så vil der for de helt almindelige hele tal gælde, at \(4 \cdot 4 = 16\). Men da 16 er kongruent med 1, så gælder i \(\mathbb{Z}_5\) at \(4 \cdot 4 = 16 \equiv 0\). Det ser vi også i multiplikations-tabellen.

For at lave regneregnerne for de fem elementer i \(\mathbb{Z}_5\), så går vi altså nogle gange ‘ud’ af mængden \(\{ \:0, \:1 , \:2, \:3, \:4 \}\) , men med kongruens fører vi resultatet tilbage igen til mængden \(\{ \:0, \:1 , \:2, \:3, \:4 \}\).

Dette afsnit hedder restklasser, og det er præcis det mængen \(\mathbb{Z}_5\) bestående af 5 elemener er, med de regneregler der er defineret i de to tabelle.

Det er desuden klart hvad \(\mathbb{Z}_5\) er, og det burde være klart hvordan vi regner i \(\mathbb{Z}_5\).

I dette afsnit skal vi se på division med heltal.

Lad os sige at vi skal lægge nogle brædder i forlængelse af hinanden, så de samlet har en længde på 20 meter. Måske skal vi lave et stakit der skal være 20 m langt.

I byggemarkedet har de brædder der er 3 m lange. Hvor mange af dem skal vi bruge, for at vi kan sætte dem i forlængelse af hinanden, og nå op på 20 m?

Figuren viser at vi skal bruge 6 hele brædder med en længde på 3 m, og så er der en rest på 2 m. Vi må naturligvis købe 7 brædder, eller har vi ikke nok.

Hvis vi vil beregne hvor mange brædder vi skal købe, så skal vi dividere 20 med 3. Vi skal nemlig finde ud af hvor mange gange 3 går op i 20. Da 20 ikke er i 3-tabellen, så går divisionen ikke op; der komme en rest. Divisionen kan skrives som

\(20 = 6 \cdot 3 + 2\)

Man kalder tallet 20 for dividenden. Tallet 3 er divisoren. Når man har udført divisionen, altså bestemt tallene 6 og 2, så kalder man 6 for kvotienten og man kalder 2 for resten.

Mere generelt:

• Det tal, der skal deles, kaldes for dividenden.
• Det tal, vi deler med, kaldes for divisoren.
• Det hele antal gange divisoren går op i dividenden kaldes for kvotienten
• Det, der er til overs ved divisonen, kaldes for resten.

Man kan altså skirve en division som

\(\textrm{dividend} = \textrm{kvotient} \cdot \textrm{divisor} + \textrm{rest}\) 

Eksempel

Vi vil dividere 19 med 5. Vi ser at 5 går op 3 gange i 19, med en rest.

Resten er \(19 – 5 \cdot 3 = 19-15 = 4\).

Dermed har vi at

\(19 = 3 \cdot  5  + 4\)

Dividenden er altså tallet 19. Divisoren er tallet 5. Kvotienten er tallet 3. Resten er tallet 4.

Antag at vi har to hele tal a og b. Vi vil finde det største hele tal, som både går op i tallet a og i tallet b. Dette tal kaldes for den største fælles divisor.

Den største fælles divisor for to hele tal a og b skrives som sfd(a, b). På engelsk skriver man gcd(a, b).

Eksempler:

Lad os se på de to tal a = 2 og b = 4.
De eneste tal der går op i 2 er tallene 1 og 2. 
De eneste tal der går op i 4 er tallene 1, 2 og 4. 
Dermed er sfd(2, 4) = 2.

Lad os se på de to tal a = 2 og b = 6.
De eneste tal der går op i 2 er tallene 1 og 2. 
De eneste tal der går op i 6 er tallene 1, 2 og 3. 
Dermed er sfd(2, 6) = 2.

Lad os se på de to tal a = 4 og b = 6.
De eneste tal der går op i 4 er tallene 1, 2 og 4. 
De eneste tal der går op i 6 er tallene 1, 2 og 3. 
Dermed er sfd(4, 6) = 2.

Lad os se på de to tal a = 12 og b = 9.
De eneste tal der går op i 12 er tallene 1, 2, 3, 4, 6, 12. 
De eneste tal der går op i 9 er tallene 1, 3 og 9. 
Dermed er sfd(12, 9) = 3.

Lad os se på de to tal a = 12345 og b = 2345.

De eneste tal der går op i 12345 er tallene 
1, 3, 5, 15, 823, 2469, 4115, 12345.

De eneste tal der går op i 2345 er tallene 
1, 5, 7, 35, 67, 335, 469, 2345.

Dermed er sfd(12345, 2345) = 5.

Når tallene a og b er store tal, så kan man ikke sådan lige finde de tal der går op i hver af dem.

Det er her Euklids algoritme kommer ind i billedet. Euklids algoritme er en effektiv metode til at bestemme den største fælles divisor for to tal.

Euklids algoritme bruges til at bestemme den største fælles diviser for to hele tal.

Den største fælles divisor for to hele tal a og b skrives som sfd(a, b).

Euklids algoritme er en effektiv metode til at bestemme den største fælles divisor for to tal.

I Euklids algoritme udfører man den ene heltalsdivsion efter den anden.

Eksempel 1

Lad os se på et eksempel på anvendelse af Euklids algoritme.

Antag at a = 86 og b = 46. Vi vil bestemme sfd(86, 46).

Vi dividerer først 86 med 46. Vi ser, at 46 kun går én gang op i 86. Resten ved divsionen er 86-46 = 40. Dermed har vi at

\(86 = 1 \cdot \color{blue} 46 \color{black} + \color{red}40\color{black}\)

Jeg har farvet divisoren 46 blå, og jeg har farvet resten på 40 rød.

Nu skal vi dele den forrige divisor med den forrige rest. Vi skal altså dele 46 med 40. Vi ser, at 40 går præcis én gang op i 46. Resten ved divisionen er 46-40 = 6. Dermed har vi at

\(\color{blue} 46 \color{black}= 1 \cdot \color{red}40\color{black} + 6\)

Nu skal vi igen dele divisoren (her 40) med resten (her 6). Sådan fortsætter vi, indtil divisionen går op. Vi dividerer altså hele tiden divisoren med resten, indtil divisionen går op.

Alt i alt får vi, med dette eksempel:

\(86 = 1 \cdot \color{blue} 46 \color{black} + \color{red}40\color{black}\)
\(\color{blue} 46 \color{black}= 1 \cdot \color{red}40\color{black} + 6\)
\(\color{red}40\color{black} = 6 \cdot 6 + 4\)
\(6 = 1 \cdot 4 + \color{red}2\color{black}\)
\(4 = 2 \cdot 2 + 0\)

Til sidst går divisionen op. Den sidste rest, der ikke er lig nul, er så den største fælles divisor. I dette tilfælde er det tallet 2, som jeg har farvet rødt.

Dermed er sfd(86, 46) = 2.

Eksempel 2

Et andet eksempel. Vi vil bestemme sfd(124, 56).

\(124 = 2 \cdot \color{blue} 56 \color{black} + \color{red}12\color{black}\)
\(\color{blue} 56 \color{black}= 4 \cdot \color{red}12\color{black} + 8\)
\(\color{red}12\color{black} = 1 \cdot 8 + \color{red}4\color{black}\)
\(8 = 2 \cdot 4 + 0\)

Dermed er sfd(124, 56) = 4.

Hvorfor virker Euklids algoritme?

Antag at vi vil bestemme sfd(a, b).

Vi skal altså bestemme det største hele tal som både går op i a og i b.

Vi dividerer a med b, og får en rest r:

\(a = q \cdot b + r\)

På figuren herunder er tegnet et liniestykke med længden a og et liniestykke med længden b.

Det røde tynde rektangel skal forestille en målestok.

Antag at a er lige så lang som et helt antal målestokke, og at b er lige så lang som et helt antal målestokke. Da må resten r også være lige så lang som et helt antal målestokke.

Og omvendt, er b er lige så lang som et helt antal målestokke, og er resten r lige så lang som et helt antal målestokke, så må a være lige så lang som et helt antal målestokke.

Sagt på en anden måde; hvis et tal går op i både a og i b, så vil tallet også gå op i resten r.

Og omvendt, hvis et tal går op i både b og i resten r, så går det også op i a.

De tal, som både går op i a og i b, er præcis de samme tal som dem der går op i b og i resten r.

Det største tal som går op i a og i b, er dermed lig det største tal som går op i b og i resten r.

Vi har altså at

\( \textrm{sfd}(a,b) = \textrm{sfd}(b,r)\)

Nu kalder jeg resten \( r \) for \(r_1\) iden næste division giver en ny rest:

\( \textrm{sfd}(a,b) = \textrm{sfd}(b,r_1) = \textrm{sfd}(r_1,r_2) = ... \)

Pythonprogram

Herunder er vist et lille Pythonprogram som udfører Euklids algoritme.

Først indtaster man de to tal a og b.

I funktionen sfd(a, b) printes mellemregninger på formen

\(\textrm{dividend} = \textrm{kvotient} \cdot \textrm{divisor} + \textrm{rest}\)

Tallet a er dividenden. Kvotienten beregnes ved brug af a // b der beregner hvor mange hele gange b går op i a. Divisoren er tallet b. Resten, ved divisionen, beregnes ved a % b.

Funktionen sfd(a, b) returnerer divisoren og resten; det er jo de to tal der skal jo bruges til næste heltalsdivision.

While-løkken kalder funktionen sfd(a, b) så længe resten ikke er lig nul.

a = int( input('Indtast et helt tal ') )
b = int( input('Indtast et helt tal ') )

def sfd(p,q):
    print(a ,"=",a//b,"*",b,"+",a % b)
    return b,a % b

while True:
    a,b=sfd(a,b)
    if b==0 :
        break

Eksempel på output ved beregning af sfd(987654321, 7654321)

Indtast et helt tal 987654321
Indtast et helt tal 7654321

 987654321 = 129 * 7654321 + 246912
 7654321 = 31 * 246912 + 49
 246912 = 5039 * 49 + 1
 49 = 49 * 1 + 0

Dermed er sfd(987654321, 7654321) = 1

Eksempel på output ved beregning af sfd(6655443322, 55443322):

Indtast et helt tal 6655443322
Indtast et helt tal 55443322

 6655443322 = 120 * 55443322 + 2244682
 55443322 = 24 * 2244682 + 1570954
 2244682 = 1 * 1570954 + 673728
 1570954 = 2 * 673728 + 223498
 673728 = 3 * 223498 + 3234
 223498 = 69 * 3234 + 352
 3234 = 9 * 352 + 66
 352 = 5 * 66 + 22
 66 = 3 * 22 + 0

sfd(6655443322, 55443322) = 22.

Det skal bemærkes at Python naturligvis har en indbygget funktion som straks beregner største fælles divisor.

Et naturligt tal, der kun kan deles med tallet 1 og tallet selv, kaldes for et primtal.

Det mindste primtal er tallet 2. Tallet 1 er ikke et primtal.

De naturlige tal er mængden \(\{1, 2, 3, 4, …\}\).

Eksempler

Tallet 2 er et primtal, da det kun er deleligt med tallet 1 og tallet 2.

Tallet 3 er et primtal, da det kun er deleligt med tallet 1 og tallet 3.

Tallet 4 er ikke et primtal; det kan nemlig deles med tallene 1, 2 og 4.

Tallet 5 er et primtal, da det kun er deleligt med tallet 1 og tallet 5.

Tallet 6 er ikke et primtal; det kan nemlig deles med tallene 1, 2, 3 og 6.

Tallet 7 er et primtal, da det kun er deleligt med tallet 1 og tallet 7.

Tallet 8 er ikke et primtal; det kan nemlig deles med tallene 1, 2, 4 og 8.

Eksempel fra den virkelige verden

Antag at vi skal sætte nogle ens brædder i forlængelse af hinanden, således at den samlede længde bliver 17 meter.

I byggemarkeder har de brædder med længderne 1m, 2m, 3 m, 4 m, …, 17 m.

Hvordan kan vi sætte ens bræddert i forlængelse af hianden, således at den samlede længde bliver 17 m?

Der er faktisk kun to muligheder; enten skal vi tage 17 brædder med en længde på 1 m, eller også skal vi tage ét langt bræt med en længde på 17 m.

Forklaringen er, at 17 er et primtal, så ingen af tallene 2, 3, 4, …, 16 går op i tallet 17.

De første primtal

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 113, 127, 131, 137, 149, 151, …

Er et tal et primtal?

Det er let at afgøre om et lille tal er et primtal; det er bare at prøve efter.

Skal vi f.eks. undersøge om 251 er et primtal, så kan vi bare dividere 251 med 2, så med 3, så med 4, så med 5 o.s.v. for at se om nogle af disse tal går op i 251.

Det er klart at lige tal ikke kan gå op i 251, og man kan også let udelukke en del andre tal på vejen som man ikke behøver at dividere op i 251. Hvis f.eks. 3 ikke går op i 251, så går 9 heller ikke op i 251. Hvis 9 nemlig går op i 251, så vil 3 gå to gange op i 251.

Desuden behøver man ikke dividere med alle tal, helt op til 251, for at undersøge om 251 er et primtal. Det er nok at prøve med tallene op til 15.

Det skyldes, at \(\sqrt{251}=15.84\). Dermed er \(251 = 15.84 \cdot 15.84\). Hvis 251 kan skrives som \( a \cdot b\), hvor a og b er heltal, med f.eks. a større end 15,84, så må b være mindre end 15,84.

Har vi derfor prøvet at dividere 251 med alle hele tal op til 15, uden at andre end tallet 1 går op, så kan ingen andre tal gå op i 251. Hvis et tal over 15 gik op i 251, så ville der jo også være et tal under 15 som går op i 251.

Hvis man vil undersøge om meget store tal er primtal, så kan man ikke bare afprøve alle muligheder. Det kan jo ikke nytte noget at det tager 1 mio år, på den hurtigste computer, at undersøge om et tal er et primtal. Der er flere andre, og smarte metoder, som på kort tid kan afgøre om et tal er et primtal.

RSA-kryptering bygger på, at tager man to meget store primtal \(p\) og \(q\), og ganger dem med hinanden; \(n = p \cdot q\), så kan man ikke på nogen let måde bestemme \(p\) eller \(q\) alene ud fra tallet \(n\). Det er altså let at gå den ene vej; det med at gange de to primtal, men det er meget vanskeligt at gå den anden vej; det med, ud fra kendskab til n, at finde p eller q.

Bemærk at det er ret let at afgøre om tallet n er et primtal; det er det naturligvis ikke da både p og q går op i det. Men det hjælper ikke på opgaven med at bestemme p eller q.

Aritmetikkens fundamentalsætning

Primtal spille en stor rolle i talteorien. En vigtig sætning er aritmetikkens fundamentalsætning. Den fortæller, list løst, at alle hele tal er bygget op af primtal.

Det vises lettest med nogle eksempler:

\(2 = 2\)
\(3 = 3\)
\(4 = 2 \cdot 2 = 2^2\)
\(5 = 5\)
\(6 = 2 \cdot 3\)
\(7 = 7\)
\(8 = 2 \cdot 2 \cdot 2 = 2^3\)
\(9 = 3 \cdot 3 = 3^2\)
\(10 = 2 \cdot 5\)
\(11 = 11\)
\(12 = 2 \cdot 2 \cdot 3 = 2^2 \cdot 2\)
\(13 = 13\)
\(14 = 2 \cdot 7\)
\(15 = 3 \cdot 5\)

På venstre side har jeg tallene 2, 3, 4, … og på højre side står der, hvordan disse tal er opbygget af primtal.

Aritmetikkens fundamentalsætning siger, at alle tal kan skrives som et produkt af primtal, dvs. som primtal ganget med hinanden. Sætningen siger også at det kun kan gøres på én måde. Her er det underforstået, at det at bytte om på to tal, ikke tæller som anden måde; \(6 = 2 \cdot 3\) og \(6 = 3 \cdot 2\) er altså ikke to forskellige måder.

Når man har skrevet et helt tal som et produkt af primtal, så siger man, at man har lavet en primfaktoropløsning af tallet.

Vi kan vælge lidt større eksempler:

\(100 = 2^2 \cdot 5^2\)
\(12345 = 3 \cdot 5 \cdot 823\)
\(987654321 = 3^2 \cdot 17^2 \cdot 379721\)
\(998877665544332211 = 3^2 \cdot 11 \cdot 229 \cdot 547 \cdot 883 \cdot 9277 \cdot 9833\)

Alle de tal der står på højre side af lighedstegnet er primtal. De resultater har jeg naturligvis ikke regnet ud ved håndkraft. Jeg har brugt Maple, og funktionen ifactor( ).

I sidste afsnit så vi på Fermats lille sætning. I dette afsnit skal vi se på Eulers sætning, som er en udvidelse af Fermats lille sætning.

Fermats lille sætning siger at:

Lad p være et primtal, og lad a være et element i \(\mathbb{Z}_p\).
Er a ikke nul, så er \( a^{p-1} \equiv 1 \)

Eller mere generelt, hvor a er et vilkårligt helt tal:

Lad p være et primtal, og lad a være et vilkårligt helt tal. 
Hvis p ikke går op i a, så er \(a^{p-1} \equiv 1\)

Fermats sætning siger altså noget om potenser af a, når p er et primtal.

Men hvad nu hvis p ikke er et primtal? Hvis p ikke er et primtal, så bruger vi bogstavet n i stedet for p. Den mængde vi ser på er så mængden \(\mathbb{Z}_n\).

Hvis n = 6.

Tallet 6 er ikke et primtal, for \(6 = 2 \cdot 3\). Lad os se på potenser af a, når a ligger i \(\mathbb{Z}_{6}\):

	0	1	2	3	4	5
1	0	1	2	3	4	5
2	0	1	4	3	4	1
3	0	1	2	3	4	5
4	0	1	4	3	4	1
5	0	1	2	3	4	5

Vi ser at det kun er elementet 5 fra \(\mathbb{Z}_6\) som giver 1-taller. Bortset naturligvis fra elementet 1 som altid giver 1-taller.

Vi ser også at der kommer 1-taller når 5 opløftes til 2. potens og til 4. potens:

\(5^2 = 25 \equiv 1 \quad 5^4 = 5^2 \cdot 5^2 \equiv 1 \cdot 1 \equiv 1 \)

Hvis n = 10.

Tallet 10 er ikke et primtal, for \(10 = 2 \cdot 5\). Lad os se på potenser af a, når a ligger i \(\mathbb{Z}_{10}\):

	0	1	2	3	4	5	6	7	8	9
1	0	1	2	3	4	5	6	7	8	9
2	0	1	4	9	6	5	6	9	4	1
3	0	1	8	7	4	5	6	3	2	9
4	0	1	6	1	6	5	6	1	6	1
5	0	1	2	3	4	5	6	7	8	9
6	0	1	4	9	6	5	6	9	4	1
7	0	1	8	7	4	5	6	3	2	9
8	0	1	6	1	6	5	6	1	6	1
9	0	1	2	3	4	5	6	7	8	9

Nå ja, tænker du, fint nok, og hvad så? Vi leder, inspireret af Fermats lille sætning, efter rækker med 1-taller. Vi kan ikke finde en række der kun indeholder et enkelt 0 og så lutter 1-taller.

I rækken hvor eksponenten er 4 og i rækken hvor eksponenten er 8 er der en del 1-taller:

	0	1	2	3	4	5	6	7	8	9
4	0	1	6	1	6	5	6	1	6	1
8	0	1	6	1	6	5	6	1	6	1

Man kan passende spørge; hvorfor lige netop eksponenterne 4 og 8?

Man kan også undre sig over hvorfor det lige er elementerne 3, 5, 7 og 9 fra \(\mathbb{Z}_{10}\) som giver 1-taller.

Hvis n = 14

Lad os se på \(\mathbb{Z}_{14}\). Tallet 14 er ikke et primatal, idet \(14 = 2 \cdot 7\). Jeg har lavet tabellen med det Python-program der er vist sidst i afsnittet om Fermats lille sætning.

Vi ser igen efter rækker med mange 1-taller. Det er rækkerne med eksponenterne 6 og 12 der indeholder flest 1-taller.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
6	0	1	8	1	8	1	8	7	8	1	8	1	8	1
12	0	1	8	1	8	1	8	7	8	1	8	1	8	1

Igen kan vi spørge; hvorfor er det eksponenterne 6 og 12 som giver de mange 1-taller? Hvorfor er det lige netop elementerne 1, 3, 5, 7, 9, 11, 13 som giver 1 når de opløftes til potenserne 6 og 12?

Opsamling

Lad os lave en lille oversigt over de resultater vi fik herover:

n = 6. Elementer 1 og 5. Eksponenter 2 og 4.
n = 10. Elementer 1, 3, 7, 9. Eksponenter 4 og 8.
n = 14. Elementer 1, 3, 5, 7, 9, 11, 13. Eksponenter 6, 12.

Det er måske ikke til at se det, hvis man ikke lige ved det:

For n = 6 er tallene 1 og 5 de tal under 6, der er primiske med tallet 6.
For n = 10 er tallene 1, 3, 7, 9 de tal under 10, der er primiske med tallet 10.
For n = 14 er tallene 1, 3, 5, 7, 9, 11, 13 de tal under 14, der er primiske med tallet 14.

Måske tænker du; hvad vil det sige at to tal er primiske? To tal er primiske hvis det eneste tal, som går op i begge, er tallet 1.

Eksempler for n = 6 :
– Tallene 5 og 6 er primiske, for det eneste tal der går op i både 5 og 6 er tallet 1.
– Tallene 4 og 6 er ikke primiske, for tallet 2 går op i både 4 og 6.
– Tallene 3 og 6 er ikke primiske, for tallet 3 går op i både 3 og 6.
– Tallene 2 og 6 er ikke primiske, for tallet 2 går op i både 2 og 6.
– Tallene 1 og 6 er primiske, for det eneste tal der går op i både 1 og 6 er tallet 1.

Så fik vi styr på den ene del:

De elementer i \(\mathbb{Z}_n\), der er primiske med n, 
giver 1-taller når de opløftes til visse potenser. 

Men hvad med eksponenterne, hvordan hænger de sammen med valg af n ?

Når \(n = 6 = 2 \cdot 3\) er den mindste eksponent lig 2.
Når \(n = 10 = 2 \cdot 5\) er den mindste eksponent lig 4.
Når \(n = 14 = 2 \cdot 7\) er den mindste eksponent lig 6.

Der er tilsyneladende en sammenhæng mellem de to primtal som n er opbygget af, og den mindste eksponent som giver de mange 1-taller: Eksponenten er, i disse tre tilfælde, en mindre end det store primtal.

Find lige frem til Fermats lille sætning igen; her er eksponenten jo også \(p-1\), altså en eksponent der er en mindre end primtallet.

Det viser sig, at (den mindste) eksponent kan udregnes ved formlen

Eksponent = \((p_1-1) \cdot (p_2-1)\)

Her er \(p_1\) og \(p_2\) de to primtal som tallene n = 6, n = 10 og n = 14 er bygget op af.

Eulers sætning

Efter den lange diskussion, så er vi klar til at formulere Eulers sætning:

Lad n være et helt positivt tal, og lad a være et element i \(\mathbb{Z}_n\).
Når a er primisk med n, så er \( a^{\varphi(n)} \equiv 1 \)

Eller mere generelt, hvor n bare er et helt (positivt) tal, og a er et helt tal:

Hvis a og n er primiske, så er \(a^{\varphi(n)} \equiv 1 \)

Vi må lige slutte af med at forklare hvad \(\varphi(n)\) er; \(\varphi(n)\) er Eulers phi-funktion.

Når \( n = p_1 \cdot p_2 \), hvor \(p_1\) og \(p_2\) er to primtal, så er \(\varphi(n) = (p_1-1) \cdot (p_2-1)\) .

Eksempler:

\(\varphi(6) = (2-1) \cdot (3-1) = 1 \cdot 2 = 2\)
\(\varphi(10) = (2-1) \cdot (5-1) = 1 \cdot 4 = 4\)
\(\varphi(14) = (2-1) \cdot (7-1) = 1 \cdot 6 = 6\) 

Det var præcis de eksponenter vi fandt ved brug af tabellerne.

Opsamling

Fermats lille sætning fortæller, at \(a^{p-1} \equiv 1\) når a er primisk med primtallet p.

Eulers sætning fortæller, at \(a^{\varphi(n)} \equiv 1 \) når a er primisk med n.

I stedet for bare at opskrive Fermats lille sætning, som sikkert ikke siger ret mange ret meget, så lad os se på nogle eksempler.

Ideen er, som i det foregående, at få nogle mentale billeder af hvad det er Fermats sætning handler om og hvad sætningen udtaler sig om.

Når man kan se det for sig, så bliver det lettere at forstår selve sætningen, og dermed bliver det lettere at huske sætningen, og det bliver lettere at kunne anvende den, nu man ved hvad den handler om.

Lad os begynde med at se på \(\mathbb{Z}_5\):

\(\mathbb{Z}_5 = \{0, 1, 2, 3, 4  \}\)

Vi har, i et tidligere afsnit, set på hvordan man regner i \(\mathbb{Z}_5\). Regnereglerne er nedarvet fra regning med hele tal, man skal bare huske, at får man et resultat udenfor mængden \(\{0, 1, 2, 3, 4\}\), så skal man ‘føre’ det tilbage til mængden \(\mathbb{Z}_5\). Det kan man gøre ved, som tidligere, at udfylde en tabel, og så gå lodret op mod tallene 0, 1, 2, 3, 4. Eller man kan dividere resultatet med 5, og så se på ‘resten’ ved divison med 5.

Vi tager nu elementet ‘3’ fra \(\mathbb{Z}_5\). Vi udregner så potenser af dette tal:

\( 3^1 = 3 \quad 3^2=9 \equiv 4 \quad 3^3=27 \equiv 2 \quad 3^4=81 \equiv 1 \)

Det var så nogle potenser af 3.

Lad os prøve at beregner potenser af alle elementerne i \(\mathbb{Z}_5\).

Vi opskriver resultaterne i en tabel. I første række har vi de fem elementer i \(\mathbb{Z}_5\), her skrevet med fed skrift. I første søjle står eksponenterne, dvs. de tal som vi opløfter i.

	0	1	2	3	4
1	0	1	2	3	4
2	0	1	4	4	1
3	0	1	3	2	4
4	0	1	1	1	1

Kolonnen med tallene markeret med fed grøn skrift svarer til resultatet af de beregninger vi lige udførte med potenser af 3 i \(\mathbb{Z}_5\). Det sidste tal i denne kolonne er tallet 1, der er farvet rødt.

De fire tal i tabellen, markeret med fed rød skrift, fortæller at

\( 1^4 \equiv 1 \quad 2^4 \equiv 1 \quad 3^4 \equiv 1 \quad 4^4 \equiv 1 \quad \)

Det ser altså ud som om at alle elementer i \(\mathbb{Z}_5\) (dog ikke tallet 0) giver 1 når det ganges med sig selv 4 gange.

For \(\mathbb{Z}_5\) har vi altså, for a = 1, a = 2, a = 3 eller a = 4, at

\(a^{5-1} \equiv 1\)

Det kunne jo være at det bare var en egenskab ved \(\mathbb{Z}_5\).

Lad os derfor se på \(\mathbb{Z}_7\), og lave en tilsvarende tabel. Vi har de 7 elementer 0, 1, 2, 3, 4, 5, 6 i første række, og eksponenterne i første søjle.

	0	1	2	3	4	5	6
1	0	1	2	3	4	5	6
2	0	1	4	2	2	4	1
3	0	1	1	6	1	6	6
4	0	1	2	4	4	2	1
5	0	1	4	5	2	3	6
6	0	1	1	1	1	1	1

Ser vi på tallene i sidste række, der igen er skrevet med rød fed skrift, så ser vi at

\( 1^6 \equiv 1 \quad 2^6 \equiv 1 \quad 3^6 \equiv 1 \quad 4^6 \equiv 1 \quad 5^6 \equiv 1 \quad 6^6 \equiv 1 \)

Nu vil nogen måske hævne at tallene 5 og 7 er lidt specielle tal; det er nemlig primtal. Men jeg kunne have valgt alle andre primtal, så ville resultatet være det samme. Man kan så spørge hvad der vil ske hvis man ser på f.eks. \(\mathbb{Z}_{10}\), hvor tallet 10 jo ikke er et primtal da \( 10 = 2 \cdot 5\). Det ser vi ikke på her, men det kommer vi tilbage til i et senere afsnit: Eulers sætning.

I tabellen med potenserne af alle a‘er i \(\mathbb{Z}_5\) stoppede vi ved fjerde portens. Hvordan ville den næste række se ud? Det er ret let at svare på, for \(a^5 = a \cdot a^4\), så vi kommer fra række fire til række fem ved at gange med a. Da der i række fire står en masse 1’taller, så vil der i række fem står tallene 0, 1, 2, 3, 4.

	0	1	2	3	4
1	0	1	2	3	4
2	0	1	4	4	1
3	0	1	3	2	4
4	0	1	1	1	1
5	0	1	2	3	4

Fermats lille sætning

Vi kan nu formulere Fermats lille sætning.

Vi ser på mængden \(\mathbb{Z}_p\), hvor p er et primtal. Når vi bruger tegnet \(\equiv\) så mener vi kongruent mht. \(\mathbb{Z}_p\), altså at vi tager et vilkårligt helt tal, og ved brug af tabellen forklaret tidligere fører det lodret op i et af tallene 0, 1, 2, 3, … , p-1. Alternativt, at vi dividerer tallet med p og ser på ‘resten’.

Lad p være et primtal, og lad a være et element i \(\mathbb{Z}_p\).
Er a ikke nul, så er \( a^{p-1} \equiv 1 \)

Mere generelt:

Lad p være et primtal, og lad a være et vilkårligt helt tal. 
Hvis p ikke går op i a, så er \(a^{p-1} \equiv 1\)

Vi kan også formlere Fermats lille sætning på følgende måde:

Lad p være et primtal, og lad a være et vilkårligt helt tal.
Da er \(a^p \equiv a\)

Man kan spørge om hvorfor der, i sidste version af Fermats lille sætning, ikke står noget med at p ikke må gå op i a. Forklaringen er, at hvis p ikke går op i a, så er \(a^{p-1} \equiv 1\), og ganger vi med a, så får vi at \(a^p \equiv a\). Det er det sætningen siger, så det er ok. Går p derimod op i a, så er \(a \equiv 0\), og dermed er, helt automatisk, \(a^p \equiv 0\). Så den sidste sætning gælder også hvis p går op i a, men resultatet er så ret trivielt at ‘0 = 0’.

For at slutte afsnittet af: Som billede på Fermats lille sætning, betragt den første tabel:

Vi ser på mængden \(\mathbb{Z}_5\). Tabellen indeholder potenser af elementerne 0, 1, 2, 3, 4 fra \(\mathbb{Z}_5\). I række 4, stå der en masse 1’taller. Det er Fermats lille sætning der siger at der skal stå 1’taller i række fire, dog ikke under 0.

Python-program

Det er, sådan set, ret trivielt at udfylde tabellerne herover med resultater. Skal man f.eks. beregne \(3^4\), så kan man gøre følgende:

\( 3^1 \equiv 3 \)
\( 3^2 \equiv 3 \cdot 3 = 9 \equiv 4 \)
\( 3^3 = 3 \cdot 3^2 \equiv 3 \cdot 4 = 12 \equiv 2 \)
\( 3^4 = 3 \cdot 3^3 \equiv 3 \cdot 2 = 6 \equiv 1 \)

Vi går altså et skridt frem ad gangen, og reducerer hver gang så vi bliver indenfor \(\mathbb{Z}_5\). På den måde udngår vi for store tal, og vi får samme resultat som hvis vi bare beregnede \(3^4\) og så, bagefter, reducerede til \(\mathbb{Z}_5\).

Man kan også lave et lille Python-program som udfører beregningerne for en:

n = int( input('Indtast et helt tal ') )

print("   ",end=' ')
 for j in range (0,n):
     print(format(j, '3d'),end=' ')

 print(' ')
 for i in range (1,n):
     print(format(i, '3d'),end=' ')
     for j in range (0,n):
         print(format((j**i) % n,'3d'),end=' ')
     print(' ')

Jeg har ikke kommenteret programmet, men først skrives tallene 0, …, n i første række. Der indledes med nogle mellemrum så alt kommer til at stå pænt.

Så kommer der to løkker; den første, den med i, er en løkke for eksponenten, og for hver værdi af eksponenten i beregnes \(j^i\) for j = 0, 1, 2, 3, … , n-1 som skrives i samme række, så ny række, ny eksponent i, …

Eksempel på output når n = 17:

Bemærk at vi regner i \(\mathbb{Z}_{17}\) , og at der står en masse 1-taller i række 16.

Vi vi i dette afsnit se på restklasserne \({ \:0, \:1 , \:2, \:3, \:4 }\).

Vi skal se på hvordan man lægger to elementer sammen og hvordan man ganger to elementer med hinanden.

Vi bruger symbolet ‘\(+\)‘ for gange, og vi bruger symbolet ‘\(\cdot\)‘ for gange.

Vores legeplads i dette afsnit er altså de fem elementer \({ \:0, \:1 , \:2, \:3, \:4 }\), og vi skal se på regler for hvordan man lægger to elementer sammen og hvordan man ganger to elementer.

Det, at vi har valgt at kalde de fem elemener i \(\mathbb{Z}_5\) for 0, 1, 2, 3, 4 er forpligtende. Skal man addere 1 og 2, så skulle man gerne få 3. Sådan er det med de helt tal. Det vil være forvirrende hvis 1 + 2 = 4.

Vi går lige til sagen. Vi laver en tabel for addition og en tabel for multiplikation:

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

\(\cdot\)	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Den måde tabellerne udfyldes på, er ved at se på det talskema vi har set tidligere:

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

Som almindelige hele tal har vi f.eks. at 2 + 3 = 5. Men 5 er kongruent med 0, så i vores mængde \(\mathbb{Z}_5\) er \(2 + 3 =5 \equiv 0 \), og der ser man i additionstabellen.

På samme måde så vil der for de helt almindelige hele tal gælde, at \(4 \cdot 4 = 16\). Men da 16 er kongruent med 1, så gælder i \(\mathbb{Z}_5\) at \(4 \cdot 4 = 16 \equiv 0\). Det ser vi også i multiplikations-tabellen.

For at lave regneregnerne for de fem elementer i \(\mathbb{Z}_5\), så går vi altså nogle gange ‘ud’ af mængden \(\{ \:0, \:1 , \:2, \:3, \:4 \}\) , men med kongruens fører vi resultatet tilbage igen til mængden \(\{ \:0, \:1 , \:2, \:3, \:4 \}\).

Dette afsnit hedder restklasser, og det er præcis det mængen \(\mathbb{Z}_5\) bestående af 5 elemener er, med de regneregler der er defineret i de to tabelle.

Det er desuden klart hvad \(\mathbb{Z}_5\) er, og det burde være klart hvordan vi regner i \(\mathbb{Z}_5\).

I de næste to afsnit ser vi på \(\mathbb{Z}_n\) og \(\mathbb{Z}_n^{*}\).