Kongruens, anvendelser

I artikkelen om regneregler for kongruens ble vi kjent med hvordan vi kan gjøre beregninger med kongruenser. I denne artikkelen ser vi på hvordan vi kan bruke reglene til å begrunne delelighetsregler, kjapt finne feil i en addisjon eller multiplikasjon, sjekke om en EAN−13-kode eller et personnummer er gyldig, utvikle en metode for å finne ut hvilken ukedag en vilkårlig dato faller på, og finne rest ved divisjon av store tall,

Kongruens og delelighetsregler

I artikkelen om delelighet brukte vi regelen om lineære kombinasjoner til å utlede delelighetsregler. Nå skal vi ta en titt på delelighetsreglene en gang til, og se hvordan vi kan begrunne dem ved hjelp av regnereglene for kongruenser. Vi skal i tillegg introdusere elleveregelen, som sier at et tall er delelig på 11 hvis den alternerende tverrsummen er delelig på 11.

I artikkelen om tall og tallsystemer lærte vi å skrive tall på utvidet form som am10m + am−110m − 1 + … + a110 + a0.

Eksempel 1:

2657 skrives på utvidet form som 2 · 103+ 6 · 102 + 5 · 10 + 7.

Regler for å avgjøre om et tall, t, er delelig med et tall, n, går ut på å erstatte t med et tall vi på en enkel måte kan avgjøre om er delelig med n. Teknikken med å bruke kongruenser til dette går ut på å erstatte t med et mindre tall som er kongruent med t modulo n. Siden tallene er kongruente, vil divisjon med n gi samme rest, og hvis denne resten er 0, er begge tallene delelige med n.

I de fleste tilfellene går teknikken ut på å skrive tallet n på utvidet form og erstatte 10 med et annet tall som er kongruent med 10 modulo n. Som vi har lært, vil da også potenser av dette tallet være kongruente med potenser av 10 modulo n.

Eksempler på bruk av reglene finnes i artikkelen om delelighet.

Toerregelen

$\fbox{Tall er delelige med 2 når siste siffer er delelig med 2}$

Denne regelen begrunner vi slik:

Siden 10 ≡ 0 (mod 2), kan vi bytte ut alle forekomster av 10 med 0 når vi regner modulo 2:

nam10m + am−110m−1 + … + a0am0m + am−10m−1 + … + a0 ≡ 0 + 0 + … + a0a0 (mod 2)

Et tall er altså kongruent med sitt siste siffer modulo 2. Hvis vi får rest 0 når vi dividerer siste siffer med 2, får vi også rest 0 hvis vi dividerer hele tallet med 2.

Femmerregelen

$\fbox{Tall er delelige med 5 når siste siffer er delelig med 5}$

Teknikken er akkurat samme som for toerregelen, bare at vi regner modulo 5 i stedet for modulo 2:

Siden 10 ≡ 0 (mod 5), kan vi bytte ut alle forekomster av 10 med 0 når vi regner modulo 5:

nam10m + am−110m−1 + … + a0am0m + am−10m−1 + … + a0 ≡ 0 + 0 + … + a0a0 (mod 5)

Et tall er altså kongruent med sitt siste siffer modulo 5. Hvis vi får rest 0 når vi dividerer siste siffer med 5, får vi også rest 0 hvis vi dividerer hele tallet med 5.

Firerregelen

$\fbox{Tall er delelige med 4 når tallet dannet av de to siste sifrene i tallet er delelig med 4}$

For å vise denne regelen kan vi ikke erstatte 10 med 0 fordi 10 ≢ 0 (mod 4), 10 er ikke delelig med 4. Derimot kan vi benytte at 100 ≡ 0 (mod 4), 100 er delelig med 4. Vi kan bytte ut alle forekomster av 100 med 0 når vi regner modulo 4:

nam100m + am−1100m−1 + … + a110 + a0am0m + am−10m−1 + … + a110 + a0 ≡ 0 + 0 + … + a110 + a0a110 + a0 (mod 4)

Et tall er altså kongruent med tallet dannet av de siste to sifrene modulo 4. Hvis vi får rest 0 når vi dividerer tallet dannet av de siste to sifrene med 4, får vi også rest 0 hvis vi dividerer hele tallet med 4.

Treerregelen

$\fbox{Tall er delelige med 3 når tverrsummen er delelig med 3}$

For å vise denne regelen erstatter vi alle potenser av 10 med potenser av 1. Det kan vi gjøre fordi 10 ≡ 1 (mod 3).

