Løsningsforslag, kongruenser

Innhold

Kongruens
Kongruens, regneregler
Kongruens, anvendelser
Kongruenslikninger

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

65 ≡ 17 (mod 12)
Vi får a − b = 65 − 17 = 48. Siden n = 12 | 48, er påstanden riktig.
−12 ≡ 18 (mod 5)
Vi får a − b = −12 − 18 = −30. Siden n = 5 | −30, er påstanden riktig.
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.

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).
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).
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. 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.

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

Både nierprøven og elleveprøven påviser feil.
Resultatet er feil.
Enten nierprøven eller elleveprøven påviser feil.
Resultatet er feil.
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 k₁	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.

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

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).
−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.

Vi skal sette opp en kongruenslikning som uttrykker dette problemet.
Etter modell fra eksempel 13, ser vi at det blir
5x ≡ 1 (mod 7)
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)
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