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.

Delelighet

Om delelighet

Når vi dividerer to heltall på hverandre, blir resultatet av og til et heltall, for eksempel er 24 : 8 = 3 og −21 : 3 = −7. Vi sier da at divisjonen går opp. Men resultatet kan også bli et tall med desimaler, for eksempel er 9 : 2 = 4,5. Vi sier da at divisjonen ikke går opp.

Generelt, hvis a og b er vilkårlige heltall og a : b = t er et heltall, går divisjonen opp, og vi sier at a er delelig med b. Andre måter å si det på er at b går opp i a, at b er en divisor i a, eller at b er en faktor i a. I matematisk terminologi skriver vi dette som b | a. Det motsatte, at b ikke går opp i a, skriver vi som ba.

At divisjonen a : b = t går opp, kan vi tolke som at en blokk med a elementer kan deles opp i t blokker med b elementer i hver.

Vi kan også tolke det slik at hvis vi på ei tallinje legger b etter seg selv t ganger, havner vi i a.

Eksempel 1:

6 : 3 = 2

Det betyr at en blokk med a = 6 elementer kan deles opp i t = 2 blokker med b = 3 elementer i hver:

Illustrasjon av at 6:3 = 2 betyr at 6 elementer kan grupperes i 2 blokker med 3 elementer i hver

Legger vi b = 3 etter seg selv t = 2 ganger, havner vi i a = 6:

Illustrasjon av at 6:3 = 2 betyr at 3 går 2 ganger opp i 6

Eksempel 2:

8 : 2 = 4

Det betyr at en blokk med a = 8 elementer kan deles opp i t = 4 blokker med b = 2 elementer i hver:

Illustrasjon av at 8:4 = 2 betyr at 8 elementer kan grupperes i 4 blokker med 2 elementer i hver

Legger vi b = 2 etter seg selv t= 4 ganger, havner vi i a = 8.

Illustrasjon av at 8:2 = 4 betyr at 2 går 4 ganger opp i 8

Hvis a, b og c er heltall, der c er en faktor i b og b er en faktor i a, er c også en faktor i a.

En annen måte å si det samme på er at hvis a er delelig med b, og b er delelig med c, er a delelig med c.

I matematisk terminologi:

$\fbox{$\text {Hvis } c \mid b \text{ og } b \mid a \text{, vil } c \mid a$}$

Det betyr at hvis a kan deles opp i blokker med b elementer i hver og b kan deles opp i blokker med c elementer i hver, kan a deles opp i blokker med c elementer i hver.

Vi tar med et bevis for denne påstanden. Det er et direkte, algebraisk bevis, det vil si at vi ved manipulasjon av symboler demonstrerer at påstanden er riktig.

Hvis c | b, finnes det et heltall, k, slik at ck = b. Hvis b | a, finnes det et heltall, l, slik at bl = a. Vi har da at a = bl = (ck)l = c(kl). Siden k og l er heltall, er kl heltall. a kan derved skrives som c multiplisert med et heltall, noe som betyr at c | a og påstanden er bevist.

Eksempel 3:

2 er en faktor i 4, og 4 er en faktor i 8, derfor er 2 en faktor i 8. Eller, sagt på en annen måte, 8 er delelig med 4 og 4 er delelig med 2, derfor er 8 delelig med 2. Vi kan illustrere det med blokker slik:

Illustrasjon av tall som går opp i hverandre

og på ei tallinje slik:

Illustrasjon av tall som går opp i hverandre

Det er også slik at hvis et heltall, t, er en faktor i et annet, a, er det også en faktor i alle heltallige multipler av a.

En annen måte å si det samme på er at hvis a er delelig med t, er alle heltallige multipler av a også delelige med t.

Eksempel 4:

2 er en faktor i 4, derfor er 2 også en faktor i 8, 12, 16, 20 og så videre. Eller sagt på en annen måte, tallene 8, 12, 16, 20 og så videre er delelige med 4, derfor er de også delelige med 2. Vi kan illustrere det på ei tallinje slik:

Illustrasjon av at 2 går oppi multipler av 4

Mer generelt er det slik at hvis et heltall, t, er en faktor i to andre heltall, a og b, er det også en faktor i alle summer av heltallige produkter av a og b.

Sagt på en annen måte, hvis heltallene a og b er delelige med heltallet t, er alle summer av heltallige produkter av a og b også delelige med t.