nam10m + am−110m−1 + … + a0am1m + am−11m−1 + … + a0am + am−1 + … + a0 (mod 3)

Et tall er altså kongruent med summen av sine sifre modulo 3. Hvis vi får rest 0 når vi dividerer summen av sifrene med 3, får vi også rest 0 hvis vi dividerer hele tallet med 3. Denne siffersummen er det vi kaller tverrsummen, som vi ble kjent med i artikkelen om tall og tallsystemer.

Nierregelen

$\fbox{Tall er delelige med 9 når tverrsummen er delelig med 9}$

Begrunnelsen er akkurat samme som for treerregelen, fordi 10 ≡ 1 (mod 9):

nam10m + am−110m−1 + … + a0am1m + am−11m−1 + … + a0am + am−1 + … + a0 (mod 9)

Et tall er altså kongruent med summen av sine sifre modulo 9. Hvis vi får rest 0 når vi dividerer summen av sifrene med 9, får vi også rest 0 hvis vi dividerer hele tallet med 9.

Så presenterer vi en regel som er vanskelig å begrunne uten bruk av kongruensregning:

Elleveregelen

$\fbox{Tall er delelige med 11 når den alternerende tverrsummen er delelig med 11}$

Her baserer vi oss på at 10 ≡ −1 (mod 11) og erstatter alle potenser av 10 med potenser av −1:

nam10m + am−110m−1 + … + a0am(−1)m + am−1(−1)m−1 + … + a0 (mod 11)

Her vil −1 gi et fortegnsskifte hvis vi opphøyer i et oddetall, men ikke noe fortegnsskifte hvis vi opphøyer i et partall. Det vil si at a1, a3, og så videre vil få fortegnsskifte, men ikke a0, a2, og så videre. Vi har altså at

n ≡ a0a1 + a2a3 + … + (−1)mam (mod 11)

Denne summen av sifre med vekslende fortegn er den alternerende tverrsummen, som vi ble kjent med i artikkelen om tall og tallsystemer.

Eksempel 2:

132 er delelig med 11 fordi A(132) = 2 − 3 + 1 = 0 er delelig med 11.

116 er ikke delelig med 11 fordi A(116) = 6 − 1 + 1 = 6 ikke er delelig med 11.

81048 er delelig med 11 fordi A(81048) = 8 − 4 + 0 − 1 + 8 = 11 er delelig med 11.

Når det gjelder treer- og nierregelen kan vi ta tverrsummen på nytt hvis vi ender opp med et stort tall. Det kan vi ikke med den alternerende tverrsummen, men vi kan finne kongruente tall ved å subtrahere eller addere 11 gjentatte ganger. Men siden vi vekselvis adderer og subtraherer sifre, ender vi imidlertid sjelden opp med særlig store tall.

Oppgave 1:

Avgjør om 924 er delelig med 2, 3, 4, 5, 9 og 11 ved å bruke delelighetsregler. Gjør testene i den rekkefølgen du ønsker.

Skjermfilm
Se film der løsningsforslaget vises

Kontrollere regnestykker

Nierprøven

Adderer vi tverrsummene til to tall, blir svaret kongruent med tverrsummen til summen av tallene modulo 9:

$\fbox{$T(a) + T(b) \equiv T(a + b) \, (mod \; 9)$}$

Det er lett å innse at dette er riktig, for som vi så da vi studerte delelighetsreglene, er et talls tverrsum kongruent med tallet selv modulo 9, T(a) ≡ a (mod 9) og T(b) ≡ b (mod 9). Da må T(a) + T(b) ≡ a + b (mod 9), ifølge regelen for å addere på begge sider av en kongruensrelasjon, som vi har lært tidligere. Og igjen, et tall er kongruent med sin egen tverrsum modulo 9, a + b ≡ T(a + b) (mod 9).

Dette utnytter vi i den såkalte nierprøven: Hvis vi adderer to tall og tverrsummen til svaret ikke er kongruent med summen av addendenes tverrsum modulo 9, er ikke addisjonen korrekt.

Eksempel 3:

Vi skal bruke nierprøven til å kontrollere utregningen 2556 + 845 = 3411.

Vi får T(a) = T(2556) = 18, T(b) = T(845) = 17, så T(a) + T(b) = 35. Tar vi tverrsummen en gang til, får vi T(35) = 8.

T(svar) = T(3411) = 9.

Siden 8 og 9 ikke er kongruente modulo 9, er ikke utregningen riktig. Riktig svar er 3401, med tverrsum T(3401) = 8.

