7. Primtal och gemensamma faktorer

Vad har talen \(2, 3, 5, 7, 11, 13 \) gemensamt?

Vi märker att alla 6 tal är delbara med sig själv och 1. Sådana tal kallas för primtal. Primtal används i kryptering.

För att undersöka om ett tal är ett primtal undersöker vi om vi kan faktorisera talet.

Exempel 1 Är talet 19 ett primtal? Vilka tal skall vi försöka faktorisera med?

Lösning

Vi börjar med att undersöka om talet 2 är en faktor i 19. \( \dfrac{19}{2} = 9 \text{ rest } 1\).

Till nästa är talet 3, \( \dfrac{19}{3} = 6 \text{ rest } 1 \).

Följande tal är inte 4, eftersom \( 4 = 2 \cdot 2 \), utan 5. \( \dfrac{19}{5} = 3 \text{ rest } 4 \).

Talet 6 hoppar vi över, eftersom \( 6 = 2 \cdot 3 \).

Vårt nästa tal är 7, \( \dfrac{19}{7} = 2 \text{ rest } 5 \).

Talen \( 8 = 2 \cdot 2 \cdot 2 \), \( 9 = 3 \cdot 3 \) och \( 10 = 2\cdot 5 \) hoppar vi över.

Följande är 11, \( \dfrac{19}{11} = 1 \text{ rest } 8 \).

Talet \( 12 = 2\cdot 2 \cdot 3 \). Det hoppas över.

Vårt nästa tal är 13, \( \dfrac{19}{13} = 1 \text{ rest } 6 \).

Talen \( 14 = 2\cdot 7 \), \( 15 = 3\cdot 5 \) och \( 16 = 2 \cdot 2 \cdot 2 \cdot 2 \) hoppar vi över.

Följande är 17, \( \dfrac{19}{17} = 1 \text{ rest } 2 \).

Talet \( 18 = 2 \cdot 3 \cdot 3 \) så det hoppar vi över.

Till sist kommer vi till 19, \( \dfrac{19}{19} = 1 \). Så 19 är ett primtal.

När vi undersöker om ett tal, \(n \), är ett primtal dividerar vi med de primtal, \( p \), så att \( p < \sqrt{n} \). Denna metod kallas för Eratosthenes såll.

Exempel 2 Dela upp följande tal i primfaktorer.

Lösning

Vi får \(16 = 2 \cdot 8 = 2 \cdot 2 \cdot 4 = 2^2 \cdot 2 \cdot 2 = 2^4 \).
Vi får \( 420 = 2 \cdot 210 = 2 \cdot 2 \cdot 105 = 2^2 \cdot 3 \cdot 35 = 2^2 \cdot 3 \cdot 5 \cdot 7 \).
Vi får \( 82 = 2 \cdot 41 \).

Faktorisering av tal till primfaktorer utnyttjar vi för att bestämma största gemensamma faktor, SGF, och minsta gemensamma nämnare MGM. Största gemensamma faktor kallas ibland för största gemensamma delaren, SGD.

Största gemensamma faktor för två tal är de största antal primtal som är faktorer i bägge talen.

Minsta gemensamma nämnare är alla de primtal som är gemensamt i bägge tal.

Exempel 3 Bestäm för talen 84, 280 och 1260 största gemensamma faktor och minsta gemensamma nämnare.

Lösning

Vi börjar med att dela upp talen i primfaktorer.

\( 84 = 2^2 \cdot 3 \cdot 7 \)

\( 280 = 2^3 \cdot 5 \cdot 7 \)

\( 1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7 \)

Den största gemensamma faktorn, SGF(84,280,1260) är \( 2^2 \cdot 7 = 28 \).

Minsta gemensamma nämnare MGM(84,280,1260) är \( 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520 \).

Uppgifter

Undersök om följande tal är primtal.
1. 113
  
  Eftersom \( \sqrt{113} = 10,6 \) dividerar vi med primtalen 2, 3, 5, 7.
  
  \( \dfrac{113}{2} = 56 \text{ rest } 1 \).
  
  \( \dfrac{113}{3} = 37 \text{ rest } 2 \).
  
  \( \dfrac{113}{5} = 22 \text{ rest } 3 \).
  
  \( \dfrac{113}{7} = 16 \text{ rest } 1 \).
  
  Alltså är talet 113 ett primtal.
