Kategori: Tallteori

Diofantiske likninger

Oppgave 1:

Vi skal avgjøre om de diofantiske likningene
4x + 12y = 16
og
3x + 12y = 16
har løsning.

En diofantisk likning ax + by = c har løsning hvis og bare hvis SFF(a, b) | c.

I likningen 4x + 12y = 16 får vi SFF(a, b) = SFF(4, 12) = 4. Siden 4 | 16, har likningen løsning.

I likningen 3x + 12y = 16 får vi SFF(a, b) = SFF(3, 12) = 3. Siden 3 ∤ 16, har ikke likningen løsning.

Tilbake til oppgaven

Oppgave 2:

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, n) | c. Her har vi SFF(a, n) = SFF(21, 14) = 7 og 7 | 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 ≡ 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 ≡ 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 ≡ 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 ≡ 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), som er det vi skulle.

Tilbake til oppgaven

Oppgave 3:

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

Et uttrykk for den generelle løsningen til en diofantisk likning, ax + by = c, er

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

der x₀ og y₀ 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₀ = 1, y₀ = 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₀ = 7, y₀ = 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 4:

Vi skal finne alle ikke-negative løsninger til den lineære diofantiske likningen fra oppgave 2 og 3, 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$.

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

(1 + 2 · 0, 9 − 3 · 0), (1 + 2 · 1, 9 − 3 · 1), (1 + 2 · 2, 9 − 3 · 2), (1 + 2 · 3, 9 − 3 · 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$.

Så $-\frac{\displaystyle 7}{\displaystyle 2} \le k \le 0$, det vil si k ∈ {−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 5:

Vi skal løse likningen fra oppgave 2, 3 og 4, 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:

Tilbake til oppgaven

Oppgave 6:

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 | 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 ≡ 33 (mod 3).

Nå har vi så mye trening at vi direkte ser at 4 ≡ 1 (mod 3) og 33 ≡ 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 ≡ 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₀ og y₀ 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₀ = 11 og y₀ = 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$.

Så −2,75 ≤ k ≤ 0, det vil si k ∈ {−2, −1, 0}. Og vi får løsningene

(11 + 4(−2), −3(−2)), (11 + 4(−1), −3(−1)), (11 + 4 · 0, −3 · 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 7:

Vi skal finne en løsning til den diofantiske likningen 11x + 3y = 1 ved hjelp av Euklids 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 8:

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

Vi har SFF(a, b) = SFF(21, 14) = 7. 7 | 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 · 3 − 1 · 2

Så 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 · 1 = 21, y = 21 · (−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² + 12² = 169, og 13² = 169, så dette er et pytagoreisk trippel. 5, 12 og 13 har heller ingen felles faktorer, så det er et primitivt pytagoreisk trippel.
    
2. (10, 24, 26).
   10² + 24² = 676 og 26² = 676, så dette er et pytagoreisk trippel. Men 10, 24 og 26 har 2 som felles faktor, så det er ikke et primitivt pytagoreisk trippel.
    
3. (7, 24, 29).
   7² + 24² = 625 og 29² = 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² + y² = z²:

11² + y² = (1 + y)²
⇓
11² + y² = 1² + 2y + y²
⇓
2y = 121 − 1
⇓
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² − 1, z = 4n² + 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² + 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² − t² og z = s² + t², 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.

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 · 2 · 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. 38
   38 primtallsfaktoriseres som 38 = 2 · 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 · 3 · 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² + 3².

​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 har krypteringsnøkkel r = 10.

Vi skal først verifisere at r = 3 da er en dekrypteringsnøkkel ved multiplikasjon modulo 29 .

Krypterings- og dekrypteringsnøkkel må være multiplikative inverser, og vi har

r · r ≡ 3 · 10 ≡ 30 ≡ 1 (mod 29).

r = 3 er altså en dekrypteringsnøkkel.

Så skal vi bruke r og r til å kryptere og dekryptere bokstaven H.

Bokstaven H kodes med u = 8, ifølge kodetabellen. Krypteringen blir

k ≡ ru ≡ 10 · 8 ≡ 80 ≡ 22 (mod 29), altså V, ifølge kodetabellen.

Dekryptering blir

u ≡ r k ≡ 3 · 22 ≡ 66 ≡ 8 (mod 29), altså H, som vi startet med.

Utregningene gjør vi ved å skrive =rest(10*8; 29) og =rest(3*22; 29) i et regneark eller mod(10*8, 29) og mod(3*22, 29) i inntastingsfeltet i GeoGebra.

Tilbake til oppgaven

Oppgave 2:

Vi skal først begrunne at krypteringsnøkkelen (9, 79) er gyldig til kryptering ved multiplikasjon, og at den tilhørende dekrypteringsnøkkelen blir (44, 79).

For at nøkkelen skal være gyldig, må vi ha at SFF(9, 79) = 1. Vi ser lett at dette er tilfelle, for den eneste primtallsfaktoren i 9 er 3, som ikke er en faktor i 79 fordi tverrsummen ikke er delelig med 3. Alternativt kan vi sjekke at vi får 1 når vi skriver sfd(9, 79) eller gcd(9, 79) i GeoGebra, eller =SFF(9; 79) i et regneark.

Vi skal videre vise at den tilhørende dekrypteringsnøkkelen blir (44, 79).

Krypterings- og dekrypteringsnøkkel må være multiplikative inverser ved gitt modulus, og vi har

r · r ≡ 44 · 9 ≡ 396 ≡ 1 (mod 79).

At 396 ≡ 1 (mod 79) finner vi ved å skrive =rest(396; 79) i et regneark eller mod(396, 79) i GeoGebra.

Vi skal så bruke disse nøklene til å kryptere og dekryptere bokstaven B.

Bokstaven B kodes med u = 2, ifølge kodetabellen. Krypteringen blir

k ≡ ru ≡ 9 · 2 ≡ 18 (mod 79).

Dekryptering blir

u ≡ r k ≡ 44 · 18 ≡ 792 ≡ 2 (mod 79), altså B, som vi startet med.

At 792 ≡ 2 (mod 79) finner vi ved å skrive =rest(792; 79) i et regneark eller mod(792, 79) i GeoGebra.

Tilbake til oppgaven

Oppgave 3:

Vi skal kode B med u = 2, og bruke eksponentiering til å kryptere med nøkkel (5, 19).

Vi får

k ≡ 2⁵ ≡ 32 ≡ 13 (mod 19). B krypteres som k = 13.

Utregningene gjør vi ved å skrive =rest(2^5; 19) i et regneark eller mod(2^5, 19) i inntastingsfeltet i GeoGebra.

Tilbake til oppgaven

Oppgave 4:

Vi skal bruke eksponentiering til å kryptere G med nøkkel (25, 99).

G kodes med u = 7, så vi må beregne

k ≡ 7²⁵ (mod 99).

Å finne resten når 7²⁵ divideres med 99 lar seg ikke gjøre i Excel eller GeoGebra fordi 7²⁵ er et for høyt tall. 

I stedet bruker vi teknikken med toerpotenser.

Vi ser at 25 = 1 + 8 + 16.

Så 7²⁵ = 7^{1 + 8 + 16} = 7¹ · 7⁸ · 7¹⁶.

Og vi får

7 ≡ 7 (mod 99)

7² ≡ 49 (mod 99)

7⁴ ≡ (7²)² ≡ 49² ≡ 2401 ≡ 25 (mod 99)

7⁸ ≡ (7⁴)² ≡ 25² ≡ 625 ≡ 31 (mod 99)

7¹⁶ ≡ (7⁸)² ≡ 31² ≡ 961 ≡ 70 (mod 99)

Så 7²⁵ ≡ 7 · 31 · 70 ≡ 15190 ≡ 43 (mod 99).

G krypteres som k = 43.

Til utregningene underveis kan vi bruke GeoGebra eller et regneark, siden bare tall i en størrelsesorden disse verktøyene håndterer uten problemer er involvert. For eksempel finner vi at 2401 ≡ 25 (mod 99) ved å skrive mod(2401, 99) i GeoGebra eller =rest(2401; 99) i et regneark.

I appen for å beregne rest setter vi «a» = 7, «b» = 25, «n» = 99, og klikker på «Finn rest». Appen beregner at 7²⁵ ≡ 43 (mod 99). Huker vi av for «Vis utregning», vises samme utregning som vi gjorde for hånd.

Tilbake til oppgaven

Oppgave 5:

Vi skal bruke dekrypteringsnøkkelen (11, 19) til å dekryptere k = 13.

Vi beregner da

u ≡ 13¹¹ ≡ 1792160394037 ≡ 2 (mod 19).

Vi kan bruke funksjonen mod i GeoGebra eller funksjonen rest i et regneark til utregningene.

Det var oppgitt at den ukrypterte verdien var u = 2, så svaret stemmer.

Tilbake til oppgaven

Oppgave 6:

Det er oppgitt at når en krypteringsnøkkel er (13, 77), er en dekrypteringsnøkkel (37, 77), og vi skal bruke dette til å kryptere og dekryptere bokstaven B, kodet med u = 2.

For å kryptere må vi beregne k ≡ u^r (mod n):

k ≡ 2¹³ ≡ 8192 ≡ 30 (mod 77).

B krypteres altså med k = 30.

Tallene i denne utregningen er så små at vi kan gjøre beregningene ved hjelp av funksjonen mod i GeoGebra eller funksjonen rest i et regneark.

For å dekryptere med nøkkel (37, 77) må vi beregne u ≡ k^s (mod n):

u ≡ 30³⁷ (mod 77).

Her er tallene så store at beregningene ikke kan gjøres i GeoGebra eller regneark, så vi bruker metoden med toerpotenser:

Vi ser at 37 = 1 + 4 + 32.

Så 30³⁷ = 30^{1 + 4 + 32} = 30¹ · 30⁴ · 30³².

Og vi får

30 ≡ 30 (mod 77)

30² ≡ 900 ≡ 53 (mod 77)

30⁴ ≡ (30²)² ≡ 53² ≡ 2809 ≡ 37 (mod 77)

30⁸ ≡ (30⁴)² ≡ 37² ≡ 1369 ≡ 60 (mod 77)

30¹⁶ ≡ (30⁸)² ≡ 60² ≡ 3600 ≡ 58 (mod 77)

30³² ≡ (30¹⁶)² ≡ 58² ≡ 3364 ≡ 53 (mod 77)

Så 30³⁷ ≡ 30 · 37 · 53 ≡ 58830 ≡ 2 (mod 77).

Vi er tilbake til u = 2, som representerer B, som vi startet med.

Tilbake til oppgaven

RSA-systemet

Oppgave 1:

Der er oppgitt at n = 1591 er et produkt av primtallene 37 og 43, og vi skal beregne φ(n).

Vi får φ(n) = (37 − 1)(43 − 1) = 36 · 42 = 1512.

Tilbake til oppgaven

Oppgave 2:

Vi skal modifisere dette regnearket til å gjøre utregningene i totient-teoremet for n = 2 · 7 = 14 i stedet for n = 3 · 5.

Når n = 2 · 7 har vi φ(n) = (2 − 1)(7 − 1) = 1 · 6 = 6.

Vi åpner regnearket og sletter siste rad, som gjelder a = 14, og ikke skal være med. Så går vi inn i celle B2, erstatter =REST(A2^8;15) med =REST(A2^6;14), og drar formelen nedover til og med B14. Tilsvarende går vi inn i celle D2 og erstatter =REST(C2;15) med =REST(C2;14), og drar formelen nedover til og med D14. Så bytter vi ut 8 med 6 og 15 med 14 i overskriftene, og endrer gulmarkering. Resultatet blir som vist under.

Åpne et regneark med tabellen vist over.

 

Tilbake til oppgaven

Oppgave 3:

Vi skal kryptere og dekryptere bokstaven Y med nøklene (13, 77) og (37, 77).

Y kodes med 25 ifølge kodetabellen.

Vi krypterer ved å beregne 25¹³ ≡ 60 (mod 77).

Beregningen gjorde vi med appen finne_rest, med «a» = 25, «b» = 13 og «n» = 77.

Så Y blir kryptert til 60.

Vi dekrypterer ved å beregne 60³⁷ ≡ 25 (mod 77).

Vi ender opp med 25, som tilsvarer Y, som vi startet med.

Beregningen gjorde vi med appen finne_rest, med «a» = 60, «b» = 37 og «n» = 77.

Tilbake til oppgaven

Oppgave 4:

Vi skal ta utgangspunkt i primtallene 13 og 19 og begrunne at r = 27 ikke vil være gyldig som del av en krypteringsnøkkel i RSA-systemet basert på disse primtallene, men at 25 vil være det.

Når n = 13 · 19 har vi φ(n) = (13 − 1)(19 − 1) = 12 · 18 = 216.

Vi har SFF(27, 216) = 27. Siden SFF(r, φ(n)) > 1, er ikke r = 27 gyldig.

Men vi har SFF(25, 216) = 1. r = 25 er derfor gyldig.

Vi skal så bruke r = 25 til å angi en krypteringsnøkkel, og beregne den tilhørende dekrypteringsnøkkelen.

Vi har n = 13 · 19 = 247.

Så krypteringsnøkkelen blir (25, 247).

For å finne dekrypteringsnøkkelen må vi beregne s slik at sr ≡ 1 (mod φ(n)). Altså

r · 25 ≡ 1 (mod 216).

Beregningen gjør vi i appen finne_invers, med «a» = 25, «n» = 216. Og vi får s = 121.

Så dekrypteringsnøkkelen blir (121, 247).

Så skal vi bruke krypterings- og dekrypteringsnøkkelen vi har funnet til å kryptere og dekryptere bokstaven Y.

Y kodes med 25 ifølge kodetabellen.

Vi krypterer ved å beregne 25²⁵ ≡ 142 (mod 247).

Beregningen gjorde vi med appen finne_rest, med «a» = 25, «b» = 25 og «n» = 247.

Så Y blir kryptert til 142.

Vi dekrypterer ved å beregne 142¹²¹ ≡ 25 (mod 247).

Vi ender opp med 25, som tilsvarer Y, som vi startet med.

Beregningen gjorde vi med appen finne_rest, med «a» = 142, «b» = 121 og «n» = 247.

Tilbake til oppgaven

Kongruens

Oppgave 1:

Vi skal avgjøre om tre påstander om kongruens er riktige. Vi benytter oss av at a ≡ b (mod n) hvis m | (a − b):

1. 65 ≡ 17 (mod 12)
   Vi får a − b = 65 − 17 = 48. Siden n = 12 | 48, er påstanden riktig.
    
2. −12 ≡ 18 (mod 5)
   Vi får a − b = −12 − 18 = −30. Siden n = 5 | −30, er påstanden riktig.
    
3. 42 ≡ 27 (mod 7)
   Vi får a − b = 42 − 27 = 15. Siden n = 7∤ 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 ≡ 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 ≡ −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 ≡ 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 ≡ b (mod 7), og skal avgjøre om a + c ≡ b + d (mod 7) når

1. 1. c = 5, d = 12
      Her er c ≡ d (mod 7) fordi 7 | (12 − 5) = 7. Følgelig er a + c ≡ b + d (mod 7).

   2. c = 8, d = 16
      Her er c ≢ d (mod 7) fordi 7 ∤ (16 − 8) = 8. Følgelig er a + c ≢ b + d (mod 7).

Tilbake til oppgaven

Oppgave 2:

Vi vet at 365 ≡ 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 · 365 + 366 ≡ 3 · 1 + 2 ≡ 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 ≡ 147 (mod 14) med henholdsvis 3 og 7 på begge sider av kongruenstegnet.

Vi har SFF(3, 14) = 1, og kan derfor dividere med 3 på begge sider uten å dividere modulus med noe.

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

Vi har SFF(7, 14) = 7. Når vi skal dividere med 7 på begge sider, må vi derfor dividere modulus med 7.

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

Tilbake til oppgaven

Oppgave 5:

Vi skal forkorte kongruensrelasjonen 126 ≡ 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 som vi dividerer med 18 på begge sider av kongruenstegnet dividere modulus med 2, og vi får 8 : 2 = 4.

Så relasjonen blir 7 ≡ 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 · 1 ≡ 2 (mod 5)
   2 · 2 ≡ 4 (mod 5)
   2 · 3 ≡ 6 ≡ 1 (mod 5)
   Så 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 · 1 ≡ 3 (mod 8)
   3 · 2 ≡ 6 (mod 8)
   3 · 3 ≡ 9 ≡ 1 (mod 8)
   Så 3 er en multiplikativ invers til 3 modulo 8.
    
3. a = 4, n = 8
   Vi har SFF(4, 8) = 4 ≠ 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. 1. 1234 · 364 = 224588.
      Vi bruker nierprøven. T(a) = T(1234) = 10, T(b) = T(364) = 13.
      Vi har altså at T(a) · T(b) = 10 · 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 · 364 = 449194.
      Vi bruker nierprøven. I 1) fant vi at T(a) · 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) · A(b) = 2 · 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 · 364 = 449176.
      Vi bruker nierprøven. I 1) fant vi at T(a) · 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) · 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. Dette er ikke noe bevis, men 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 ≡ 108 ≡ 8 (mod 10).