Nierprøven fanger imidlertid ikke opp feil som er multipler av 9, så vi kan ikke konkludere med at en addisjon er riktig fordi om nierprøven ikke påviser feil. Hadde vi for eksempel fått det gale svaret 3410 i eksempel 3, ville vi ikke funnet feilen fordi T(3410) = 8.

Eksempel 4:

Vi skal bruke nierprøven til å kontrollere utregningen: 1342 + 786 = 2164.

Vi får T(a) = T(1342) = 10. T(b) = T(786) = 21, så T(a) + T(b) = 31. Tar vi tverrsummen en gang til, får vi T(31) = 4.

T(svar) = T(2164) = 13. Tar vi tverrsummen en gang til, får vi T(13) = 4.

Siden 4 og 4 er kongruente modulo 9, har vi ikke påvist feil. Men utregningen er allikevel feil, riktig utregning er 1342 + 786 = 2128. Men vi oppdager ikke feilen fordi den er en multippel av 9, 2164 − 2128 = 45.

Nierprøven virker også på multiplikasjon. Multipliserer vi tverrsummene til to tall, blir svaret kongruent med tverrsummen til produktet av tallene modulo 9:

$\fbox{$T(a) \cdot T(b) \equiv T(a \cdot b) \, (mod \; 9)$}$

Vi kunne laget en treerprøve som virket etter samme prinsipp, men den ville ikke fange opp feil som nierprøven ikke fanger opp, og ville feile for alle multipler av 3, så nierprøven er et bedre valg.

Elleveprøven

Adderer vi de alternerende tverrsummene til to tall, blir svaret kongruent med den alternerende tverrsummen til summen av tallene modulo 11:

$\fbox{$A(a) + A(b) \equiv A(a + b) \, (mod \; 11)$}$

Dette utnytter vi i den såkalte elleveprøven: Hvis vi adderer to tall og den alternerende tverrsummen til svaret ikke er kongruent med summen av addendenes alternerende tverrsum modulo 11, er ikke addisjonen korrekt.

Eksempel 5:

Vi skal bruke elleveprøven til å kontrollere utregningen: 1342 + 786 = 2164.

Vi får A(a) = A(1342) = 2 − 4 + 3 − 1 = 0. A(b) = A(786) = 6 − 8 + 7 = 5, så A(a) + A(b) = 5.

A(svar) = A(2164) = 4 − 6 + 1 − 2 = −3. Vi adderer 11 en gang og får 8.

Siden 5 og 8 ikke er kongruente modulo 11, er ikke utregningen riktig. Riktig svar er 2128.

​Eksempel 4 og 5 besto av nøyaktig samme, uriktige regnestykke. Men nierprøven sviktet fordi svaret var 45 for høyt, og 45 er en multippel av 9. Men 45 er ikke en multippel av 11, derfor fungerte elleveprøven.

Gjennomsnittlig vil nierprøven feile i hvert niende tilfelle og elleveprøven feile i hvert ellevte tilfelle. Men begge prøvene vil bare feile hvis feilen både er en multippel av både 9 og 11, hvert 99. tilfelle. Det er derfor bare ca. 1 % sannsynlighet for at begge prøvene feiler.

Elleveprøven virker også på multiplikasjon. Multipliserer vi de alternerende tverrsummene til to tall, blir svaret kongruent med den alternerende tverrsummen til produktet av tallene modulo 11:

$\fbox{$A(a) \cdot A(b) \equiv A(a \cdot b) \, (mod \; 11)$}$

Oppgave 2:

Bruk nierprøven og/eller elleveprøven til å kontrollere utregningen 757 · 987 = 747249.

Skjermfilm
Se film der løsningsforslaget vises

Oppgave 3:

Bruk nierprøven og/eller elleveprøven til å kontrollere utregningene under. (Legg merke til at faktorene er de samme i alle oppgavene, så resultater fra en deloppgave kan brukes i en annen):

      1. 1234 · 364 = 224588
         
      2. 1234 · 364 = 449194
         
      3. 1234 · 364 = 449176

​Se løsningsforslag

Oppgave 4:

Hva betyr følgende for resultatet av en multiplikasjon?

      1. Både nierprøven og elleveprøven påviser feil.
         
      2. Enten nierprøven eller elleveprøven påviser feil.
         
      3. Verken nierprøven eller elleveprøven påviser feil.

​Se løsningsforslag

Kontrollsiffer