I matematisk terminologi:

$\fbox{$\text {Hvis } t \mid a \text{ og } t \mid b \text{, vil } t \mid (ma + nb)$}$

Her er m og n vilkårlige heltall.

Tallet ma + nb kalles en lineær kombinasjon av a og b. Vi vil derfor referere til denne regelen som «regelen om lineære kombinasjoner».

Eksempel 5:

3 er en faktor i 6 og 9. Da er 3 en faktor i 57, fordi 57 kan skrives som en lineær kombinasjon av 6 og 9.
57 = 2 · 6 + 5 · 9.

7 er en faktor i 14 og 35. Da er 7 en faktor i 259, fordi 259 kan skrives som en lineær kombinasjon av 14 og 35.
259 = (−9) · 14 + 11 · 35.

Oppgave 1:

9 er en faktor i 18 og 27. Begrunn at 9 derfor er en faktor i 63.

Se løsningsforslag

Det er også slik at hvis a, b og c er heltall, der c er en faktor i a, men ikke en faktor i b, er c heller ikke en faktor i a + b.

En annen måte å si det samme på er at hvis a er delelig med c, men b ikke er delelig med c, er a + b ikke delelig med c.

I matematisk terminologi:

$\fbox{$\text {Hvis } c \mid a \text{ men } c \nmid b \text{, vil } c \nmid (a + b)$}$

Beviset for denne påstanden er et såkalt «bevis ved selvmotsigelse», eller «reductio ad absurdum». Vi tar utgangspunkt i det motsatte av det vi skal bevise, nemlig at a + b faktisk er delelig med c. Så demonstrerer vi at dette fører til en selvmotsigelse. Vi kommer fram til at b faktisk er delelig med c, noe som er i strid med den ene av forutsetningene.

Vi antar altså at c | (a + b). Da finnes det et heltall, k, slik at ck = a + b. Siden c | a, vet vi at det finnes et heltall, l, slik at cl = a. Dette kan vi sette sammen til ck = cl + b. Vi flytter cl over til venstre side med fortegnsskifte og får ckcl = b. Setter vi c utenfor parentes, får vi c(kl) = b. Siden k og l er heltall, er kl heltall. b kan derved skrives som c multiplisert med et heltall, noe som er i strid med en av forutsetningene. Setningen er derved bevist.

c kan allikevel være en faktor i lineære kombinasjoner av a og b.

Eksempel 6:

3 er en faktor i 6, men ikke i 4. 3 kan derfor ikke være en faktor i 10 = 6 + 4. Men 3 er en faktor i 18 = 6 + 3 · 4.

Delelighetsregler

Nå skal vi se på en praktisk anvendelse av regelen om lineære kombinasjoner, nemlig å vise hvordan vi kan utlede regler for om et vilkårlig heltall er delelig med 2, 3, 4, 5 eller 9.

For å begrunne reglene kommer vi til å skrive tallene på utvidet form,
n = am10m + am−110m−1 + … + a110 + a0, slik vi lærte i artikkelen om tall og tallsystemer. I noen tilfeller bruker vi også tallets tverrsum, som vi lærte om i samme artikkel.

Toerregelen

Når vi studerer et tall på utvidet form, ser vi at vi multipliserer alle koeffisientene unntatt a0 med potenser av 10. Setter vi 10 utenfor parentes, får vi følgende uttrykk for et tall på utvidet form:

n = (am 10m−1+ am−1 10m−2+ … + a1)10 + a0

Vi trenger ikke bry oss med alle detaljene inni parentesen, så for enkelhets skyld kaller vi hele dette uttrykket for b:

n = 10b + a0

Vi vet at 10 er delelig med 2, følgelig er alle multipler av 10 også er delelige med 2. Det vil si at 10b er delelig med 2, uavhengig av verdien til b. Hvis nå a0 også er delelig med 2, sier regelen om lineære kombinasjoner at n også er delelig med 2. Siden koeffisienten a0 representerer siste siffer i tallet n, følger toerregelen:

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

Eksempel 7:

336 er delelig med 2 fordi 6 er delelig med 2.

227 er ikke delelig med 2 fordi 7 ikke er delelig med 2.

Femmerregelen

Samme argument, basert på at 10 er delelig med 5, fører til femmerregelen:

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

Eksempel 8:

220 er delelig med 5 fordi 0 er delelig med 5.

231 er ikke delelig med 5 fordi 1 ikke er delelig med 5.

Firerregelen

Vi gjør nå et tilsvarende triks med tallet på utvidet form, men baserer oss på at alle koeffisienter unntatt a1 og a0 blir multiplisert med potenser av 100, og setter 100 utenfor parentes:

n = (am10m−2 + am−110m−3 + … + a2)100 + a110 + a0

Vi trenger ikke bry oss med alle detaljene inni parentesen, så for enkelhets skyld kaller vi hele dette uttrykket for b:

n = 100b + a110 + a0

Vi vet at 100 er delelig med 4, følgelig er alle multipler av 100 også er delelige med 4. Det vil si at 100b er delelig med 4, uavhengig av verdien til b. Hvis nå a110 + a0 også er delelig med 4, sier regelen om lineære kombinasjoner at n også er delelig med 4. Siden uttrykket a110 + a0 representerer tallet dannet av de to siste sifrene i tallet n, følger firerregelen:

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

Eksempel 9:

336 er delelig med 4 fordi 36 er delelig med 4.

222 er ikke delelig med 4 fordi 22 ikke er delelig med 4.

Hvis vi har brukt firerregelen og funnet at et tall er delelig med 4, vet vi automatisk at det også er delelig med 2. Og omvendt, hvis vi har brukt toerregelen og funnet at et tall ikke er delelig med 2, vet vi automatisk at det heller ikke er delelig med 4.

Nierregelen

Toer- og femmerregelen virker fordi 2 og 5 går opp i tallsystemets grunntall, nemlig 10, og firerregelen fordi 4 går opp i grunntallet opphøyd i 2, nemlig 100. Noe slikt system finnes imidlertid ikke for 3 og 9, så for å finne regler for delelighet med 3 og 9 må vi angripe problemet på en litt annen måte. Vi starter med å addere (− 1 + 1) til alle tierpotensene i tallet på utvidet form. Det kan vi fritt gjøre, for vi adderer jo bare 0.

n = am(10m − 1 + 1) + am−1(10m−1 − 1 + 1) + … + a1(10 − 1 + 1) + a0

som ved å skille ut multiplikasjonen av koeffisientene med 1 kan omformes til

n = am(10m − 1) + am−1(10m−1 − 1) + … + a1(10 − 1) + am · 1 + am−1 · 1 + … + a1 · 1 + a0

Poenget med dette er at alle tierpotensene minus 1 vil være multipler av 9, nemlig 9, 99, 999, og så videre. Vi kan altså forenkle uttrykket til

n = 9b + am + am−1 + … + a1 + a0, der b er et eller annet tall vi ikke trenger å bry oss om.

9b er delelig med 9 fordi det er en multippel av 9. Hvis nå am + am−1 + … + a1 + a0 også er delelig med 9, sier regelen om lineære kombinasjoner at n også er delelig med 9. Vi ser at am + am−1 + … + a1 + a0 er summen av koeffisientene i tallet, det vil si det samme som tverrsummen, slik den ble presentert i artikkelen om tall og tallsystemer. Av dette følger nierregelen:

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

Hvis tverrsummen blir et stort tall som vi kanskje ikke vet om er delelig på 9, bruker vi nierregelen på dette tallet også.

Eksempel 10:

48528 er delelig med 9 fordi T(48528) = 27 er delelig med 9. Hvis vi skulle være usikre på om 27 er delelig med 9, tar vi tverrsummen på nytt, T(27) = 9.

116 er ikke delelig med 9 fordi T(116) = 8 ikke er delelig med 9.

222 er ikke delelig med 9 fordi T(222) = 6 ikke er delelig med 9.

Treerregelen

I begrunnelsen for nierregelen skrev vi tallet n som

n = 9b + am + am−1 + … + a1 + a0. Fordi 9 er en multippel av 3, vil alle tall på formen 9b være delelige med 3. Hvis am + am−1 + … + a1 + a0, altså tverrsummen, også er delelig med 3, vil n være delelig med 3. Av dette følger treerregelen:

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

Hvis tverrsummen blir et stort tall som vi kanskje ikke vet om er delelig på 3, bruker vi treerregelen på dette tallet også.

Eksempel 11:

48525 er delelig med 3 fordi T(48525) = 24 er delelig med 3. Hvis vi skulle være usikre på om 24 er delelig med 3, tar vi tverrsummen på nytt, T(24) = 6.

116 er ikke delelig med 3 fordi T(116) = 8 ikke er delelig med 3.

222 er delelig med 3 fordi T(222) = 6 er delelig med 3.

Hvis vi har brukt nierregelen og funnet at et tall er delelig med 9, vet vi automatisk at det også er delelig med 3. Og omvendt, hvis vi har brukt treerregelen og funnet at et tall ikke er delelig med 3, vet vi automatisk at det heller ikke er delelig med 9.

Oppgave 2:

Avgjør om 1386 er delelig med henholdsvis 2, 3, 4, 5 og 9 ved å bruke delelighetsregler. Bruk reglene i den rekkefølgen du ønsker.

Se løsningsforslag

Divisjon med rest

Innledningsvis sa vi at hvis divisjonen a : b = t går opp, betyr det at t er et helt tall. a kan da deles i t blokker med b elementer i hver.

I eksempel 2 så vi for eksempel at 8 : 2 = 4 betydde at a = 8 elementer kunne organiseres i t = 4 blokker med b = 2 elementer i hver.

Hvis divisjonen derimot ikke går opp, vil det ikke være mulig å organisere alt i blokker med b elementer. Det kan være mulig å danne et antall fulle blokker med b elementer, men det vil alltid være en blokk som ikke blir full.

Eksempel 12:

Divisjonen 7 : 3 går ikke opp. Forsøker vi å dele a = 7 elementer i blokker med b = 3 elementer, vil vi få to fulle blokker, men også en blokk som bare inneholder ett element:

Illustrasjon av at 7:3 ikke går opp

Eksempel 13:

Divisjonen 6 : 4 går ikke opp. Forsøker vi å dele a = 6 elementer i blokker med b = 4 elementer, vil vi få én full blokk, men også en blokk som bare inneholder to elementer:

Illustrasjon av at 6:4 ikke går opp

Antall elementer i en blokk som ikke er full, kaller vi for en rest, og å dividere på denne måten kalles å dividere med rest. I eksempel 12 er resten 1, i eksempel 13 er resten 2. Ser vi tilbake på eksempel 1 og 2, der divisjonen gikk opp, fantes det ingen elementer i blokker som ikke var fulle. Det er det samme som at resten er 0.

Utfører vi divisjonene i eksempel 12 og 13 på ordinær måte, får vi 7 : 3 = 2,3 og 6 : 4 = 1,5.

Streken over tretallet betyr at sifferet 3 gjentar seg i det uendelige.

Vi ser at heltallsdelen av svarene, henholdsvis 2 og 1, forteller hvor mange fulle blokker vi får.

Multipliserer vi desimaldelen av svarene med divisor, finner vi ut hva resten blir, henholdsvis 0, 3 · 3 = 1 og 0,5 · 4 = 2.

Eksempel 14:

Tabellen under viser tallene fra 0 til 10 dividert med 4. Vi bruker heltallsdelen av resultatene til å regne ut hvor mange hele blokker på 4 vi får, og desimaldelen av resultatene multiplisert med 4 til å regne ut hvilken rest vi får i hvert tilfelle.

Tall: 0 1 2 3 4 5 6 7 8 9 10
Tall dividert på 4: 0,00 0,25 0,50 0,75 1,00 1,25 1,50 1,75 2,00 2,25 2,50
Hele blokker: 0 0 0 0 1 1 1 1 2 2 2
Rest: 0 1 2 3 0 1 2 3 0 1 2

Vi ser at vi starter med 0 blokker og 0 i rest. Hver gang tallet øker med 1, øker resten med 1, inntil tallet blir en multippel av 4. Da går resten tilbake til 0, og vi får en ny full blokk med 4 elementer.

Alle hele tall dividert på 4 vil kunne representeres unikt som i eksempel 14, med et antall blokker à 4 elementer, og en rest som varierer mellom 0 og 3.

Å dividere på denne måten vil vi heretter referere til som å dividere med rest, og antall fulle blokker kaller vi kvotienten i divisjonen. En kvotient er her altså et helt tall, noe den ikke trenger være ved vanlig divisjon.

GeoGebra / regneark