Siden 8 ≢ 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 fødselsnummer.

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

Første kontrollsiffer: 

Fødselsnummer	2	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 fødselsnummer	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 ≡ 126 ≡ 5 (mod 11).

Siden 5 ≢ 0 (mod 11) er første kontrollsiffer ikke riktig. Det har da ingen hensikt å undersøke andre kontrollsiffer, fødselsnummeret 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.
    
   At 2525 ≡ 2 (mod 7) kan vi finne ved å bruke kommandoen mod(2515, 7) i GeoGebra eller =rest(2515; 7) i et regneark.
    
2. Wolfgang Amadeus Mozarts fødsel den 27. januar 1756.
   Januar 1756 er måned 11 i året før, altså 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.
    
   At 2235 ≡ 2 (mod 7) kan vi finne ved å bruke kommandoen mod(2235, 7) i GeoGebra eller =rest(2235; 7) i et regneark.

Tilbake til oppgaven

Oppgave 8:

Vi skal bruke metoden med toerpotenser til å beregne resten vi får når vi dividerer 6¹³ med 11.

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

Så 6¹³ = 6¹⁺⁴⁺⁸ = 6 · 6⁴ · 6⁸.

6² ≡ 36 ≡ 3 (mod 11)

6⁴ ≡ (6²)² ≡ 3² ≡ 9 ≡ −2 (mod 11)

