Løsningsforslag, tallteori

Tall og tallsystemer

Oppgave 2:

Vi skal regne ut hva $52306_7$ i sjutallsystemet blir i titallsystemet:

$52306_7=5 \cdot 7^4 + 2 \cdot 7^3 + 3 \cdot 7^2 + 0 \cdot 7^1 + 6 \cdot 7^0 = 12005 + 686 + 147 + 0 + 6 = 12844_{10}$

Tilbake til oppgaven

Oppgave 3:

Vi skal skrive $52306_7$ på utvidet form. Siden vi er i sjutallsystemet, er grunntallet, lik $7$. Vi får

$52306_7 = 5 \cdot 7^4 + 2 \cdot 7^3 + 3 \cdot 7^2 + 0 \cdot 7 + 6$.

Tilbake til oppgaven

Oppgave 5:

Vi har gitt et tall i totallsystemet, $11101001111_2$, og skal regne ut hva tallet blir i

  1. Sekstentallsystemet.
    Grupperer 4 og 4 fra høyre og setter på en ledende null:
    $(0111 \; 0100 \; 1111)_2$
    Regner om hver gruppe til sekstentallsystemet:
    $0111_2 = 7_{16} \\
    0100_2 = 4_{16} \\
    1111_2 = F_{16}$

    $11101001111_2 = 74F_{16}$.
     
  2. Titallsystemet.
    Vi har tallet både i totallsystemet og sekstentallsystemet, og kan velge hvilket vi vil regne om fra. Naturligvis er det letteste å ta utgangspunkt i sekstentallsystemet som har færrest sifre:
    $74F_{16} = 7 \cdot 16^2 + 4 \cdot 16 +15 = 1792 + 64 + 15 = 1871_{10}$
    Tar vi utgangspunkt i totallsystemet, får vi:
    $11101001111_2 = \\
    1 \cdot 2^{10} + 1 \cdot 2^9 + 1 \cdot 2^8 + 0 \cdot 2^7 + 1 \cdot 2^6+0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 1 = \\
    1024+512+256+0+64+0+0+8+4+2+1=1871_{10}$

Tilbake til oppgaven

Oppgave 7:

Vi har gitt et tall, $n = 7193536$, og skal finne tallets

  1. tverrsum
    $T(n) = 7 + 1 + 9 + 3 + 5 + 3 + 6 = 34$.
     
  2. alternerende tverrsum
    $A(n) = 6 – 3 + 5 – 3 + 9 – 1 + 7 = 20$.

Tilbake til oppgaven

Delelighet

Oppgave 1:

Basert på at vi vet at $9$ er en faktor i $18$ og $27$ skal vi begrunne at $9$ er en faktor i $63$.

Siden $63$ kan skrives som en lineær kombinasjon av $18$ og $27$, $63 = 2 \cdot 18 + 1 \cdot 27$, er $9$ en faktor i $63$.

Tilbake til oppgaven

Oppgave 2:

Vi skal avgjøre om $1386$ er delelig med henholdsvis $2$, $3$, $4$, $5$ og $9$ ved å bruke delelighetsregler.

Tallet dannet av de to siste sifrene er $86$. $86$ er ikke delelig med $4$, derfor er $1386$ ikke delelig med $4$.

Siste siffer er $6$, og $6$ er delelig med $2$. $1386$ er derfor delelig med $2$.

Siste siffer er $6$, og $6$ er ikke delelig med $5$. $1386$ er derfor ikke delelig med $5$.

Tverrsummen til $1386$ er $T(1386) = 1 + 3 + 8 + 6 = 18$. $18$ er delelig med $9$. $1386$ er derfor delelig med $9$. Skulle vi være usikre på om $18$ er delelig med $9$, tar vi tverrsummen en gang til og får $T(18)= 1 + 8 = 9$

Siden $1386$ er delelig med $9$, er $1386$ også delelig med $3$.

Vi har altså funnet at $1386$ er delelig med $2$, $3$ og $9$.

NB! Dette betyr ikke at vi har funnet alle faktorene i tallet, $1386 = 2 \cdot 3 \cdot 3 \cdot 7 \cdot 11$.

Tilbake til oppgaven

Oppgave 3:

Vi skal bruke divisjonsalgoritmen på

  1. ​$a = 133, b = 21$
    Vi finner ${\large \frac{a}{b}} = {\large \frac{133}{21}} \approx 6{,}33$
    Så $q = \lfloor 6{,}33 \rfloor = 6$
    og $r = 133 – 6 \cdot 21 = 7$
    $133 = 6 \cdot 21 + 7$.
     
  2. $a = -50, b = 8$
    Vi finner ${\large \frac{a}{b}} = {\large \frac{-50}{8}} = -6{,}25$
    $q = \lfloor -6{,}25 \rfloor = -7$
    og $r = -50 – (-7 \cdot 8) = 6$
    $-50 = -7 \cdot 8 + 6$.

​Tilbake til oppgaven

Primtall

Oppgave 1:

Vi skal bruke metoden med Eratosthenes' såld til å finne alle primtall opp til 120.

Vi lager en tabell med de naturlige tallene fra 1 til 120. Så krysser vi ut alle multipler av 2, 3, 5 og 7. Da er alle tallene som står igjen primtall fordi vi bare trenger å sjekke multipler av $p$ som er slik at $p \le \sqrt {120} \approx 10,95$. Det største primtallet som er mindre enn 10,95 er 7.

​​Tilbake til oppgaven

Oppgave 2:

Vi får oppgitt at $900$ kan skrives som $20 \cdot 45$ og skal avgjøre om følgende er riktig:

  1. 3 går opp i 900. Da går 3 opp i 45.
    Riktig. 3 går opp i 900, men ikke i den ene faktoren, 20. Da må 3 gå opp i den andre faktoren, 45.
     
  2. 5 går opp i 900. Da kan ikke 5 gå opp i både 20 og 45.
    Galt. Vi har et teorem som sier at hvis p går opp i produktet ab, vil p gå opp i a eller b. Men et matematisk "eller" betyr "den ene eller den andre eller begge". Teoremet er altså ikke til hinder for at 5 kan gå opp i både 20 og 45, noe 5 jo faktisk gjør.

​​​Tilbake til oppgaven

Oppgave 3:

Vi skal begrunne at det for $n > 2$ ikke finnes primtall på formen $n^2 – 1$.

Ved hjelp av tredje kvadratsetning baklengs kan vi skrive $n^2 – 1$ som $(n+1)(n-1)$. Et slikt tall kan altså alltid deles opp i minst to faktorer.

$3^2 – 1 = 8$, for eksempel, kan skrives som $(3 + 1)(3 – 1) = 4 \cdot 2$.

​​​Tilbake til oppgaven

Oppgave 4:

Basert på lista med Mersenne-primtall og formelen for å generere perfekte tall, skal vi finne det perfekte tallet generert av Mersenne-primtall nummer fire.

Mersenne-primtall nummer fire er $7$, vi setter inn i formelen og får $2^{( 7 – 1)}(2^7 – 1) = 64 \cdot 127 = 8128$.

​​​Tilbake til oppgaven

Oppgave 5:

Basert på primtallsetningen skal vi anslå hvor mange primtall det finnes som er lavere enn 5 000 000.

Vi setter inn $n = 5 \, 000 \, 000$ i primtallsetningen og får $\frac{\displaystyle n}{\displaystyle \ln n} = \frac{\displaystyle 5 \, 000 \, 000}{\displaystyle \ln 5 \,000 \, 000} \approx 324 \,150$.