Strekkoder, som vi i dag finner på nesten alt mulig i butikken, brukes til å identifisere en vare. For å verifisere at koden blir riktig avlest, inneholder den et kontrollsiffer som er laget slik at en vektet sum av sifrene i strekkoden blir 0 modulo 10. Vektinga gjøres slik at sifrene annet hvert multipliseres med 1 og 3, for å avsløre om to etterfølgende siffer byttes om. Uten vekting ville jo tverrsummen uansett blitt den samme.

En mye brukt strekkode er EAN-13, som består av 13 siffer, hvorav det siste er kontrollsifferet.

Et eksempel på en EAN-13-kode er sifrene 9-7-8-8-2-0-2-4-2-0-9-8-7, der kontrollsifferet er 7. Koden og vektene satt opp i en tabell ser slik ut:

Strekkode 9 7 8 8 2 0 2 4 2 0 9 8 7
Vekt 1 3 1 3 1 3 1 3 1 3 1 3 1
Vektet kode 9 21 8 24 2 0 2 12 2 0 9 24 7

Vi ser at summen av de vektede kodene blir 9 + 21 + 8 + 24 + 2 + 0 + 2 + 12 + 2 + 0 + 9 + 24 + 7 = 120. Siden 120 ≡ 0 (mod 10), er dette en gyldig EAN-13-kode.

Oppgave 5:

Avgjør om 7-6-1-3-0-3-5-8-3-0-5-9-0 er en gyldig EAN-13-kode.

​Se løsningsforslag

Et annet eksempel på bruk av kontrollsifre finner vi i personnummer. Et personnummer er elleve siffer langt og består av fødselsdato (d1d2), -måned (m1m2) og -år (å1å2), etterfulgt av et tresifret løpenummer (n1n2n3), der n3 er oddetall for menn, og partall for kvinner. Til slutt kommer to kontrollsifre (k1k2).

Kontrollsifrene er slik at en vektet tverrsum skal være kongruent med 0 modulo 11 både ved bruk av det ene og det andre sifferet. I noen tilfeller vil et kontrollsiffer måtte være 10 for at tverrsummen skal bli riktig, men da blir personnummeret 12 siffer langt, og må forkastes.

Til å beregne kontrollsifferet i en EAN-kode ble det brukt en vekting som besto av 1 og 3 annet hvert. Tilsvarende for personnummer er mer komplisert, 3-7-6-1-8-9-4-5-1-0 for første kontrollsiffer og 5-4-3-2-7-6-5-4-3-2-1 for andre. Vi kan sette det opp i en tabell slik:

Personnummer d1 d2 m1 m2 å1 å2 n1 n2 n3 k1 k2
Vekt ved k1 3 7 6 1 8 9 4 5 2 1 0
Vekt ved k2 5 4 3 2 7 6 5 4 3 2 1

Hvis for eksempel Harry Potter oppgir at fødselsnummeret hans er 31078012334, kontrollerer vi først gyldigheten ved å se på første kontrollsiffer:

Personnummer 3 1 0 7 8 0 1 2 3 3 4
Vekt ved k1 3 7 6 1 8 9 4 5 2 1 0
Vektet personnummer 9 7 0 7 64 0 4 10 6 3 0

Og den vektede summen blir 9 + 7 + 0 + 7 + 64 + 0 + 4 + 10 + 6 + 3 + 0 ≡ 110 ≡ 0 (mod 11).

Så ser vi på andre kontrollsiffer:

Personnummer 3 1 0 7 8 0 1 2 3 3 4
Vekt ved k2 5 4 3 2 7 6 5 4 3 2 1
Vektet personnummer 15 4 0 14 56 0 5 8 9 6 4

Og den vektede summen blir 15 + 4 + 0 + 14 + 56 + 0 + 5 + 8 + 9 + 6 + 4 ≡ 121 ≡ 0 (mod 11).

Personnummeret er derved gyldig.

Navn og personnummer aksepteres i mange tilfeller som bevis på en persons identitet. Men personnummer kan lett kommer på avveie, for eksempel ved at uvedkommende leser det på et førerkort eller bankkort.

Det fantes en periode en side på Internett der en kunne registrere seg som bruker å oppgi navn og personnummer. Siden sjekket så navn og personnummer mot folkeregisteret og avviste registreringen hvis noe var feil. Hvis vi kjente en persons navn og fødselsdato, kunne vi da prøve oss fram til vi ble akseptert, og på den måten finne ut av personnummeret.

For en gitt fødselsdato finnes det nemlig ikke så veldig mange mulige personnumre.