6⁸ ≡ (6⁴)² ≡ (−2)² ≡ 4 (mod 11)

Så 6¹³ ≡ 6 · 6⁴ · 6⁸ ≡ 6 · (−2) · 4 ≡ −48 ≡ 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. 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, og vi skal sette opp en kongruenslikning som modellerer hvor mange intervaller hun kan ha løpt.
      Her må vi finne ut hvilke antall 300-meters intervaller som er kongruente med 100 meter modulo lengden på banen, altså 400 meter.
      Så likningen blir 300x ≡ 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, og vi skal sette opp en kongruenslikning som modellerer hvor mange passeringer senere banen igjen passerer på et helt klokkeslett.
      Her må vi finne ut hvilke antall perioder på 12 minutter som er kongruente med 0 modulo 60. Grunnen til at vi regner modulo 60 er at det er 60 minutter i en time, og grunnen til at vi skal ha kongruens med 0 er at 0 minutter representerer «hel time».
      Så likningen blir 12x ≡ 0 (mod 60), der x representerer antall passeringer.

Tilbake til oppgaven

Oppgave 2:

Vi skal foreslå en situasjon som kan modelleres med kongruenslikningen 4x ≡ 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. 1. 4x ≡ 8 (mod 10)
      Vi har SFF(4, 10) = 2. 2 | 8, så likningen har løsning i 2 restklasser.
       
   2. 3x ≡ 8 (mod 10)
      Vi har SFF(3, 10) = 1. 1 | 8, så likningen har løsning i 1 restklasse.

   3. 4x ≡ 9 (mod 10)
      Vi har SFF(4, 10) = 2. 2 ∤ 9, så likningen har ingen løsning.

   4. 84x ≡ 108 (mod 12)
      Vi har SFF(84, 12) = 12. 12 | 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 ≡ 13 − 5x (mod 5).

