Vi vil nu se på mængderne
\(\mathbb{Z}_n\) og \(\mathbb{Z}^{*}_n\)
Inden vi kommer dertil skal vi se på begrebet kongruens.
Kongruens, og restklasser som vi ser på i næste afsnit, spiller en stor rolle inden for talteorien, og ligger til grund for f.eks. RSA kryptering.
I princippet kan man klare definitionerne af kongruens og restklasser på et par linier, men så forsvinder forståelsen.
Det med kongruens og restklasser lyder måske svært, men det er det på ingen måde.
Formålet med de næste afsnit er at forklare begreberne på en sådan måde, at læseren ikke bare præsenteres for færdige begreber, men også får en forståelse for hvad der foregår, og, hvad der også er vigtigt, ser nogle indre billeder for sig, når snakken handler om to begreber.
Vi har før set på de hele tal. Symbolet for de hele tal er \(\mathbb{Z}\) , og det er mængden
\(\mathbb{Z} = \{ \: ... , \: -3 \: , \: -2 \: , \: -1 \: , \: 0 \:, \: 1 \: , \: 2 \: , \: 3 \: , \: ... \}\)
Lad os tage de første ca. 50 hele tal og skrive dem ind 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 |
En række i en tabel er tal der står ved siden af hinanden.
En søjle i en tabel er tal der står lodret over hinanden.
Vi indfører nu et nyt tegn: \(\equiv\)
Tegnet \(\equiv\) læses ‘kongruent med’. Ordet ‘kongruent’ betyder noget i retningen af at være ens. Konkruente figurer er figurer der, ved at flytte dem rund, kan lægges 100% ovenpå hinanden.
Betragt tabellen herover. To tal er kongruente, hvis de hører til i samme søjle i tabellen.
F.eks. er \(17 \equiv 42\) og \(35 \equiv 0\).
Alle tal i samme søjle er kongruente med hinanden.
Det er klart at ethvert helt tal er kongruent med enten 0, 1, 2, 3 eller 4.
Når vi har tallene 0, 1, 2, 3, 4 i første række, så siger man at man ser på kongruens modulo 5.
Hvis vi vil se på kongruens modulo 7, så skal vi bare have tallene 0, 1, 2, 3, 4, 5, 6 i første række:
| 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 | 50 | 51 | 52 | 53 | 54 | 55 |
| 56 | 57 | 58 | 59 | 60 | 61 | 62 |
Når vi ser på kongruens modulo 5, så er \(10 \equiv 0\).
Når vi ser på kongruens modulo 7, så er \(10 \equiv 3\).
Hvis man både ser på kongruens modulo 5 og kongruens modulo 7,. så er det altså ikke klart om \(10 \equiv 0\) eller \(10 \equiv 3\). Derfor skriver man f.eks.
\(10 \equiv_5 0\)
og
\(10 \equiv_7 3\)
Man kan også skrive
\(10 \equiv 0 \textrm{ (mod 5)}\)
og
\(10 \equiv 3 \textrm{ (mod 7)}\)
Jeg vil holde mig til første skrivemåde, idet den anden med (mod 5) let bliver uoverskuelig når der står (mod 5) mange gange i samme linie.
Er det klart at vi f.eks. ser på kongruens modulo 5, så skrives bare \(\equiv\) uden 5’tallet for neden.