2. 259
  
  Eftersom \( \sqrt{259} = 16,1 \) dividerar vi med primtalen som är mindre än 16.
  
  \( \dfrac{259}{2} = 129 \text{ rest } 1 \).
  
  \( \dfrac{259}{3} = 86 \text{ rest } 1 \).
  
  \( \dfrac{259}{5} = 51 \text{ rest } 4 \).
  
  \( \dfrac{259}{7} = 37 .
  
  Eftersom vi kan faktorisera med 7 är 259 inte ett primtal.
3. 297
  
  Eftersom \( \sqrt{297} = 17,2 \) dividerar vi med primtalen som är mindre än 16.
  
  \( \dfrac{297}{2} = 148 \text{ rest } 1 \).
  
  \( \dfrac{297}{3} = 99 \).
  
  Eftersom vi kan faktorisera med 3 är 297 inte ett primtal.
Fakotrisera följande tal till primfaktorer.
1. 259
  
  Eftersom \( \sqrt{259} = 16,1 \) jobbar vi med primtalen som är mindre än detta.
  
  Vi får \(259 = 7 \cdot 37 \). Eftersom 37 är ett primtal är 259 färdigt faktoriserat.
2. 297
  
  Eftersom \( \sqrt{297} = 17,2 \) jobbar vi med primtal som är mindre än detta.
  
  Vi får \( 297 = 3 \cdot 99 = 3 \cdot 3 \cdot 33 = 3^2 \cdot 3 \cdot 11 = 3^3 \cdot 11 \).
3. 1904
  
  Eftersom \( \sqrt{1904} = 43,6 \) jobbar vi med primtal som är mindre än detta.
  
  Vi får \( 1904 = 2\cdot 952 = 2 \cdot 2 \cdot 476 = 2^2 \cdot 2 \cdot 238 = 2^3 \cdot 2 \cdot 119 = 2^4 \cdot 7 \cdot 17 \).
Utnyttja Eratosthenes såll för att hitta de primtal som är mindre än 150.

Lösningen
Bestäm för följande tal största gemensamma faktor och minsta gemensamma nämnare.
1. 55 och 120
  
  Vi får
  
  \( 55 = 5 \cdot 11 \)
  
  \( 120 = 2^3 \cdot 3 \cdot 5 \)
  
  Vi får SDF(55,120) är \( 5 \).
  
  Vi får MGM(55,120) är \( 2^3 \cdot 3 \cdot 5 \cdot 11 = 1320 \).
2. 34 och 55
  
  Vi får
  
  \( 34 = 2 \cdot 17 \)
  
  \( 55 = 5 \cdot 11 \)
  
  Vi får SDF(34,55) är \( 1 \).
  
  Vi får MGM(34,55) är \( 2 \cdot 5 \cdot 11 \cdot 17 = 1870 \).
3. 190 och 172
  
  Vi får
  
  \( 190 = 2 \cdot 5 \cdot 19 \)
  
  \( 172 = 2^2 \cdot 43 \)
  
  Vi får SDF(190,172) är \( 2 \).
  
  Vi får MGM(190,172) är \( 2^2 \cdot 5 \cdot 19 \cdot 43 = 16340 \).
4. -84 och 99
  
  \( -84 \) kan vi inte dela upp i primtalsfaktoer eftersom talet är negativt.
  
  Då extisterar inte SDF och MGM för -84 och 99.
Skriv en algoritm som går igenom stegen då man undersöker om ett tal är ett primtal.

Något i följande stil:

Börja med att ta roten av talet som undersöks.

Börja dividera talet som undersöks med första primtalet.

Går divisionen jämnt ut är det inte frågan om ett primtal.

Går den sista divisionen, den mellan talet och det största möjliga primtalet, inte jämnt ut är det frågan om ett primtal.
Skriv en algoritm där vi söker största gemensamma faktor och största gemensamma nämnare.

Något i följadne stil:

Börja med att dela upp talen i primtalsfaktorer.

För att få största gemensamma faktor: per primtalsfaktor som finns, multiplicer det minsta antalet multiplar av varje.

För att få största gemensamma nämnare: tag största antalet multipel av alla primtalsfaktorer som finns och multipliera ihop dem.
Skriv ett program där man kan undersöka om talet som undersöks är ett pritmal.

Lösningen
Skriv ett program som skriver ut största gemensamma faktor och största gemensamma nämnare för två tal.

Lösningen