Vi starter med å flytte 4 over på høyre side, −5x over på venstre side og skifte fortegn:
x + 5x ≡ 13 − 4 (mod 5)

Så trekker vi sammen like ledd:
6x ≡ 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 ≡ 4 (mod 5)

Tilbake til oppgaven

Oppgave 5:

Vi skal finne alle restklasser som inneholder løsninger til likningen 6x ≡ 12 (mod 9).

Vi har at SFF(6, 9) = 3 og 3 | 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 ≡ 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 ≡ 3 (mod 7).

Fra lista nederst i artikkelen om regneregler for kongruens finner vi at en invers til a = 4 modulo 7 er a = 2.

Vi multipliserer med 2 på begge sider av kongruenstegnet og får (4 · 2)x ≡ 3 · 2 (mod 7) ⇒ x ≡ 6 (mod 7).

Tilbake til oppgaven

Oppgave 7:

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

1. 270x − 10 ≡ −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 ≡ −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 ≡ 12 (mod 44).
    
   Vi finner d = SFF(a, n) = SFF(36, 44) = 4. Siden 4 | 12, har likningen løsninger i 4 restklasser.
    
   Vi dividerer alle ledd med 4 og får
   9x ≡ 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 ≡ 1 (mod 11).
    
   Fra lista nederst i artikkelen om regneregler for kongruens finner vi at en invers til a = 3 modulo 11 er a = 4.
   Vi multipliserer med 4 på begge sider av kongruenstegnet og får (3 · 4)x ≡ 1 · 4 (mod 11).
    
   Vi har altså følgende løsning:
   x ≡ 4 (mod 11).
    
   Ut fra denne løsningen finner vi de fire restklassene med løsninger i den opprinnelige likningen modulo 44:
   x₀ = 4 + 0 · 11 = 4
   x₁ = 4 + 1 · 11 = 15
   x₂ = 4 + 2 · 11 = 26
   x₃ = 4 + 3 · 11 = 37
    
   Så løsningene til kongruenslikningen er x ≡ 4, 15, 26, 37 (mod 44).