Det finnes omlag 324 150 primtall mindre enn 5 000 000.

​​​Tilbake til oppgaven

Faktorisering

Oppgave 1:

Vi skal bruke Fermats metode til å faktorisere $189$.

Vi starter med $a = \lceil \sqrt{189} \rceil = 14$.

Vi får

$b^2 = (14)^2 – 189 = 196 – 189 = 7$.

$7$ er ikke et kvadrattall, så vi går videre og prøver $a + 1 = 15$.

Vi får

$b^2 = (15)^2 – 189 = 225 – 189 = 36$.

$36$ er et kvadrattall, $6^2$.

Vi kan derved skrive $189$ som en differanse av to kvadrattall, $(15)^2 – (6)^2$, og følgelig kan $189$ faktoriseres som $(15 + 6)(15 – 6) = 21 \cdot 9$.

Vi vet at $21 = 3 \cdot 7$ og at $9 = 3 \cdot 3$, men la oss vise det ved hjelp av Fermats metode:

For å faktorisere $21$ starter vi med $a = \lceil \sqrt{21} \rceil = 5$.

Vi får

$b^2 = (5)^2 – 21 = 25 – 21 = 4$$4$ er et kvadrattall, $2^2$.

Vi kan derved skrive $21$ som en differanse av to kvadrattall, $(5)^2 – (2)^2$, og følgelig kan $21$ faktoriseres som $(5 + 2)(5 – 2) = 7 \cdot 3$.

For å faktorisere $9$ starter vi med $a = \lceil \sqrt{9} \rceil = 3$.

Vi får

$b^2 = (3)^2 – 9 = 9 – 9 = 0$$0$ er et kvadrattall, $0^2$. Vi kan derved skrive $9$ som en differanse av to kvadrattall, $(3)^2 – (0)^2$, og følgelig kan $9$ faktoriseres som $(3 + 0)(3 – 0) = 3 \cdot 3$.

Tilbake til oppgaven

Oppgave 3:

Vi skal bruke "brute force"-algoritmen til å faktorisere 1660.

Vi forsøker første primtall, og sjekker om 1660 er delelig med 2. Det er det. Vi noterer at 2 er en faktor, og utfører divisjonen 1660 / 2 = 830.

Vi arbeider videre med 830, og sjekker om 830 er delelig med 2. Det er det. Vi noterer at 2 er en faktor, og utfører divisjonen 830 / 2 = 415.

Vi arbeider videre med 415, og sjekker om 415 er delelig med 2. Det er det ikke.

Vi forsøker neste primtall, og sjekker om 415 er delelig med 3. Det er det ikke.

Vi forsøker neste primtall, og sjekker om 415 er delelig med 5. Det er det. Vi noterer at 5 er en faktor, og utfører divisjonen 415 / 5 = 83.

Vi arbeider videre med 83, og sjekker om 83 er delelig med 5. Det er det ikke.

Vi forsøker neste primtall, og sjekker om 83 er delelig med 7. Det er det ikke.

Siden $\sqrt {83} \approx 9,11$, er det høyeste primtallet som må sjekkes lik 7, så vi slår fast at 83 er et primtall.

Vi lister så opp faktorene vi har funnet, og konkluderer med at $1660 = 2 \cdot 2 \cdot 5 \cdot 83$.

Tilbake til oppgaven

Oppgave 4:

Vi skal finne $SFF(168, 140)$ ved hjelp av primtallsfaktorisering.

Ved hjelp av for eksempel "brute force"-metoden finner vi at $168 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 7$, og at $140 = 2 \cdot 2 \cdot 5 \cdot 7$. Vi ser at to totall og ett sjutall er felles, så vi får $SFF(168, 140) = 2 \cdot 2 \cdot 7 = 28$.

Så skal vi benytte dette til å forkorte brøken ${\large \frac{140}{168}}$ så langt det går. 

Å forkorte en brøk så langt det går betyr å dividere teller og nevner med deres største felles faktor. Denne har vi funnet ut er 28, så teller blir 140 / 28 = 5, og nevner blir 168 / 28 = 6.

Så ${\large \frac{140}{168}} = {\large \frac{5}{6}}$.

Tilbake til oppgaven

Oppgave 5:

Vi skal bruke Euklids algoritme til å finne $SFF(1365, 495)$.

Vi finner $q = {\large \lfloor \frac{1365}{495} \rfloor} = 2$, og $r = 1365 – 2 \cdot 495 = 375$. Så $1365 = 2 \cdot 495 + 375$.

Følgelig er $SFF(1365, 495) = SFF(495, 375)$.

Vi finner $q = {\large \lfloor \frac{495}{375} \rfloor} = 1$, og $r = 495 – 1 \cdot 375 = 120$. Så $495 = 1 \cdot 375 + 120$.

Følgelig er $SFF(495, 375) = SFF(375, 120)$.

Vi finner $q = {\large \lfloor \frac{375}{120} \rfloor} = 3$, og $r = 375 – 3 \cdot 120 = 15$. Så $375 = 3 \cdot 120 + 15$.

Følgelig er $SFF(375, 120) = SFF(120, 15)$.

Vi finner $q = {\large \lfloor \frac{120}{15} \rfloor} = 8$, og $r = 120 – 8 \cdot 15 = 0$. Så $120 = 8 \cdot 15 + 0$.

Følgelig er $SFF(120, 15) = SFF(15, 0) = 15$.

Så $SFF(1365, 495) = 15$.

Tilbake til oppgaven

Oppgave 6:

Vi skal finne $MFM(63, 135)$ ved hjelp av primtallsfaktorisering.

Ved hjelp av for eksempel "brute force"-metoden finner vi at $63 = 3 \cdot 3 \cdot 7$, og at $135 = 3 \cdot 3 \cdot 3 \cdot 5$. Vi ser at faktor $3$ i $b = 135$ forekommer to ganger i $a = 63$, og kan strykes to ganger. Så vi får $MFM(63, 135) = 3 \cdot 3 \cdot 7 \cdot \not {3} \cdot {\not 3} \cdot 3 \cdot 5 = 945$.

Alternativt: $63 = 3^2 \cdot 7^1$, og $135 = 3^3 \cdot 5^1$. Multipliserer vi høyeste potens av alle faktorene, får vi $MFM(63, 135) = 3^3 \cdot 5^1 \cdot 7^1 = 945$.

Så skal vi bruke resultatet til å regne ut ${\large \frac{1}{63}} + {\large \frac{1}{135}}$. Vi utvider brøkene med 945 og får.

${\large \frac{1}{63}} + {\large \frac{1}{135}} = {\large \frac{1}{63}} \cdot  {\large \frac{945}{945}} + {\large \frac{1}{135}} \cdot  {\large \frac{945}{945}}=  {\large \frac{\frac{945}{63}}{945}} + {\large \frac{\frac{945}{135}}{945}} = {\large \frac{15}{945}} + {\large \frac{7}{945}} = {\large \frac{22}{945}}$.

Tilbake til oppgaven

Oppgave 7:

Vi skal benytte at $SFF(3528, 9450) = 126$ til å finne $MFM(3528, 9450)$.

Vi bruker formelen $MFM(a, b) = \frac{\displaystyle a \cdot b}{\displaystyle SFF(a, b)}$ og får $MFM(3528, 9450) = \frac{\displaystyle 3528 \cdot 9450}{\displaystyle 126} = 264 \, 600$.

Tilbake til oppgaven