La oss si at vi på Facebook ser at Harry Potter fylte 38 år 31. juli 2018. Da kjenner vi de 6 første sifrene i personnummeret, 310780. Løpenummeret må vi gjette på. Det finnes i utgangspunktet 1000 muligheter, men ved å google litt, finner vi ut at på det tidspunktet ble det bare tildelt sifre mellom 000 og 499. Siden Harry Potter er mann, må det tredje sifferet være oddetall. Og 17 % av løpenumrene må forkastes fordi de resulterer i at et kontrollsiffer blir 10. Det gjenstår da bare ca. 207 muligheter, og statistisk vil vi i gjennomsnitt få treff etter om lag 100 forsøk.

Oppgave 6:

Avgjør om 21023712345 er et gyldig personnummer.

​Se løsningsforslag

Ukedagsformelen

Ukedagene er et glimrende eksempel på kongruensregning, der vi regner modulo 7. Nå skal vi utlede en formel, en evighetskalender for å finne hvilken ukedag en vilkårlig dato faller på.

Vi starter med å nummerere dagene fra 1 til 7, der 1 er ukens første dag, mandag. 

Hvis året hadde 364 dager, ville en gitt dato falle på samme ukedag hvert år fordi 364 ≡ 0 (mod 7). Når 1. mars år 2000 var onsdag, altså dag 3, ville 1. mars 2001 blitt dag 3 + 364 ≡ 3 + 0 ≡ 3 (mod 7), også en onsdag.

Men lengden på året bestemmes ut fra hvor lang tid Jorda bruker på å gå rundt Sola, og de fleste årene har 365 dager. Når 1. mars 2000 var dag 3, blir 1. mars 2001 dag 3 + 365 ≡ 3 + 1 ≡ 4 (mod 7), altså en torsdag.

Vi øker altså dagnummeret med 365 ≡ 1 (mod 7) for hvert år etter år 2000. 

Vil vi lage en formel for å finne ukedagen til 1. mars et vilkårlig år, tar vi utgangspunkt i at 1. mars 2000 var dag nummer 3, og adderer antall år etter 2000 modulo 7.

u ≡ 3 + y − 2000 (mod 7), der y er året der vi vil finne dagnummeret til 1. mars. 

Eksempel 7:

1. mars 2002 blir u ≡ 3 + 2002 − 2000 ≡ 5 (mod 7), en fredag.

1. mars 2003 blir u ≡ 3 + 2003 − 2000 ≡ 6 (mod 7), en lørdag.

Men Jorda bruker ikke nøyaktig 365 dager på turen rundt Sola, men om lag en kvart dag mer. For at året skal bli et helt antall dager, lar en 3 år bestå av 365 dager og 1 år – skuddåret, består av 366 dager. Et skuddår forskyver dagnummeret med 366 ≡ 2 (mod 7) dager. Vi må justere formelen for å ta høyde for den ekstra dagen.

Skuddår er år med årstall som er delelige med 4, så 2000, 2004, 2008, etc. var skuddår. Vi finner derved antall skuddår etter år 2000 ved å telle antall hele fireårsperioder etter år 2000. Det blir $\lfloor \frac{\displaystyle y − 2000}{\displaystyle 4} \rfloor$.

For hvert skuddår må vi addere 1 ekstra til dagnummeret, så formelen blir 

$u \equiv 3 + y − 2000 + \lfloor \frac{\displaystyle y − 2000}{\displaystyle 4} \rfloor \, (mod \; 7)$

Formelen er nå korrekt innenfor et ganske stort tidsspenn.

Eksempel 8:

Vi kan beregne at 1. mars 2065 vil falle på en søndag:
$u \equiv 3 + 2065 − 2000 + \lfloor \frac{\displaystyle 2065 − 2000}{\displaystyle 4} \rfloor \equiv 3 + 2065 − 2000 + 16 \equiv 84 \equiv 0 \, (mod \; 7)$.

Logikken er den samme for år før år 2000, så vi kan regne ut at Harry Belafonte (1/3-1927) ble født på en tirsdag:
$u \equiv 3 + 1927 − 2000 + \lfloor \frac{\displaystyle 1927 − 2000}{\displaystyle 4} \rfloor \, \equiv 3 + 1927 − 2000 − 19 \equiv −89 \equiv 2 (mod \; 7)$.

Men Jorda bruker ikke nøyaktig 365 og en kvart dag på runden rundt Sola, men litt mindre. For å kompensere for dette sløyfes skuddårsdagen i hele hundreår som ikke er delelige med 4. Det vil si at år 1700, 1800 og 1900 ikke var skuddår, mens år 2000 var skuddår. For de tre første hele hundreårene i en periode på 400 år tas det altså bort en skuddårsdag, men ikke for det fjerde.