2. −108x − 100 ≡ 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 ≡ 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 ≡ 21 (mod 44).
    
   Vi finner d = SFF(14, 44) = 2.
   Siden 2 ∤ 21, har likningen ingen løsning.

​Tilbake til oppgaven

Oppgave 8:

Vi skal løse kongruenslikningen 60x ≡ −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 ≡ −5 (mod 7).

Vi benytter så at 6 ≡ −1 (mod 7) og skriver om til

−x ≡ −5 (mod 7).

Vi multipliserer med −1 på begge sider og får

x ≡ 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 ≡ 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 ≡ 3 (mod 7)
    
3. Vi ser at operasjonen må gå i tre trinn, siden x = 3. En trinnvis beskrivelse 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

Tall og tallsystemer

Oppgave 2:

Vi skal regne ut hva 52306₇ i sjutallsystemet blir i titallsystemet:

52306₇ = 5 · 7⁴ + 2 · 7³ + 3 · 7² + 0 · 7¹ + 6 · 7⁰ = 12005 + 686 + 147 + 0 + 6 = 12844₁₀

Tilbake til oppgaven

Oppgave 3:

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

52306₇ = 5 · 7⁴ + 2 · 7³ + 3 · 7² + 0 · 7 + 6.

Tilbake til oppgaven