Kongruens

Oppgave 1:

Vi skal avgjøre om tre påstander om kongruens er riktige. Vi benytter oss av at $a \equiv b \, (mod \, m) \text{ hvis } m \mid (a – b)$:

  1. $65 \equiv 17 \, (mod \; 12)$
    Vi får $a – b = 65 – 17 = 48$. Siden $m = 12 \mid 48$, er påstanden riktig.
     
  2. $-12 \equiv 18 \, (mod \; 5)$
    Vi får $a – b = -12 – 18 = -30$. Siden $m = 5 \mid -30$, er påstanden riktig.
     
  3. $42 \equiv 27 \, (mod \; 7)$
    Vi får $a – b = 42 – 27 = 15$. Siden $m = 7 \nmid 15$, er påstanden ikke riktig.

Tilbake til oppgaven

Oppgave 2:

Vi skal formulere påstandene under som kongruenser.

  1. Tallet 37 gir samme rest ved divisjon med 8 som tallet 69.
    At 37 og 69 gir samme rest ved divisjon med 8, betyr at tallene er kongruente modulo 8:
    $37 \equiv 69 \, (mod \; 8)$.
     
  2. Om 15 timer er klokka det samme som for 9 timer siden.
    Regner vi med en 24-timers klokke, betyr det at 15 er kongruent med -9 modulo 24:
    $15 \equiv -9 \, (mod \; 24)$.
     
  3. Tallet 15 er et oddetall.
    Oddetall er tall som gir rest 1 når vi dividerer dem med 2, de er med andre ord kongruente med 1 modulo 2:
    $15 \equiv 1 \, (mod \; 2)$.

Tilbake til oppgaven

Oppgave 3:

Det er oppgitt at alle tall i samme kolonne I tabellen under tilhører samme restklasse, og vi skal finne modulus.

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18

Modulus vil være differansen av to etterfølgende tall i samme kolonne, for eksempel 7 – 1 = 6. Modulus er altså 6.

Tilbake til oppgaven

Kongruens, regneregler

Oppgave 1:

Vi har at $a \equiv b \, (mod \; 7)$, og skal avgjøre om $a + c \equiv b + d \, (mod \; 7)$ når

$c = 5, \, d = 12$

Her er $c \equiv d \, (mod \; 7)$ fordi $7 \mid (12 – 5) = 7$. Følgelig er $a + c \equiv b + d\, (mod \; 7)$.

$c = 8, \, d = 16$

Her er $c \not \equiv d \, (mod \; 7)$ fordi $7 \nmid (16 – 8) = 8$. Følgelig er $a + c \not \equiv b + d\, (mod \; 7)$.

Tilbake til oppgaven

Oppgave 2:

Vi vet at $365 \equiv 1 \, (mod \; 7)$, at 15. mars 2017 er en onsdag, og skal bruke kongruensregning til å finne ut hvilken ukedag 15. mars 2021 vil falle på.

Mellom disse datoene er det 3 ordinære år og 1 skuddår. Forskyvingen av ukedag blir derfor

$3 \cdot 365 + 366 \equiv 3 \cdot 1 + 2 \equiv 5 \, (mod \; 7)$.

Datoforskyvningen blir 5 dager, så 15. mars 2021 vil falle på en mandag.

Tilbake til oppgaven

Oppgave 3:

Vi skal finne det laveste, ikke-negative tallet som er kongruent med 243 modulo 13.

Vi har $243 \equiv 243 –  \lfloor \frac{\displaystyle 243}{\displaystyle 13}\rfloor \cdot 13  \equiv  243 – 18 \cdot 13 \equiv 9 \, (mod \; 13)$.

Tilbake til oppgaven

Oppgave 4:

Vi skal bruke divisjonsregelen til å dividere $21 \equiv 147 \, (mod \; 14)$ med henholdsvis $3$ og $7$ på begge sider av kongruenstegnet.

Vi har $SFF(3, 14) = 1$. Derfor får vi ${\large \frac{21}{3}} \equiv {\large \frac{147}{3}} \, (mod \; 14)$, det vil si $7 \equiv 49 \, (mod \; 14)$.

Vi har $SFF(7, 14) = 7$. Derfor får vi ${\large \frac{21}{7}} \equiv {\large \frac{147}{7}} \, (mod \; {\large \frac{14}{7}})$, det vil si $3 \equiv 21 \, (mod \; 2)$.

Tilbake til oppgaven

Oppgave 5:

Vi skal forkorte kongruensrelasjonen $126 \equiv 198 \, (mod \; 8)$ så mye som mulig.

Det er oppgitt at $SFF(126, 198) = 18$, så 18 er det største tallet vi kan dividere både 126 og 198 på og fremdeles få hele tall. 126 : 18 = 7 og 198 : 18 = 11.

$SFF(18, 8) = 2$, så vi må samtidig gå over fra å regne modulo 8 til å regne modulo 8 : 2 = 4.

Så relasjonen blir $7 \equiv 11 \, (mod \; 4)$.

Tilbake til oppgaven

Oppgave 6:

Vi skal lage en addisjonstabell modulo 5. Vi lager da en tabell med tallene 0-4 i første rad og første kolonne. Så fyller vi ut hver rute med summen av tallet i første rad og kolonne modulo 5:

+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3

Tilbake til oppgaven

Oppgave 7:

Vi skal avgjøre om det finnes en multiplikativ invers til $a$ modulo $n$ i eksemplene under, og i så fall finne en multiplikativ invers ved prøving og feiling.

  1. $a = 2, n = 5$
    Vi har $SFF(2, 5) = 1$, så det finnes multiplikativ invers. Vi prøver oss fram fra $1$ og oppover:
    $2 \cdot 1 \equiv 2 \, (mod \; 5) \\
    2 \cdot 2 \equiv 4 \, (mod \; 5) \\
    2 \cdot 3 \equiv 6 \equiv 1 \, (mod \; 5)$

    $3$ er en multiplikativ invers til $2$ modulo $5$.
     
  2. $a = 3, n = 8$
    Vi har $SFF(3, 8) = 1$, så det finnes multiplikativ invers. Vi prøver oss fram fra $1$ og oppover:
    $3 \cdot 1 \equiv 3 \, (mod \; 8) \\
    3 \cdot 2 \equiv 6 \, (mod \; 8) \\
    3 \cdot 3 \equiv 9 \equiv 1 \, (mod \; 8)$

    $3$ er en multiplikativ invers til $3$ modulo $8$.
     
  3. $a = 4, n = 8$
    Vi har $SFF(4, 8) = 4 \not \equiv 1$, så $4$ har ingen multiplikativ invers modulo $8$.

​Tilbake til oppgaven

Kongruens, anvendelser

Oppgave 3:

Vi skal bruke nierprøven og/eller elleveprøven til å undersøke om

  1. $1234 \cdot 364 = 224588$.
    Vi bruker nierprøven. $T(a) = T(1234) = 10, T(b) = T(364) = 13$.
    Vi har altså at $T(a) \cdot T(b) = 10 \cdot 13 = 130$. Tar vi tverrsummen en gang til, får vi $T(130) = 4$.
    $T(svar) = T(224588) = 29$. Tar vi tverrsummen to ganger til, får vi $T(T(29)) = 2$.
    Siden $4$ og $2$ ikke er kongruente modulo $9$, er utregningen feil.
     
  2. $1234 \cdot 364 = 449194$.
    Vi bruker nierprøven. I 1) fant vi at $T(a) \cdot T(b) = 130$ og $T(130) = 4$.
    $T(svar) = T(449194) = 31$. Tar vi tverrsummen en gang til, får vi $T(31) = 4$.
    Siden $4$ og $4$ er kongruente modulo $9$, påviser ikke nierprøven feil.
    Vi går videre med elleveprøven. $A(a) = A(1234) = 4 – 3 + 2 – 1 = 2, A(b) = A(364) = 4 – 6 + 3 = 1$. Vi har altså at $A(a) \cdot A(b) = 2 \cdot 1 = 2$.
    $A(svar) = A(449194) = 4 – 9 + 1 – 9 + 4 – 4 = -13$. Vi adderer $11$ to ganger og får $9$.
    Siden $2$ og $9$ ikke er kongruente modulo $11$, er utregningen feil.
     
  3. $1234 \cdot 364 = 449176$.
    Vi bruker nierprøven. I 1) fant vi at $T(a) \cdot T(b) = 130$ og $T(130) = 4$.
    $T(svar) = T(449176) = 31$. Tar vi tverrsummen en gang til, får vi $T(31) = 4$.
    Siden $4$ og $4$ er kongruente modulo $9$, påviser ikke nierprøven feil.
    Vi går videre med elleveprøven. I 2) fant vi at $A(a) \cdot A(b) = 2$.
    $A(svar) = A(449176) = 6 – 7 + 1 – 9 + 4 – 4 = -9$. Vi adderer $11$ og får $2$.
    Siden $2$ og $2$ er kongruente modulo $11$, påviser ikke elleveprøven feil. Og utregningen er faktisk riktig.

​Tilbake til oppgaven

Oppgave 4:

Vi skal avgjøre hva følgende betyr for resultatet av en multiplikasjon:

  1. Både nierprøven og elleveprøven påviser feil.
    Resultatet er feil.
     
  2. Enten nierprøven eller elleveprøven påviser feil.
    Resultatet er feil.
     
  3. Verken nierprøven eller elleveprøven påviser feil.
    Resultatet kan være riktig, men det trenger ikke være det.

​​Tilbake til oppgaven

Oppgave 5:

Vi skal avgjøre om 7-6-1-3-0-3-5-8-3-0-5-9-0 er en gyldig EAN-13-kode.

Vi legger inn sifrene i tabellen for EAN-koder og multipliserer hvert siffer med de angitte vektene:

Strekkode 7 6 1 3 0 3 5 8 3 0 5 9 0
Vekt 1 3 1 3 1 3 1 3 1 3 1 3 1
Vektet kode 7 18 1 9 0 9 5 24 3 0 5 27 0

Vi ser at summen av de vektede kodene blir

$7+18+1+9+0+9+5+24+3+0+5+27+0 \equiv 108 \equiv 8 \, (mod \; 10)$

Siden $8 \not \equiv 0 \, (mod \; 10)$, er dette ikke en gyldig EAN-13-kode.

​​Tilbake til oppgaven

Oppgave 6:

Vi skal avgjøre om 21023712345 er et gyldig personnummer.

Vi legger inn sifrene i tabellene for personnummer og multipliserer hvert siffer med de angitte vektene.

Første kontrollsiffer: 

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

Den vektede summen blir

$6+7+0+2+24+63+4+10+6+4+0 \equiv 126 \equiv 5 \, (mod \; 11)$.

Siden $5 \not \equiv 0 \, (mod \; 11)$ er første kontrollsiffer ikke riktig. Det har da ingen hensikt å undersøke andre kontrollsiffer, personnummeret er ikke gyldig.

​​Tilbake til oppgaven

Oppgave 7:

Vi skal bruke ukedagsformelen, $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)$, til å finne ut hvilken ukedag følgende begivenheter fant sted.

  1. Angrepet på tvillingtårnene i New York den 11. september 2001.
    September er måned 7 når vi regner fra mars. Så vi får
    $u \equiv 2001 + \lfloor \frac{\displaystyle 2001}{\displaystyle 4} \rfloor – \lceil \frac{\displaystyle 3 \cdot 20}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 7 – 1}{\displaystyle 5} \rfloor + 11\\\equiv 2001 + 500 – 15 + 18 + 11 \equiv 2515 \equiv 2 \, (mod \; 7)$
    En tirsdag.
     
  2. Wolfgang Amadeus Mozarts fødsel den 27. januar 1756.
    Januar 1756 er måned 11 i 1755 når vi regner fra mars. Så vi får
    $u \equiv 1755 + \lfloor \frac{\displaystyle 1755}{\displaystyle 4} \rfloor – \lceil \frac{\displaystyle 3 \cdot 17}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 11 – 1}{\displaystyle 5} \rfloor + 27 \\ \equiv 1755 + 438 – 13 + 28 + 27 \equiv 2235 \equiv 2 \, (mod \; 7)$
    En tirsdag.

Tilbake til oppgaven

Oppgave 8:

Vi skal bruk4 metoden med toerpotenser til å beregne resten vi får når vi dividerer $6^{13}$ med 11.

Vi skriver 13 som en sum av toerpotenser: 13 = 1 + 4 + 8.

Så $6^{13} = 6^{1 + 4 + 8} = 6 \cdot 6^4 \cdot 6^8$.

$6^2 \equiv 36 \equiv 3 \, (mod \; 11)$.

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

$6^8 \equiv {(6^4)}^2  \equiv (-2)^2 \equiv 4 \, (mod \; 11)$.

Så $6^{13} \equiv 6 \cdot 6^4 \cdot 6^8 \equiv 6 \cdot (-2) \cdot 4 \equiv -48 \equiv 7 \, (mod \; 11)$.

Resten er 7.

Her valgte vi -2 (mod 11) i stedet for 9 (mod 11) for å få mindre tall.

I et regneark kontrollerer vi svaret ved å skrive =rest(6^13; 11), i GeoGebra ved å skrive mod(6^13,11). I appen fyller vi ut 6 for a, 13 for b, 11 for n, og klikker på "Finn rest".

Tilbake til oppgaven

Kongruenslikninger

Oppgave 1:

Vi skal modellere problemene under med kongruenslikninger.

  1. En friidrettsutøver løper 300-meters intervaller på en 400-meters bane, og står stille og hviler mellom hvert intervall. Når hun gir seg, har hun passert målstreken med 100 meter. Hvor mange intervaller kan hun ha løpt.
    Likningen blir $300x \equiv 100 \, (mod \; 400)$, der  $x$ representerer antall 300-metere.
     
  2. En forstadsbane passerer et stoppested første gang klokka 05:00, deretter hvert 12. minutt. Etter hvor mange passeringer passerer banen deretter på hele klokkeslett?
    Likningen blir $12x \equiv 0 \, (mod \; 60)$, der $x$ representerer antall passeringer. Vi regner her modulo 60 fordi det er 60 minutter i en time. "Hel time" betyr da at antall minutter er kongruente med 0 modulo 60.

Tilbake til oppgaven

Oppgave 2:

Vi skal foreslå en situasjon som kan modelleres med kongruenslikningen $4x \equiv 0 \, (mod \; 10)$.

For eksempel: På et skolekjøkken har hver arbeidsgruppe brukt 4 dl melk til en oppskrift. Hvor mange grupper kan det ha vært på skolekjøkkenet hvis det er brukt et helt antall kartonger med melk à 10 dl?

Tilbake til oppgaven

Oppgave 3:

Vi skal avgjøre om følgende kongruenslikninger har løsning, og i så fall hvor mange restklasser de har løsninger i:

  1. $4x \equiv 8 \, (mod \; 10)$
    Vi har $SFF(4, 10) = 2$. $2 \mid 8$, så likningen har løsning i 2 restklasser.
     
  2. $3x \equiv 8 \, (mod \; 10)$
    Vi har $SFF(3, 10) = 1$. $1 \mid 8$, så likningen har løsning i 1 restklasse.
  3. $4x \equiv 9 \, (mod \; 10)$
    Vi har $SFF(4, 10) = 2$. $2 \nmid 9$, så likningen har ingen løsning.

  4. $84x \equiv 108 \, (mod \; 12)$
    Vi har $SFF(84, 12) = 12$. $12 \mid 108$, så likningen har løsning i 12 restklasser, det vil si samtlige restklasser modulo 12. Siden alle tall i disse restklassene også er løsninger, betyr det at alle hele tall er løsning av denne kongruenslikningen.

Tilbake til oppgaven

Oppgave 4:

Vi skal forenkle kongruenslikningen $x + 4 \equiv 13 – 5x \, (mod \; 5)$.

Vi starter med å flytte $4$ over på høyre side, $-5x$ over på venstre side og skifte fortegn:
$x + 5x \equiv 13 – 4\, (mod \; 5)$

Så trekker vi sammen like ledd:
$6x \equiv 9 \, (mod \; 5)$

Så erstatter vi $6$ med $6 – \lfloor \frac{\displaystyle 6}{\displaystyle 5} \rfloor \cdot 5 = 6 – 1 \cdot 5 = 1$ og $9$ med $9 – \lfloor \frac{\displaystyle 9}{\displaystyle 5} \rfloor \cdot 5 = 9 – 1 \cdot 5 = 4$. Så svaret blir

$x \equiv 4\, (mod \; 5)$

Tilbake til oppgaven

Oppgave 5:

Vi skal finne alle restklasser som inneholder løsninger til likningen $6x \equiv 12 \, (mod \; 9)$.

Vi har at $SFF(6, 9) = 3$ og $3 \mid 12$, så likningen har løsninger i 3 restklasser.

Det største tallet vi kan dividere med på begge sider av kongruenstegnet er $SFF(6, 12) = 6$. Da må vi samtidig dividere modulus med $d = SFF(6, 9) = 3$. Så vi får

$x \equiv 2 \, (mod \; 3)$

$x = 2$ er en løsning, og $d = 3$, så de tre restklassene blir

$x_0 = 2 + 0 \cdot \frac{\displaystyle 9}{\displaystyle 3} = 2$

$x_1 = 2 + 1 \cdot \frac{\displaystyle 9}{\displaystyle 3} = 5$

$x_2 = 2 + 2 \cdot \frac{\displaystyle 9}{\displaystyle 3} = 8$.

Tilbake til oppgaven

Oppgave 6:

Vi skal få $x$ til å stå alene på venstre side i kongruenslikningen $4x \equiv 3 \, (mod \; 7)$.

Siden $SFF(4, 7) = 1$, vet vi at $4$ har en multiplikativ invers modulo $7$. Vi går inn i raden med $a=4$ i tabellen "modulo 7" og finner at inversen er $\overline a = 2$.

Vi multipliserer med $2$ på begge sider av kongruenstegnet og får $(4 \cdot 2)x \equiv 3 \cdot 2 \, (mod \; 7) \Rightarrow x \equiv 6 \, (mod \; 7)$.

Tilbake til oppgaven

Oppgave 7:

Vi skal løse 2 kongruenslikninger hvis de er løsbare:

  1. $270x – 10 \equiv -130 + 14x \, (mod \; 44)$.
    Vi starter med å flytte $14x$ over på venstre side og $-10$ over på høyre side, skifte fortegn og trekke sammen. Vi får
    $256x \equiv -120 \, (mod \; 44)$.
    Så erstatter vi $256$ med $256 – \lfloor \frac{\displaystyle 256}{\displaystyle 44} \rfloor \cdot 44 = 256 – 5 \cdot 44 = 36$.
    Og vi erstatter $-120$ med $-120 – \lfloor \frac{\displaystyle -120}{\displaystyle 44} \rfloor \cdot 44 = -120 – (-3) \cdot 44 = 12$ Vi får
    $36x \equiv 12 \, (mod \; 44)$.
    Vi finner $d = SFF(a, n) = SFF(36, 44) = 4$. Siden $4 \mid 12$, har likningen løsninger i $4$ restklasser.
    Vi dividerer alle ledd med $4$ og får
    $9x \equiv 3 \, (mod \; 11)$.
    Vi undersøker om likningen kan forkortes, og finner $c = SFF(a, b) = SFF(9, 3) = 3$. Vi dividerer $a$ og $b$ med $3$ og får
    $3x \equiv 1 \, (mod \; 11)$.
    Vi går inn i raden med $a = 3$ i tabellen "Modulo 11" og finner at inversen er $\overline a = 4$.
    Vi multipliserer med $4$ på begge sider av kongruenstegnet og får $(3 \cdot 4)x \equiv 1 \cdot 4 \, (mod \; 11)$.
    Vi har altså følgende løsning:
    $x \equiv 4 \, (mod \; 11)$.
    Ut fra denne løsningen finner vi de fire restklassene med løsninger i den opprinnelige likningen modulo $44$:
    $x_0 = 4 + 0 \cdot 11 = 4 \\
    x_1 = 4 + 1 \cdot 11 = 15 \\
    x_2 = 4 + 2 \cdot 11 = 26 \\
    x_3 = 4 + 3 \cdot 11 = 37$

    Så løsningene til kongruenslikningen er $x \equiv 4, 15, 26, 37 \, (mod \; 44)$.
  2. $-108x – 100 \equiv 229 + 10x \, (mod \; 44)$.
    Vi starter med å flytte $10x$ over på venstre side og $-100$ over på høyre side, skifte fortegn og trekke sammen. Vi får
    $-118x \equiv 329 \, (mod \; 44)$.
    Så erstatter vi $-118$ med $-118 – \lfloor \frac{\displaystyle -118}{\displaystyle 44} \rfloor \cdot 44 = -118 – (-3) \cdot 44 = 14$.
    Og vi erstatter $329$ med $329 – \lfloor \frac{\displaystyle 329}{\displaystyle 44} \rfloor \cdot 44 = 329 – 7 \cdot 44 = 21$. Vi får
    $14x \equiv 21 \, (mod \; 44)$.
    Vi finner $d = SFF(14, 44) = 2$.
    Siden $2 \nmid 21$, har likningen ingen løsning.

​Tilbake til oppgaven

Oppgave 8:

Vi skal løse kongruenslikningen $60x \equiv -50 \, (mod \; 7)$ på en enkel måte.

Vi ser at vi kan dividere med $10$ på begge sider. Siden $SFF(a, n) = SFF(60, 7) = 1$, trenger vi ikke endre modulus. Vi får

$6x \equiv -5 \, (mod \; 7)$.

Vi benytter så at $6 \equiv -1 \, (mod \; 7)$ og skriver om til

$-x \equiv -5 \, (mod \; 7)$.

Vi multipliserer med $-1$ på begge sider og får

$x \equiv 5 \, (mod \; 7)$.

​Tilbake til oppgaven

Oppgave 9:

Vi har to bøtter uten målestreker på henholdsvis 5 og 7 liter og skal måle opp akkurat 1 liter.

  1. Vi skal sette opp en kongruenslikning som uttrykker dette problemet.
    Etter modell fra eksempel 13, ser vi at det blir
    $5x \equiv 1 \, (mod \; 7)$
     
  2. Vi skal vise at likningen har løsning, og løse den.
    Vi har $SFF(a, n) = SFF(5, 7) = 1$, så likningen har løsning i én restklasse.
    I tabellen over multiplikative inverser modulo 7, ser vi at 3 er en multiplikativ invers til 5 modulo 7. Vi multipliserer med 3 på begge sider av kongruenstegnet og får
    $x \equiv 3 \, (mod \; 7)$
     
  3. Vi ser at operasjonen må gå i tre trinn, siden $x = 3$. En trinnvis beskrivelse er er vist under, tallene i parentes forteller hvor mye det er igjen i bøttene.
    Vi heller over 5 liter. (0, 5).
    Vi heller over 5 liter, med en pause mens vi tømmer den store bøtta. (0, 3).
    Det er nå plass til 4 liter i den store bøtta. Vi heller over 4 liter og står igjen med 1 liter i den lille.

Tilbake til oppgaven

Diofantiske likninger

Oppgave 1:

Vi skal avgjøre om den lineære diofantiske likningen $21x + 14y = 147$ er løsbar, og i så fall finne en løsning.

Vi har at en lineær diofantisk likning, $ax + by = c$, har løsning hvis $SFF(a, b) \, | \, c$. Her har vi $SFF(a, b) = SFF(21, 14) = 7$ og $7 \mid 147$, så likningen har løsning.

Vi løser likningen ved å omforme den til en kongruenslikning. Vi kan velge å regne modulo $14$ og løse med hensyn på $x$, eller å regne modulo $21$ og løse med hensyn på $y$. Vi har sagt at det ofte lønner seg å velge metoden som gir lavest modulus, så vi viser utregningen modulo $14$ først, men vi viser også utregningen modulo $21$.

Løsning modulo 14:

Vi flytter y-leddet over på høyre side:
$21x = 147 – 14y$.

Vi skriver om til en kongruenslikning modulo $14$:
$21x \equiv 147\; (mod \; 14)$.

Vi erstatter $21$ med $21 – \lfloor \frac{\displaystyle 21}{\displaystyle 14} \rfloor \cdot 14 = 21 – 1 \cdot 14 = 7$ og
$147$ med $147 – \lfloor \frac{\displaystyle 147}{\displaystyle 14} \rfloor \cdot 14 = 147 – 10 \cdot 14 = 7$. Så vi får:
$7x \equiv 7\; (mod \; 14)$.

Vi bryr oss ikke om å bruke flere formelle metoder, for vi ser direkte at $x = 1$ er en løsning.

Den tilhørende løsningen for $y$ blir $y = \frac{\displaystyle 147 -21 \cdot 1}{\displaystyle 14} = 9$.

Så vi ender opp med tallparet $(1, 9)$.

Løsning modulo 21:

Vi flytter x-leddet over på høyre side:
$14y = 147 – 21x$.

Vi skriver om til en kongruenslikning modulo $21$:
$14y \equiv 147\; (mod \; 21)$.

Vi erstatter $147$ med $147 – \lfloor \frac{\displaystyle 147}{\displaystyle 21} \rfloor \cdot 21 = 147 – 7 \cdot 21 = 0$. Så vi får:
$14y \equiv 0\; (mod \; 21)$.

Vi bryr oss ikke om å bruke flere formelle metoder, for vi ser direkte at $y = 0$ er en løsning.

Den tilhørende løsningen for $x$ blir $x = \frac{\displaystyle 147 – 14 \cdot 0}{\displaystyle 21} = 7$.

Så vi ender opp med tallparet $(7, 0)$.

Tilbake til oppgaven

Oppgave 2:

Vi skal finne et uttrykk for alle løsninger til den lineære diofantiske likningen fra oppgave 1, $21x + 14y = 147$.

Et uttrykk for den generelle løsningen er

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k$
og
$y_k = y_0 – \frac{\displaystyle a}{\displaystyle d}k$,

der $x_0$ og $y_0$ er én spesiell løsning, $k$ er et helt tall, og $d = SFF(a, b)$.

I vår oppgave har vi $a = 21$, $b = 14$ og $d = SFF(21, 14) = 7$.

Da vi løste modulo $14$, fikk vi 

$x_0 = 1, y_0 = 9$. Setter vi dette inn, får vi

$x_k = 1 + \frac{\displaystyle 14}{\displaystyle 7}k = 1 + 2k$
og
$y_k = 9 – \frac{\displaystyle 21}{\displaystyle 7}k = 9 – 3k$.

Da vi løste modulo $21$, fikk vi

$x_0 = 7, y_0 = 0$. Setter vi dette inn, får vi

$x_k = 7 + \frac{\displaystyle 14}{\displaystyle 7}k = 7 + 2k$
og
$y_k = 0 – \frac{\displaystyle 21}{\displaystyle 7}k = – 3k$.

Tilbake til oppgaven

Oppgave 3:

Vi skal finne alle ikke-negative løsninger til den lineære diofantiske likningen fra oppgave 1 og 2, $21x + 14y = 147$.

Da vi løste modulo $14$, fikk vi følgende uttrykk for den generelle løsningen:

$x_k = 1 + 2k$
og
$y_k = 9 – 3k$.

Vi må ha
$1 + 2k \ge 0 \Rightarrow k \ge -\frac{\displaystyle 1}{\displaystyle 2}$
og
$9 – 3k \ge 0 \Rightarrow k \le 3$.

$-\frac{\displaystyle 1}{\displaystyle 2} \le k \le 3$, det vil si $k \in \{0, 1, 2, 3 \}$. Og vi får løsningene

$(1 + 2 \cdot 0, 9 – 3 \cdot 0), \;\; (1 + 2 \cdot 1, 9 – 3 \cdot 1), \;\; (1 + 2 \cdot 2, 9 – 3 \cdot 2), \;\; (1 + 2 \cdot 3, 9 – 3 \cdot 3)$, altså

$(1, 9), (3, 6), (5, 3), (7,0)$.

Da vi løste modulo $21$, fikk vi følgende uttrykk for den generelle løsningen:

$x_k = 7 + 2k$
og
$y_k= – 3k$.

Vi må ha
$7 + 2k \ge 0 \Rightarrow k \ge -\frac{\displaystyle 7}{\displaystyle 2}$
og
$- 3k \ge 0 \Rightarrow k \le 0$.

$-\frac{\displaystyle 7}{\displaystyle 2} \le k \le 0$, det vil si $k \in \{-3, -2, -1, 0 \}$. Og vi får løsningene

$(7 + 2 (-3), – 3(-3)), \;\; (7 + 2 (-2), (-3)(-2)), \;\; (7 + 2 (-1), (-3)(-1)), \;\; (7 + 2 (0), (-3)0)$, altså

$(1, 9), (3, 6), (5, 3), (7,0)$.

Som ventet fikk vi samme resultat i begge tilfeller.

Tilbake til oppgaven

Oppgave 4:

Vi skal løse likningen fra oppgave 1, 2 og 3, $21x + 14y = 147$, som en vanlig likning med hensyn på $y$, tegne grafen i GeoGebra og plotte inn løsningene fra oppgave 3.

Vi flytter $21x$ over til høyre side med fortegnsskifte, dividerer med $14$ på begge sider av likhetstegnet og får

$y = -\frac{\displaystyle 3}{\displaystyle 2}x + \frac{\displaystyle 21}{\displaystyle 2}$.