Nå skal vi se hvordan vi kan implementere denne mekanismen matematisk. Tabellen under viser verdien til $\frac{\displaystyle 3n}{\displaystyle 4}$ og $\lceil \frac{\displaystyle 3n}{\displaystyle 4} \rceil$ for n = 0, 1, … , 9.

n 0 1 2 3 4 5 6 7 8 9
$\frac{\displaystyle 3n}{\displaystyle 4}$ 0 0,75 1,5 2,25 3 3,75 4,5 5,25 6 6,75
$\big \lceil \frac{\displaystyle 3n}{\displaystyle 4}\big \rceil$ 0 1 2 3 3 4 5 6 6 7

 

Vi ser at $\lceil \frac{\displaystyle 3n}{\displaystyle 4} \rceil$ øker tre ganger i trinn på 1, men ikke øker i det fjerde trinnet. Og dette er akkurat det vi trenger for å kompensere for de utelatte skuddårene. Lar vi h betegne antall hele hundreår i årstallet, trekker vi fra $\lceil \frac{\displaystyle 3(h − 20)}{\displaystyle 4} \rceil$.

Nå har vi en komplett formel for å regne ut hvilken ukedag 1. mars faller på i et vilkårlig år:

$u \equiv 3 + y − 2000 + \lfloor \frac{\displaystyle y − 2000}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3(h − 20)}{\displaystyle 4} \rceil \, (mod \; 7)$

Nå er det jo litt tungvint å regne i forhold til år 2000. Regnet vi i forhold til år 0, ville vi slippe å trekke fra 2000 hele veien. Grunnen til at vi startet på år 2000, er at det er praktisk å regne med datoer vi lett kan sjekke på kalenderen. Bruker vi formelen til å regne oss tilbake til år 0, ser vi imidlertid at 1. mars år 0 også ville falt på en onsdag og hatt dagnummer 3. I forhold til skuddår, er år 0 også delelig på 4 og på 400. År 0 har altså samme egenskaper som år 2000, så vi kan bytte ut 2000 med 0 i formelen:

$u \equiv 3 + y − 0 + \lfloor \frac{\displaystyle y − 0}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3(h − 0)}{\displaystyle 4} \rceil \, (mod \; 7)$.

Å trekke fra 0 kan vi selvfølgelig droppe, så vi får:

$u \equiv 3 + y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil \, (mod \; 7)$, der y er årstallet og h antall hundreår i årstallet, altså $\lfloor \frac{\displaystyle y}{\displaystyle 100} \rfloor$.

Eksempel 9:

Vi skal regne ut hvilken ukedag 1. mars 3165 faller på. Vi får

$u \equiv 3 + 3165 + \lfloor \frac{\displaystyle 3165}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3\cdot 31}{\displaystyle 4} \rceil \equiv 3 + 3165 + 791 − 24 \equiv 3935 \equiv 1 \, (mod \; 7)$

En mandag

Nå er det selvfølgelig ikke særlig tilfredsstillende å bare kunne regne ut hvilken ukedag 1. mars faller på. Men tar vi utgangspunkt i 1. mars, finner vi også greit ut hvilken ukedag andre datoer faller på ved å beregne hvor stor forskyvningen er i hver måned. Grunnen til at vi har valgt akkurat 1. mars som utgangspunkt er ikke tilfeldig. Dette er første dag etter en eventuell skuddårsdag. Med første mars som utgangspunkt, vil en eventuell skuddårsdag alltid falle i slutten av en periode, og beregningene blir mye enklere. Vi later derfor som om mars er årets første måned.

Tabellen under viser hvor stor forskyvningen av ukedagene er pr. måned, og hvor stor den akkumulerte forskyvingen er totalt den første i hver måned, målt fra første mars. Forskyvningen finnes ved å beregne antall dager i måneden modulo 7. For eksempel 31 ≡ 3 (mod 7) for måneder med 31 dager. Den variable lengden på februar påvirker ikke den akkumulerte forskyvningen siden den ligger sist i perioden.

En morsom digresjon er at i den romerske kalenderen begynte året også 1. mars, slik at september, oktober, november og desember var måned nummer 7, 8, 9 og 10, slik som i tabellen under. Det forklarer at månedsnavnene er avledet av de latinske ordene for 7, 8, 9 og 10, septem, octo, novem og decem.

