Heltal modulo n

[28.03.2020] [Nørderier/Teori]

• Intro
• Talteori
• Heltal modulo n

Lad n være et givet positivt heltal. Definer følgende relation: a .sim b .dlrarrow n .divides (b - a) hvilken er en ækv. relation:

• Refleksiv: a .sim a .drarrow n .divides (a - a) .drarrow n .divides 0.
• Symmetrisk: a .sim b .drarrow qn = (b - a) .drarrow -qn = (a - b) .drarrow b .sim a
• Transitiv:
  a .sim b .and b .sim c .drarrow nq_1 = (b - a) .and nq_2 = (c - b) .drarrow nq_1 + nq_2 = c - a .drarrow n(q_1 + q_2) = c - a .drarrow a .sim c

Vi skriver a ≡ b (mod n) "a er kongruent med b mod n", hvis a ∼ b. For et k ∈ ℤ skriver vi ækv. klasserne for a som a og kalder dem for restklasser af a mod n. Disse er mængden af alle tal hvis forskel til a er et multiplum af n:

overline a = {a + kn | k .isin setZ}

Der er præcist n forskellige restklasser mod n, nemlig:

overline 0, overline 1, overline 2, ... , overline{n - 1}

og disse restklasser deler ℤ i en klassedeling. Ækvivalensklasserne under denne klassedeling vil vi notere som setZ .setminus nsetZ og kalde de hele tal modulo n. Under setZ .setminus nsetZ kan vi definere multiplikation og addition:

overline a + overline b = overline{a + b}
og
overline a .sdot overline b = overline{a .sdot b}

For at regne et produkt af to repræsentanter af to restklasser ganger vi bare en repræsentat fra hver med hinanden. Og det kan være en hvilken som helst repræsentant. Det samme gælder så for summen af to repræsentanter. Resultatet bliver en ny repræsentant for en restklassen mod n. Eksempel:

Betrag overline 3, overline 5 .isin setZ .setminus 14setZ. Summen af de to giver: overline 3 + overline 5 = overline{3 + 5} = overline 8. Denne sum kan også skrive som: overline 17 + overline{- 37} = overline{-20} hvor overline 8 = {... ,-20, -6, 8, ...} mod 14. Læg mærke til at hver restklasse består af uendelig mange elementer, og da man frit kan vælge et vilkårligt element som repræsentant, er det tit en god idé at overveje hvilket element der er nemmest at regne med.

Index Del