Når vi dividerer med rest, kan vi i GeoGebra finne kvotienten ved hjelp av funksjonen div, og resten ved hjelp av funksjonen mod. Skriver vi for eksempel div(7, 4) i inntastingsfeltet, svarer GeoGebra med tallet 1 i algebrafeltet. Tilsvarende gir mod(7, 4) tallet 3 i algebrafeltet. Dette er det samme som vi fant i eksempel 14.

I regneark som Excel heter de tilsvarende funksjonene kvotient og rest. For eksempel gir =kvotient(7; 4) tallet 1 og =rest(7; 4) tallet 3. Vi legger merke til at i et regneark innledes alle kommandoer med likhetstegn, og parameterne skilles med semikolon, ikke komma.

Divisjonsalgoritmen

Generelt vil alle hele tall, a, dividert på et positivt heltall, b, på en unik måte kunne representeres som en kvotient, q, og en rest, r, som varierer mellom 0 og b−1. Dette er divisjonsalgoritmen, eller divisjonslemmaet, som vi matematisk uttrykker slik:

$\fbox{Hvis $a \in \mathbb Z, b \in \mathbb N$, vil det alltid finnes unike heltall, $q$ og $r$ slik at $a = qb + r$, der $0 \le r < b$}$

Hvis divisjonen a : b går opp, blir resten r = 0. Hvis b > a, blir q = 0 og r = a, slik vi ser i eksempel 15.

Eksempel 15:

I eksempel 14 er b = 4, mens a varierer fra 0 til 10.

Vi ser at a ved hjelp av divisjonsalgoritmen kan uttrykkes som

$\begin{align}
0 &= 0 \cdot 4 + 0 \\
1 &= 0 \cdot 4 + 1 \\
2 &= 0 \cdot 4 + 2 \\
3 &= 0 \cdot 4 + 3 \\
4 &= 1 \cdot 4 + 0 \\
5 &= 1 \cdot 4 + 1 \\
6 &= 1 \cdot 4 + 2 \\
7 &= 1 \cdot 4 + 3 \\
8 &= 2 \cdot 4 + 0 \\
9 &= 2 \cdot 4 + 1 \\
10 &= 2 \cdot 4 + 2 \\
\end{align}$

Ei tallinje kan brukes til å illustrere divisjonsalgoritmen. I a = qb + r er q antall ganger vi må legge b etter hverandre for å komme så langt at vi bare mangler resten, r, på å nå fram til a.

Eksempel 16:

$\begin{align}
8 &= 2 \cdot 4 + 0 \\
14 &= 3 \cdot 4 + 2
\end{align}$

Dette er illustrert på tallinja under. Linjestykket med lengde b = 4 rekker nøyaktig fram til a = 8 når vi legger det etter seg selv q = 2 ganger, her er resten r = 0. Men vi får det ikke til å rekke nøyaktig fram til a = 14. Da legger vi det etter seg selv q = 3 ganger, og bruker en rest på r = 2 på å nå a.

Illustrasjon av divisjonsalgoritmen

Divisjonsalgoritmen er svært nyttig i mange sammenhenger. I artikkelen om faktorisering ser vi for eksempel at den gir oss en effektiv metode til å finne to talls største felles faktor.

Divisjonsalgoritmen kan også brukes på negative tall. a i uttrykket a = qb + r vil da være mindre enn null, mens b forblir positiv. Vi får en negativ q, mens r, som skal ligge mellom 0 og b−1 forblir positiv eller 0.

Eksempel 17:

$\begin{align}
−8 &= −2 \cdot 4 + 0\\
−14 &= −4 \cdot 4 + 2
\end{align}$

Akkurat som for positive tall kan vi illustrere dette med ei tallinje.

Eksempel 18:

Tallene fra eksempel 17 er illustrert under. Linjestykket med lengde b = 4 rekker nøyaktig fram til −8 når vi legger det etter seg selv −2 ganger, her er rest 0. Men vi får det ikke til å rekke nøyaktig fram til −14. Siden resten skal være positiv, må vi gå forbi −14 ved å legge b = 4 etter seg selv −4 ganger og så bruke resten på 2 til å gå tilbake til 14.

Illustrasjon av divisjonsalgoritmen for negative tall

Beregning med GeoGebra / regneark