Nummer Måned Forskyvning Akkumulert forskyvning
1 mars 3 0
2 april 2 3
3 mai 3 5
4 juni 2 8
5 juli 3 10
6 august 3 13
7 september 2 16
8 oktober 3 18
9 november 2 21
10 desember 3 23
11 januar 3 26
12 februar 0 (1) 29

 

Vi kan altså finne ukedagen den første i hver måned ved å bruke ukedagsformelen for å finne ukedagen 1. mars falt på, og så legge til månedsforskyvningen.

Eksempel 10:

Vi har tidligere funnet ut at første mars år 2000 var en onsdag, med dagnummer 3. Da blir dagnummeret til 1. oktober samme år 3 + 18 ≡ 0 (mod 7). Altså var 1. oktober år 2000 en søndag.

Litt klønete er det jo med denne tabellen, det ville vært mer elegant hvis vi kunne beregnet forskyvningen ved hjelp av en formel. Og faktisk viser det seg at $\lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor − 2$, der m er månedsnummeret regnet fra mars, er lik den akkumulerte forskyvningen. Så nå kan vi utvide ukedagsformelen til å beregne hvilken dag den 1. i hver måned faller på, når vi husker at januar og februar regnes som måned 11 og 12 året før:

$u \equiv 3 + y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor − 2 \, (mod \; 7)$.

Eksempel 11:

Vi skal finne ut hvilken dato 1. juni 2013 falt på. Juni er måned 4, når vi regner fra mars. Vi får

$u \equiv 3 + 2013 + \lfloor \frac{\displaystyle 2013}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3 \cdot 20}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 4 − 1}{\displaystyle 5} \rfloor − 2 \equiv$

$3 +2013 + 503 − 15 + 10 − 2 \equiv 6\, (mod \; 7)$

En lørdag.

Vi skal finne ut hvilken dato 1. februar 1966 falt på. Februar 1966 er måned 12 i 1965, når vi regner fra mars. Vi får

$u \equiv 3 + 1965 + \lfloor \frac{\displaystyle 1965}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3 \cdot 19}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 12 − 1}{\displaystyle 5} \rfloor − 2 \equiv $

$3 + 1965 + 491 − 15 + 31 − 2 \equiv 2473 \equiv 2\, (mod \; 7)$

En tirsdag.

Så gjenstår det bare å utvide formelen til å gjelde en vilkårlig dato, ikke bare den 1. hver måned. Dette er enkelt, for hvis datoen er d, legger vi til d − 1, det vil si antall dager datoen kommer etter den 1. Så ukedagsformelen blir

$u \equiv 3 + y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor − 2 + d − 1 \, (mod \; 7)$

Vi ser at 3 − 2 − 1 = 0, så disse leddene kan strykes, og vi får ukedagsformelen i sin endelige form:

$\fbox{$u \equiv y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor + d \, (mod \; 7)$}$

Her er y årstallet, h antall hundreår i årstallet, m månedsnummeret regnet fra mars, og d dagnummeret.

Dette nettstedet har en app som finner ukedager ved hjelp av ukedagsformelen. Hvis du der huker av for «Vis utregning», lister appen opp detaljene i utregningen.

Eksempel 12:

Vi skal finne ut hvilken ukedag månelandingen 20. juli 1969 fant sted på. Juli er måned 5, når vi regner fra mars. Vi får

$u \equiv 1969 + \lfloor \frac{\displaystyle 1969}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3 \cdot 19}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 5 − 1}{\displaystyle 5} \rfloor + 20 \equiv $

$1969 + 492 − 15 + 12 + 20 \equiv 2478 \equiv 0 \, (mod \; 7)$

En søndag.

​Oppgave 7:

Bruk ukedagsformelen til å finne ut hvilken ukedag følgende begivenheter fant sted.

      1. Angrepet på tvillingtårnene i New York den 11. september 2001.
         
      2. Wolfgang Amadeus Mozarts fødsel den 27. januar 1756.

Se løsningsforslag

Fordi vår tidsregning hopper over år 0, gir ukedagsformelen ikke riktige svar for årstall tidligere enn år 1.

Rest ved divisjon av store tall

Som vi skal se i artikkelen om kryptografi, vil vi kunne ha behov for å finne resten vi får når to store tall divideres på hverandre. Så lenge tallene ikke er for store, kan vi enkelt gjøre slike beregninger direkte med en datamaskin eller kalkulator, for eksempel ved kommandoen rest i Excel eller mod i GeoGebra. Men tall som er så store at de har noen nytte i kryptografi, klarer ikke disse verktøyene å håndtere direkte. Vi må da gjøre tallene om til mindre, kongruente tall, som vi kan bruke i vanlige beregninger.