Oppgave 5:

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

1. Sekstentallsystemet.
   Slår sammen i grupper på fire fra høyre, og setter på en ledende null:
   (0111 0100 1111)₂
   Regner om hver gruppe til sekstentallsystemet:
   0111₂ = 7₁₆
   0100₂ = 4₁₆
   1111₂ = F₁₆
   Så 11101001111₂ = 74F₁₆.
    
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₁₆ = 7 · 16² + 4 · 16 + 15 = 1792 + 64 + 15 = 1871₁₀
   Tar vi utgangspunkt i totallsystemet, får vi:
   11101001111₂ = 1 · 2¹⁰ + 1 · 2⁹ + 1 · 2⁸ + 0 · 2⁷ + 1 · 2⁶ + 0 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 1 · 2² + 1 · 2 + 1 = 1024 + 512 + 256 + 0 + 64 + 0 + 0 + 8 + 4 + 2 + 1 = 1871₁₀

Tilbake til oppgaven

Oppgave 7:

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

1. 1. Tverrsummen av tallet.
      T(n) = 7 + 1 + 9 + 3 + 5 + 3 + 6 = 34.
       
   2. Den alternerende tverrsummen av tallet.
      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 · 18 + 1 · 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.

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

Tverrsummen til 1386 er T(1386) = 1 + 3 + 8 + 6 = 18. 18 er delelig med 3, og også med 9. 1386 er derfor delelig med 3 og 9.

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 ikke delelig med 5. 1386 er derfor ikke delelig med 5.

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 · 3 · 3 · 7 · 11.

Tilbake til oppgaven

Oppgave 3:

Vi skal bruke divisjonsalgoritmen på