For å kunne bruke divisjonsalgoritmen på to tall, a og b, må vi beregne q og r. I GeoGebra kan vi bruke funksjonene div og mod til dette, og i Excel funksjonene kvotient og rest, slik vi så tidligere. Dessverre håndterer ikke Excel negative a riktig. Skal vi for eksempel finne kvotient og rest når a = −14 og b = 4, skriver vi =kvotient(-14; 4), og får −3, og =rest(-14; 4), og får 2. Men prøver vi å regne oss tilbake, får vi −4 · 3 + 2 = −10, ikke −14. GeoGebra gjør det derimot riktig. div(-14, 4) gir −4, og mod(-14, 4) gir 2. Og −4 · 4 + 2 = −14, slik vi så i eksempel 18.

Manuell beregning

Nå skal vi se på en metode til å beregne q og r for hånd, eller med en vanlig kalkulator.

q er tallet vi skal multiplisere med b for å komme så nærme a at vi havner eksakt i a når vi adderer resten, r. q finner vi ved å dividere ab og så runde ned til nærmeste heltall. For å indikere at vi runder ned til nærmeste heltall bruker vi symboler med klammeparenteser som bare er lukket i bunnen, slik at de danner et golv: $\lfloor \; \rfloor$.

Formelt sett er $\lfloor x \rfloor$ definert som det største heltallet som er mindre eller lik x. For positive tall betyr det å sløyfe tallets desimaler, slik vi gjorde i eksempel 13 og 14. Men for negative tall vil det ikke være slik. Vi kan tenke oss at vi finner $\lfloor x \rfloor$ ved å starte på x og gå mot venstre langs tallinja til vi treffer første heltall.

Eksempel 19:

$\begin{align}
\lfloor 2{,}75 \rfloor &= 2\\
\lfloor 2 \rfloor &= 2\\
\lfloor −2 \rfloor &= −2\\
\lfloor −2{,}75 \rfloor &= −3 \;\;\text{NB!}
\end{align}$

Som nevnt gir qb et tall som er slik at når vi adderer resten, r, havner vi i a. Altså: qb + r = a, det vil si at r = aqb.

Det betyr at vi i praksis kan bruke divisjonsalgoritmen på a og b slik:

  1. Vi finner $q = \lfloor \frac{\displaystyle a}{\displaystyle b} \rfloor$
     
  2. Vi finner r = aqb
     
  3. Vi skriver opp uttrykket a = qb + r

Eksempel 20:

Vi skal bruke divisjonsalgoritmen på a = 1028, b = 34.

Vi finner $\frac{\displaystyle a}{\displaystyle b} = {\large \frac{1028}{34}} \approx 30{,}24$

$q = \lfloor 30{,}24 \rfloor = 30$

og r = 1028 − 30 · 34 = 8

Så 1028 = 30 · 34 + 8.

Eksempel 21:

Vi skal bruke divisjonsalgoritmen på a = −380, b = 75.

Vi finner $\frac{\displaystyle a}{\displaystyle b} = {\large \frac{−380}{75}} \approx −5{,}07$

$q = \lfloor −5{,}07 \rfloor = −6$

og r = −380 − (−6 · 75) = 70

Så −380 = −6 · 75 + 70.

Oppgave 3:

Bruk divisjonsalgoritmen på

      1. a = 133, b = 21
         
      2. a = −50, b = 8

Se løsningsforslag

Beregne $\lfloor x \rfloor$ i GeoGebra og regneark

I GeoGebra finner vi $\lfloor x \rfloor$ ved hjelp av funksjonen floor. I GeoGebra er punktum, ikke komma, desimalskilletegn, så hvis vi for eksempel vil finne $\lfloor −2{,}75 \rfloor$ i GeoGebra, skriver vi floor(-2.75) i inntastingsfeltet. GeoGebra svarer med −3 i algebrafeltet, slik vi fant i eksempel 19.

I regneark som Excel finner vi $\lfloor x \rfloor$ ved hjelp av funksjonen med det forferdelige navnet avrund.gjeldende.multiplum.ned.matematisk. Det finnes også andre avrundingsfunksjoner, for eksempel avrund.ned, men denne vil ikke beregne $\lfloor x \rfloor$ riktig for negative x. Det kan angis mange parametere til avrund.gjeldende.multiplum.ned.matematisk, men for å finne $\lfloor x \rfloor$ angir vi bare x. For eksempel gir =avrund.gjeldende.multiplum.ned.matematisk(-2,75) tallet −3.

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.