I eksempel 9 i artikkelen om regneregler for kongruens viste vi at 2916 ≡ 4 (mod 19) ved å benytte at potensen 2916 kunne skrives som $(29)^{\large 2^{\Large 2^{\Large 2^{\Large 2}}}}$ og så bruke potensregelen til å finne tall kongruente med 29, 292, etc.

I eksemplet ser det ut som vi hadde flaks, siden 16 er en potens av 2. Men faktum er at alle tall kan skrives som en sum av toerpotenser, og derved kan denne metoden utvides til å fungere på alle tall.

De første toerpotensene er 20 = 1, 21 = 2; 22 = 4, 23 = 8; 24 = 16; 25 = 32; 26 = 64; 27 = 128; 28 = 256; 29 = 512; 210 = 1024; 211 = 2048; 212 = 4096; 213 = 8192.

For å finne toerpotensene et tall er sammensatt av, trekker vi suksessivt fra den største toerpotensen vi kan.

Eksempel 13:

Vi skal skrive 605 som en sum av toerpotenser.

Den største potensen vi kan trekke fra er 512:
605 − 512 = 93.

Nå er den største potensen vi kan trekke fra 64:
93 − 64 = 29.

Nå er den største potensen vi kan trekke fra 16:
29 − 16 = 13.

Nå er den største potensen vi kan trekke fra 8:
13 − 8 = 5.

Nå er den største potensen vi kan trekke fra 4:
5 − 4 = 1.

Nå er den største potensen vi kan trekke fra 1:
1 − 1 = 0.

Så 605 = 1 + 4 + 8 + 16 + 64 + 512.

I det følgende bruker vi regneeksempler der tallene ikke er større enn at vi kan kontrollere svaret i et regneark eller GeoGebra.

Eksempel 14:

Vi skal finne resten vi får når vi dividerer 715 med 13.

Vi skriver først 15 som en sum av toerpotenser: 15 = 1 + 2 + 4 + 8, så

715 = 71+2+4+8 = 7 · 72 · 74 · 78.

Så erstatter vi suksessivt de enkelte faktorene med mindre, kongruente tall. (Utregningene underveis gjør vi med Excel eller GeoGebra.)

Faktoren 7 kan ikke bli mindre, men for 72 får vi

72 ≡ 49 ≡ 10 (mod 13)

74 skriver vi først som (72)2. Siden vi har funnet ut at 72 ≡ 10 (mod 13), gir potensregelen at

74 ≡ (72)2 ≡ 102 ≡ 100 ≡ 9 (mod 13)

Så skriver vi 78 som (74)2. Siden vi har funnet ut at 74 ≡ 9 (mod 13), gir potensregelen at

78 ≡ (74)2 ≡ 92 ≡ 81 ≡ 3 (mod 13)

Så vi har 715 ≡ 7 · 72 · 74 · 78 ≡ 7 · 10 · 9 · 3 ≡ 1890 ≡ 5 (mod 13).

Resten blir 5. Dette kan vi kontrollere ved å skrive =rest(7^15;13) i et regneark eller mod(7^15,13) i GeoGebra.

Dette nettstedet har en app som finner rest ved divisjon av store tall. Hvis du der huker av for «Vis utregning», lister appen opp trinnene i beregningen, det kan være veldig instruktivt.

Vil vi holde tallene så små som mulig i utregningen, kan det imidlertid av og til lønne seg å velge negative tall i en kongruens.

Eksempel 15:

Vi gjør om igjen noen av utregningene i eksempel 14, men nå med negative tall der det forenkler utregningen:

72 ≡ 49 ≡ −3 (mod 13)

74 ≡ (72)2 ≡ (−3)2 ≡ 9 ≡ −4 (mod 13)

78 ≡ (74)2 ≡ (−4)2 ≡ 16 ≡ 3 (mod 13)

Så vi har 715 ≡ 7 · 72 · 74 · 78 ≡ 7 · (−3) · (−4) · 3 ≡ 252 ≡ 5 (mod 13).

Oppgave 8:

Bruk metoden med toerpotenser til å beregne resten du får når du dividerer 613 med 11. Kontroller svaret i et regneark eller GeoGebra, eller med appen som finner rest.

Se løsningsforslag

Kilder

    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.
    • Rinvold, A. R. (2009). Visuelle perspektiv. Tallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Petersen V.B., Tvete K.S., (2013). I tallkongruensenes verden. Caspar forlag.