1. 1. ​a = 133, b = 21
      Vi finner $\frac{\displaystyle a}{\displaystyle b} = {\large \frac{133}{21}} \approx 6{,}33$
      Så $q = \lfloor 6{,}33 \rfloor = 6$
      og r = 133 − 6 · 21 = 7
      Så 133 = 6 · 21 + 7.
       
   2. a = −50, b = 8
      Vi finner $ \frac{\displaystyle a}{\displaystyle b} = {\large \frac{-50}{8}} = -6{,}25$
      Så $q = \lfloor -6{,}25 \rfloor = -7$
      og r = −50 − (−7 · 8) = 6
      Så −50 = −7 · 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 · 45 og skal avgjøre om følgende er riktig:

• 3 går opp i 900. Da går 3 opp i 45.
  Riktig. 3 går opp i 900, men ikke i faktoren 20. Da må 3 gå opp i faktoren 45.
   
• 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² − 1.

Ved hjelp av konjugatsetningen baklengs kan vi skrive n² − 1 som (n + 1)(n − 1). Et slikt tall kan altså alltid deles opp i minst to faktorer.

3² − 1 = 8, for eksempel, kan skrives som (3 + 1)(3 − 1) = 4 · 2.

​​​Tilbake til oppgaven

Oppgave 4:

Basert på lista med n som gir Mersenne-primtall, 2, 3, 5, 7, 13, …, og formelen for å generere perfekte tall, 2^{(n − 1)}(2ⁿ − 1), skal vi finne det perfekte tallet generert av Mersenne-primtall nummer fire.

Mersenne-primtall nummer 4 genereres av n = 7, vi setter inn i formelen, og får 2^{(7 − 1)}(2⁷ − 1) = 64 · 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 om lag 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² = a² − n = (14)² − 189 = 196 − 189 = 7.

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

Vi får

 b² = a² − n = (15)² − 189 = 225 − 189 = 36.

36 er et kvadrattall, 6².

Vi har altså at a² = 15² og b² = 6².

Så 189 = 15² − 6², og kan faktoriseres som (15 + 6)(15 − 6) = 21 · 9.

Vi vet at 21 = 3 · 7 og at 9 = 3 · 3, men vi viser det ved hjelp av Fermats metode:

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

 b² = a² − n = (5)² − 21 = 25 − 21 = 4.

4 er et kvadrattall, 2².

Vi har altså at a² = 5² og b² = 2².

Så 21 = 5² − 2², og kan faktoriseres som (5 + 2)(5 − 2) = 7 · 3.

Vi vet at både 7 og 3 er primtall, og går ikke videre med prosessen.

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

Vi får b² = a² − n = (3)² − 9 = 9 − 9 = 0.

0 er et kvadrattall, 0².

Vi har altså at a² = 3² og b² = 0².

Så 9 = 3² − 0², og kan faktoriseres som (3 + 0)(3 − 0) = 3 · 3.

Vi vet at 3 er primtall, og går ikke videre med prosessen.

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 $\lfloor \sqrt {83} \rfloor = 9$, er 7 det høyeste primtallet som må sjekkes, så vi slår fast at 83 er et primtall.

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

Tilbake til oppgaven

Største felles faktor

Oppgave 1:

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

Ved hjelp av for eksempel «brute force»-metoden finner vi at 168 = 2 · 2 · 2 · 3 · 7, og at 140 = 2 · 2 · 5 · 7. Vi ser at to totall og ett sjutall er felles, så vi får SFF(168, 140) = 2 · 2 · 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 2:

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

Vi finner $q = {\large \lfloor \frac{1365}{495} \rfloor} = 2$, og r = 1365 − 2 · 495 = 375. Så 1365 = 2 · 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 · 375 = 120. Så 495 = 1 · 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 · 120 = 15. Så 375 = 3 · 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 · 15 = 0. Så 120 = 8 · 15 + 0.

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

Vi har nå at a = 15 og r = 0.

Så SFF(1365, 495) = 15.

Tilbake til oppgaven

Minste felles multiplum

Oppgave 1:

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

Ved hjelp av for eksempel «brute force»-metoden finner vi at 63 = 3 · 3 · 7, og at 135 = 3 · 3 · 3 · 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 · 3 · 7 · 3 · 3 · 3 · 5 = 945.

Alternativt: 63 = 3² · 7¹ og 135 = 3³ · 5¹.

Multipliserer vi høyeste potens av alle faktorene, får vi

MFM(63, 135) = 3³ · 5^{1 ·} 7¹= 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 2:

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