Vi åpner GeoGebra og skriver -3x/2 + 21/2 i inntastingsfeltet, deretter (1, 9), (3, 6), (5, 3) og (7,0).

GeoGebra lager plottet vist under:

Heltallsløsninger av likningen 21x + 14y = 147

Tilbake til oppgaven

Oppgave 5:

En snekker lager krakker med 3 bein og bord med 4 bein. En dag har han brukt opp 33 bein, og vi skal finne ut hvor mange krakker og bord han kan ha laget.

Kaller vi antall krakker for $x$ og antall bord for $y$, vil følgende likning uttrykke dette problemet:

$3x + 4y = 33$.

Fordi han bare kan ha laget et helt antall krakker og bord, finner vi løsningen ved å betrakte dette som en diofantisk likning.

Siden $SFF(a, b) = SFF(3, 4) = 1$, har likningen løsning. (Vi dropper å presisere at $1 \mid 33$, for $1$ går opp i alle tall).

Vi velger å regne modulo $3$. Vi flytter x-leddet over på høyre side og får
$4y = 33 -3x$.

Gjort om til kongruenslikning blir det
$4y \equiv 33 \; (mod \; 3)$.

Nå har vi så mye trening at vi direkte ser at $4 \equiv 1 \; (mod \; 3)$ og $33 \equiv 0 \; (mod \; 3)$. Hvis ikke, kan vi regne det ut ved hjelp av formelen vi har lært for å bytte ut tall med mindre, kongruente tall.

Så vi får kongruenslikningen
$y \equiv 0 \; (mod \; 3)$.

Det betyr at $y = 0$ er en løsning.

Den tilhørende løsningen for $x$ blir $x = \frac{\displaystyle 33 – 4 \cdot 0}{\displaystyle 3} = 11$.

Så en mulighet er at snekkeren laget 11 krakker og ingen bord.

Så skal vi se hvilke andre muligheter som finnes og henter fram uttrykket for den generelle løsningen av en diofantisk likning:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k$
og
$y_k = y_0 – \frac{\displaystyle a}{\displaystyle d}k$.

der $x_0$ og $y_0$ er én spesiell løsning, $k$ er et helt tall, og $d = SFF(a, b)$.

I vår oppgave har vi $a = 3$, $b = 4$ og $d = SFF(3, 4) = 1$. Og vi fant $x_0 = 11$ og $y_0 = 0$, så vi får

$x_k = 11 + \frac{\displaystyle 4}{\displaystyle 1}k= 11 + 4k$
og
$y_k = 0 – \frac{\displaystyle 3}{\displaystyle 1}k = -3k$.

Snekkeren kan ikke ha laget et negativt antall krakker og bord. Vi må derfor ha at

$11 + 4k \ge 0 \Rightarrow k \ge -\frac{\displaystyle 11}{\displaystyle 4} \approx -2,75$
og
$-3k \ge 0 \Rightarrow k \le 0$.

$-2,75 \le k \le 0$, det vil si $k \in \{-2, -1, 0 \}$. Og vi får løsningene

$(11 + 4(-2), -3(-2)), \;\; (11 + 4(-1), -3(-1)), \;\; (11 + 4 \cdot 0, -3 \cdot 0)$,

altså $(3, 6), (7, 3), (11, 0)$.

Så snekkeren kan ha laget 3 krakker og 6 bord, 7 krakker og 3 bord og 11 krakker og ingen bord.

Tilbake til oppgaven

Oppgave 6:

Vi skal finne en løsning til den diofantiske likningen $11x + 3y = 1$ ved hjelp avEuklids algoritme baklengs.

Vi starter med å bruke Euklids algoritme til å finne $SFF(11, 3)$:

$\begin{align}11 &= 3 \cdot 3 + 2\\
3 &= 1 \cdot 2  + 1 \\
2 &= 2 \cdot 1 + 0 \end{align}$

Vi dropper den siste linja, i de andre uttrykker vi resten, $r$, som en lineær kombinasjon av $a$ og $b$, markert med brunt:

$\begin{align}2 &= {\color{brown}{11}} – 3 \cdot {\color{brown}{3}} \\
1 &= {\color{brown}{3}} – 1 \cdot {\color{brown}{2}} \\
\end{align}$

I siste linje erstatter vi så 2-tallet med uttrykket i linja over

$1 = {\color{brown}{3}} – 1 \cdot {\color{brown}{2}}  \\
\Downarrow \\
1 = {\color{brown}{3}} – 1 \cdot ({\color{brown}{11}} – 3 \cdot {\color{brown}{3}})  \\
\Downarrow \\
1 =  -1 \cdot {\color{brown}{11}} + 4 \cdot {\color{brown}{3}}$

Det betyr at $x = -1$, $y = 4$ er en løsning til den diofantiske likningen $11x + 3y = 1$, som vi startet med.

Tilbake til oppgaven

Oppgave 7:

Vi skal finne en løsning til likningen $21x + 14y = 147$ ved hjelp av Eulers algoritme baklengs.

Vi har $SFF(a, b) = SFF(21, 14) = 7$. $7 \mid 147$, så likningen har løsning. Vi forkorter med $7$ og får

$3x + 2y = 21$.

Vi ser på $3x + 2y = 1$, der vi har satt $c = 1$.

Vi starter med å bruke Euklids algoritme til å finne $SFF(3, 2)$:

$\begin{align}3 &= 1 \cdot 2 + 1\\
2 &= 2 \cdot 1 + 0 \end{align}$

Vi dropper den siste linja, i nest siste uttrykker vi resten, $r$, som en lineær kombinasjon av $a$ og $b$, markert med brunt:

$1 = 1 \cdot {\color{brown}{3}} – 1 \cdot {\color{brown}{2}}$

$x = 1$, $y = -1$ er en løsning til $3x + 2y = 1$.

Så multipliserer vi med $21$ for å få løsningene til $3x + 2y = 21$, og får $x = 21 \cdot 1 = 21$, $y = 21 \cdot (-1) = -21$.

$x = 21$, $y = -21$ er da også en løsning til den opprinnelige likningen $21x + 14y = 147$.

Vi fikk ikke samme svar som i oppgave 1, men går vi videre og finner et generelt uttrykk for løsningene, vil vi se at vi får samme resultat.

Tilbake til oppgaven

Pytagoreiske tripler

Oppgave 2:

Vi skal avgjøre om følgende er primitive pytagoreiske tripler:

  1. $(5, 12, 13)$.
    $5^2 + 12^2 = 169$, og $13^2 = 169$, så dette er et pytagoreisk trippel. $5, 12 \text{ og } 13$ har heller ingen felles faktorer, så det er et primitivt pytagoreisk trippel.
     
  2. $(10, 24, 26)$.
    $10^2 + 24^2 = 676$ og $26^2 = 676$, så dette er et pytagoreisk trippel. Men $10, 24 \text{ og } 26$ har $2$ som felles faktor, så det er ikke et primitivt pytagoreisk trippel.
     
  3. $(7, 24, 29)$.
    $7^2 + 24^2 = 625$ og $29^2 = 841$, så dette er ikke et pytagoreisk trippel i det hele tatt.

Tilbake til oppgaven

Oppgave 3:

Vi skal finne $y$ og $z$ slik at $(11, y, z)$ er et primitivt pytagoreisk trippel der $z = y + 1$.

Vi setter $x = 11$ og $z = y + 1$ inn i $x^2 + y^2 = z^2$:

$11^2 + y^2 = (1 + y)^2 \\
\Downarrow \\
11^2 + y^2 = 1^2 + 2y + y^2 \\
\Downarrow \\
2y = 121 – 1 \\
\Downarrow \\
y = 60$

Og, som oppgitt, har vi $z = y + 1$, så $z = 60 + 1 = 61$.

$(11,60,61)$ er det ønskede, primitive pytagoreiske trippelet.

Tilbake til oppgaven

Oppgave 4:

Vi skal argumentere for at de pytagoreiske triplene Platons generator, $x = 4n, y = 4n^2 – 1, z = 4n^2 + 1$, produserer er primitive.

I triplene som Platons generator produserer er $z – y = 2$, og tallene som går opp i $2$ er $2$ og $1$. $z$ og $y$ har derved en felles faktor, $k = 2$ som kan divideres bort hvis de er partall. Men vi ser at $z = 4n^2 + 1$ har oddetallsformen $2m + 1$. $z$ og $y$ er derfor alltid oddetall. Siden eneste mulige felles faktor var $2$, har de derved ingen felles faktor som kan divideres bort. Triplene er derfor primitive.

Tilbake til oppgaven

Oppgave 5:

Basert på generatoren for primitive, pytagoreiske tripler, $x = 2st$, $y = s^2 – t^2$ og $z = s^2 + t^2$, skal vi finne de 10 minste triplene. Disse vises i figuren under. Her settes $s$ i tur lik alle naturlige tall større enn $1$. ($s$ må være større enn $1$ for at $t$ skal kunne være større enn $0$). Hver verdi av $s$ kombineres med alle tillatte verdier av $t$, det vil si $t$ som er større enn $0$ men mindre enn $s$, ikke har andre felles faktorer med $s$ enn $1$, og er partall hvis $s$ er oddetall og oddetall hvis $s$ er partall.

Utfylt tabell med genererte pytagoreiske tripler

Tilbake til oppgaven

Oppgave 7:

Vi skal avgjøre om følgende kan skrives som en sum av to kvadrattall:

  1. $20$
    $20$ primtallsfaktoriseres som $20 = 2 \cdot 2 \cdot 5$.
    Ingen av primtallsfaktorene gir rest $3$ når de divideres med $4$.
    $20$ kan derfor skrives som en sum av kvadrattall. $20 = 4^2 + 2^2$.
     
  2. $38$
    $38$ primtallsfaktoriseres som $38 = 2 \cdot 19$.
    $19$ gir rest $3$ ved divisjon med $4$ og forekommer et odde ($1$) antall ganger. $38$ kan derfor ikke skrives som en sum av kvadrattall.
     
  3. $18$
    $18$ primtallsfaktoriseres som $18 = 2 \cdot 3 \cdot 3$.
    $2$ gir ikke rest $3$ ved divisjon med $4$, men det gjør $3$. Imidlertid forekommer $3$ et par ($2$) antall ganger. $18$ kan derfor skrives som en sum av kvadrattall. $18 = 3^2 + 3^2$.

​Tilbake til oppgaven

Oppgave 8:

Vi skal forklare at teoremet "Et odde primtall kan skrives som en sum av to kvadrattall hvis og bare hvis vi får rest 1 når vi dividerer det med 4" kan utledes av teoremet "Et naturlig tall kan skrives som en sum av to kvadrattall hvis og bare hvis ingen av tallets primtallsfaktorer gir rest 3 når vi dividerer den med 4, med mindre faktoren forekommer et par antall ganger":

Et odde primtall vil alltid ha en primtallsfaktor som forekommer et odde antall ganger, nemlig tallet selv. Hvis tallet skal kunne skrives som en sum av kvadrattall, må det altså ikke gi rest 3 ved divisjon med 4. Et oddetall gir alltid rest 1 eller 3 ved divisjon med 4. Å si at divisjonen ikke gir rest 3 er derfor det samme som å si at divisjonen gir rest 1, slik teoremet om odde primtall gjør.

​Tilbake til oppgaven

Kryptografi

Oppgave 1:

Vi skal bruke multiplikasjon modulo $29$ til å kryptere og dekryptere bokstaven 'H' med krypteringsnøkkel $r=10$ og dekrypteringsnøkkel $\overline r=3$.

Bokstaven 'H' symboliseres med x = 8, ifølge kodetabellen. Krypteringen blir

$rx \equiv 10 \cdot 8 \equiv 80 \equiv 22 \; (mod \; 29)$. Vi får altså k = 22, som tilsvarer 'V'.

Dette finner vi ved å skrive =rest(10*8; 29) i et regneark eller mod(10*8, 29) i inntastingsfeltet i GeoGebra.

Dekrypteringen blir

$\overline r k \equiv 3 \cdot 22 \equiv 66 \equiv 8 \; (mod \; 29)$. Vi får altså x = 8, som tilsvarer 'H', som vi startet med.

Dette finner vi ved å skrive =rest(3*22; 29) i et regneark eller mod(3*22, 29) i inntastingsfeltet i GeoGebra.

Tilbake til oppgaven

Oppgave 2:

Vi skal bruke eksponentiering modulo n til å kryptere og dekryptere bokstaven 'U' med krypteringsnøkkel ( r = 27, n = 187) og  dekrypteringsnøkkel (s = 83, n = 187).

Bokstaven 'U' symboliseres med x = 21, ifølge kodetabellen. Krypteringen blir

$x^{\large r} \equiv 21^{27} \equiv 98 \; (mod \; 187)$. 'U'-en krypteres som k = 98.

Dekrypteringen blir

$k^{\large s} \equiv 98{83} \equiv 21 \; (mod \; 187)$. Vi får x = 21, som tilsvarer 'U', som vi startet med.

Oppgave 3:

Vi vet at $n = 1591$ er et produkt av primtallene $37$ og $43$, og skal beregne $\phi(n)$.

Vi får $\phi(n) = (37 – 1)(43 – 1) = 1512$.

Tilbake til oppgaven

Oppgave 4:

Vi skal bruke RSA-systemet med krypteringsnøkkel (13, 77) og dekrypteringsnøkkel (37, 77)  til å kryptere og dekryptere bokstaven 'X' .

'X' symboliseres med 24 ifølge kodetabellen.

Vi krypterer ved å beregne $24^{13} \equiv 52 \, (mod \; 77)$. Denne beregningen gjør vi ved hjelp av appen finne_rest, ved å fylle ut "a = 24", "b = 13" og "n = 77" og klikke på "Beregn". Vi får svaret 52.

$k = 52$.  'X' blir altså kryptert til 52.

Vi dekrypterer ved å beregne $52^{37} \equiv 24 \, (mod \; 77)$ på samme måte. Vi ender altså opp med 24, som tilsvarer 'X', som vi startet med.

Tilbake til oppgaven

Oppgave_5:

Det er umulig å gi noe komplett løsningsforslag, siden utregningene avhenger av valget av $n$ og $r$. Men her er noen sjekkpunkter:

  • $n$ er valgt som produktet av to forskjellige primtall, $p$ og $q$.
     
  • $\phi(n)$ er beregnet som $(p – 1)(q – 1)$.
     
  • $r < n$ og $SFF(r, \phi(n)) = 1$.
     
  • $rs \equiv 1 \, (mod \; \phi(n))$.
     
  • Kryptering, $x \rightarrow k$ etterfulgt av dekryptering $k \rightarrow x$, gir tilbake verdien vi startet med.

Tilbake til oppgaven