Løsningsforslag, grunnleggende tallteori

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