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,

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 $a_m10^m + a_{m – 1}10^{m – 1} + \dots + a_110 + a_0$.

Eksempel 1:

$2657$ skrives på utvidet form som $2 \cdot 10^3+ 6 \cdot 10^2 + 5 \cdot 10 + 7$.

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

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 $t$. Som vi har lært, vil da også potenser av dette tallet være kongruente med potenser av $10$ modulo $t$.

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

Toerregelen

$\fbox{Alle tall der siste siffer er delelig med 2, er delelige med 2}$

Denne regelen begrunner vi slik:

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

$n = a_m10^m + a_{m – 1}10^{m – 1} + \dots + a_110 + a_0 \equiv \\
a_m0^m + a_{m – 1}0^{m – 1} + \dots + a_10 + a_0 \equiv a_0 \, (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{Alle tall der siste siffer er delelig med 5, er delelige med 5}$

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

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

$n = a_m10^m + a_{m – 1}10^{m – 1} + \dots + a_110 + a_0 \equiv \\
a_m0^m + a_{m – 1}0^{m – 1} + \dots + a_10 + a_0 \equiv a_0 \, (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{Alle tall der tallet dannet av de to siste sifrene er delelig med 4, er delelige med 4}$

For å vise denne regelen kan vi ikke erstatte $10$ med $0$ fordi $10 \not \equiv 0 \, (mod \; 4)$, $10$ er ikke delelig med $4$. Derimot kan vi benytte at $100 \equiv 0 \, (mod \; 4)$, $100$ er delelig med $4$. Vi setter $100$ utenfor parentes og erstatter $100$ med $0$ når vi regner modulo $4$:

$n = (a_m10^{m – 2} + a_{m – 1}10^{m – 3} + \dots + a_2)100+ a_110 + a_0 \equiv \\
(a_m10^{m – 2} + a_{m – 1}10^{m – 3} + \dots + a_2)0+ a_110 + a_0 \equiv a_110 + a_0 \, (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{Alle tall der tverrsummen er delelig med 3, er delelige med 3}$

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

$n = a_m10^m + a_{m – 1}10^{m – 1} + \dots + a_110 + a_0 \equiv \\
a_m1^m + a_{m – 1}1^{m – 1} + \dots + a_11 + a_0 \equiv a_m + a_{m – 1} + \dots + a_1 + a_0 \, (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{Alle tall der tverrsummen er delelig med 9, er delelige med 9}$

Begrunnelsen er akkurat samme som for treerregelen, fordi $10 \equiv 1 \, (mod \; 9)$:

$n = a_m10^m + a_{m – 1}10^{m – 1} + \dots + a_110 + a_0 \equiv \\
a_m1^m + a_{m – 1}1^{m – 1} + \dots + a_11 + a_0 \equiv a_m + a_{m – 1} + \dots + a_1 + a_0 \, (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å til en regel som er vanskelig å begrunne uten bruk av kongruensregning:

Elleveregelen

$\fbox{Alle tall der den alternerende tverrsummen er delelig med 11, er delelige med 11}$

Her baserer vi oss på at $10 \equiv -1 \, (mod \; 11)$ og erstatter alle potenser av $10$ med potenser av $-1$:

$n = a_m10^m + a_{m – 1}10^{m – 1} + \dots + a_110 + a_0 \equiv \\
a_m(-1)^m + a_{m – 1}(-1)^{m – 1} + \dots + a_1(-1) + a_0 \, (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 $a_1, a_3, \dots$ vil få fortegnsskifte, men ikke $a_0, a_2, \dots$. Vi har altså at

$n \equiv a_0 – a_1 + a_2 – a_3 + \dots + (-1)^ma_m \, (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.

Screencast
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) \equiv a (mod \; 9)$ og $T(b) \equiv b (mod \; 9)$. Da må $T(a) + T(b) \equiv 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 \equiv 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 et 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 et multippel av $9$. Men $45$ er ikke et 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 et 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 \cdot 987 = 747249$.

Screencast
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 \cdot 364 = 224588$
     
  2. $1234 \cdot 364 = 449194$
     
  3. $1234 \cdot 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 den vektede summen 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 \equiv 0 \; (mod \; 10)$, er dette en gyldig EAN-13-kode.

Et annet eksempel på bruk av kontrollsifre finner vi i personnummer. Et personnummer er elleve siffer langt og består av fødselsdato $(d_1d_2)$, -måned $(m_1m_2)$ og -år $(å_1å_2)$, etterfulgt av et tresifret løpenummer $(n_1n_2n_3)$, der $n_3$ er oddetall for menn, og partall for kvinner. Til slutt kommer to kontrollsifre $(k_1k_2)$.

Kontrollsifrene er slik at den vektede tverrsummen 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.

De enkelte vektene er slik:

Personnummer $d_1$ $d_2$ $m_1$ $m_2$ $å_1$ $å_2$ $n_1$ $n_2$ $n_3$ $k_1$ $k_2$
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 \equiv 110 \equiv 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 \equiv 121 \equiv 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 36 år 31. juli 2016. 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 omlag 100 forsøk.

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 \equiv 0 \, (mod \; 7)$. Når 1. mars år 2000 var onsdag, altså dag $3$, ville 1. mars 2001 blitt dag $3 + 364 \equiv 3 + 0 \equiv 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 \equiv 3 + 1 \equiv 4 \, (mod \; 7)$, altså en torsdag.

Vi øker altså dagnummeret med $365 \equiv 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 \equiv 3 + y – 2000 \, (mod \; 7)$, der $y$ er året der vi vil finne dagnummeret til 1. mars. 

Eksempel 7:

1. mars 2002 blir $u \equiv 3 + 2002 – 2000 \equiv 5 \, (mod \; 7)$, en fredag.

1. mars 2003 blir $u \equiv 3 + 2003 – 2000 \equiv 6 \, (mod \; 7)$, en lørdag.

Men Jorda bruker ikke nøyaktig $365$ dager på turen rundt Sola, men omlag 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 \equiv 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, \dots, 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$ bety de to første sifrene 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, var at de i år 0 ikke brukte vår tidsregning, og 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 etter vår tidsregning ville 1. mars år 0 også 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$ de to første sifrene 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 \equiv 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 \equiv 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$ er årstallet, $h$ de to første sifrene i årstallet, $m$ månedsnummeret regnet fra mars, og $d$ dagnummeret.

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 5:

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

matematikk.org har også en side der de diskuterer en metode for å beregne riktig ukedag i hodet:
http://www.matematikk.org/oss.html?tid=105667. Men det later ikke til at de tar hensyn til at forskyvingen i skuddår er forskjellig før og etter 29. februar.

Rest ved divisjon av store tall

Som vi skal se i artikkelen om kryptografi, vil vi kunne ha behov for å finne resten når vi heltallsdividerer store tall. Med andre ord å finne mindre, kongruente tall for en gitt modulus. For små tall kan vi enkelt gjøre dette med en datamaskin eller kalkulator, for eksempel ved kommandoen rest i et regneark eller mod i GeoGebra. Men for store tall vil vi måtte gjøre en trinnvis omregning til mindre, kongruente tall som vi kan bruke i vanlige beregninger.

I eksempel 9 i artikkelen om regneregler for kongruens viste vi at $29^{16} \equiv 4 \, (mod \; 19)$ ved å benytte at potensen $29^{16}$ kunne skrives som $(29)^{2^{\Large 2^{\Large 2^{\Large 2}}}}$ og så bruke potensregelen til å finne tall kongruente med $29$, $29^2$, 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 $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 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 heltallsdividerer $7^{15}$ med $13$.

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

$7^{15} = 7^{1+2+4+8} = 7 \cdot 7^2 \cdot 7^4 \cdot 7^8$.

$7^2 \equiv 49 \equiv 10 \, (mod \; 13)$.

$7^4 \equiv {(7^2)}^2 \equiv 10^2 \equiv 100 \equiv 9 \, (mod \; 13)$.

$7^8 \equiv {(7^4)}^2 \equiv 9^2 \equiv 81 \equiv 3 \, (mod \; 13)$.

Så vi har $7^{15} \equiv7 \cdot 7^2 \cdot 7^4 \cdot 7^8 \equiv 7 \cdot 10 \cdot 9 \cdot 3 \equiv 1890 \equiv 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.

For å beregne at $1890 \equiv 5 \, (mod \; 13)$ i eksempel 14, kan vi bruke metoden vi lærte i avsnittet om regneregler i kongruens

$1890 \equiv 1890 – \lfloor \frac{\displaystyle 1890}{\displaystyle 13} \rfloor \cdot 13 \equiv 1890 – 1885 \equiv 5 \, (mod \; 13)$.

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:

$7^2 \equiv 49 \equiv -3 \, (mod \; 13)$.

$7^4 \equiv {(7^2)}^2 \equiv (-3)^2 \equiv 9 \equiv -4 \, (mod \; 13)$.

$7^8 \equiv {(7^4)}^2 \equiv (-4)^2 \equiv 16 \equiv 3 \, (mod \; 13)$.

Så vi har $7^{15} \equiv 7 \cdot 7^2 \cdot 7^4 \cdot 7^8 \equiv 7 \cdot (-3) \cdot (-4) \equiv 252 \equiv 5 \, (mod \;13)$.

Oppgave 6:

Finn resten du får når du heltallsdividerer $6^{13}$ med $11$. Kontroller svaret i et regneark eller GeoGebra.

Se løsningsforslag

Dette nesstedet har en app som finner rest ved heltallsdivisjon av store tall.

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.
  • Wikipedia