4. Delninsgsekvationen och Euklides algoritm

Hittils har vi jobbat med delninsgsekvationen utan att namne att vi jobbar med den. Delningsekvationen handlar om att vi skriver divisioner med hjälp av rest.

Vi utför divisionen \( \dfrac{13}{4} \). Vi får att \( \dfrac{13}{4} = 3 \text{ rest } 1 \).

Vi kan skriva \( 13 = 3\cdot 4 + 1 \). Detta är delningsekvationen.

Matematiskt uttrycker vi delninsgsekvationen på följande sätt.

Anta att \( b \) är ett positivt heltal. Varje heltal \( a \) kan skrivas som \[ a = br + q \] där \( q \) och \( r \) är heltal och \( 0 \leq r < b \).

Exempel 1 Visa att summan av 99 på varandra följande heltal är delbar med 11.

Lösning

Vi betecknar det minsta talet med \( k \). Då är följande \( k +1 \) och vi får summan \( k + (k+1)+(k+2)+\ldots+ (k+98) \).

Vi märker att vi har en aritmetisk summa. Summan är \( S_n = \dfrac{n(a_1 + a_n)}{2} \).

Vi får \( \dfrac{99(k+(k+98))}{2} = \dfrac{99(2k +98)}{2} \).

Då vi vill visa att summan är delbar med 3, skall vi förenkla så att vi hittar faktorn 11.

Vi får \( 11\cdot 9 \cdot \dfrac{2(k+49)}{2} = 11 \cdot 9 (k + 49) \).

Alltså är summan delbar med 11. Dessutom är den delbar med alla faktorer som vi hittar i summan.

Exempel 2 Visa att talet \( n(n+2)(n+4) \) är delbart med talet 3 för alla heltal \( n \).

För att visa att \( n(n+2)(n+4) \) är delbart med 3 för alla heltal så skall vi visa att då vi sätter in talen av formen \( 3q \), \( 3q +1 \) och \( 3p + 2 \) i \( n(n+2)(n+4) \) så skall vi hitta en faktor 3.

Vi börjar med \( 3q \), \( 3q(3q+2)(3q+4) = 3\cdot q(3q+2)(3q+4) \). Här har vi en faktor 3.

Följande \( 3q + 1 \), \( (3q+1)(3q+1+2)(3q+1+4) = (3q+1)(3q+3)(3q+5) = 3(3q+1)(q+1)(3q+5) \). Här har vi en faktor 3.

Det sista är \( 3q +2 \), \( (3q+2)(3q+2+2)(3q+2+4) = (3q+2)(3q+4)(3q+6) = 3(3q+2)(3q+4)(q+2) \). Här har vi också en faktor 3.

Alltså är talet \( n (n+2)(n+4) \) alltid delbart med 3.

Euklides algortim handlar om att vi utnyttjar delningsekvationen för att bestämma största gemensamma faktor för två positiva heltal.

Exempel 3 Bestäm med hjälp av Euklides algoritm största gemensamma faktor för talen 396 och 332.

Lösning

Vi delar det större talet med det mindre och skriver resultatet med hjälp av delningsekvationen.

Alltså \( \dfrac{396}{332} = 1 \text{ rest } 64 \). Alltså \( 396 = 332 \cdot 1 + 64 \).

Sedan dividerar vi 332 med resten 64. \( \dfrac{332}{64} = 5 \text{ rest } 12 \). Alltså \( 332 = 64 \cdot 5 + 12 \).

Sedan dividerar vi 64 med 12. \( \dfrac{64}{12} = 5 \text{ rest } 4 \). Alltså \( 64 = 12\cdot 5 + 4 \).

Sedan dividerar vi 12 med 4. \( \dfrac{12}{4} = 3 \text{ rest } 0 \). Alltså \( 12 = 4\cdot 3 + 0 \).

Eftersom vi har resten 0 slutar vi dividera.

Det betyder att \( SGF(12,4) = 4 \) och \( SGF(396,332) = 4 \).

Uppgifter

Bestäm största gemensamma faktor för följande tal med hjälp av Euklides algoritm.
1. 202 och 102
  
  Vi får
  
  \( \dfrac{202}{102} = 1 \text{ rest } 100\). Alltså \( 202 = 102 \cdot 1 + 100 \).
  
  \( \dfrac{102}{100} = 1 \text{ rest } 2\). Alltså \( 102 = 100 \cdot 1 + 2 \).
  
  \( \dfrac{100}{2} = 50 \text{ rest } 0\). Alltså \( 100 = 2 \cdot 50 + 0 \).
  
  Alltså \( SGF(202,102) = 2 \).
2. 111 och 629
  
  Vi får
  
  \( \dfrac{629}{111} = 5 \text{ rest } 74\). Alltså \( 629 = 111 \cdot 5 + 74 \).
  
  \( \dfrac{111}{74} = 1 \text{ rest } 37 \). Alltså \( 111 = 74 \cdot 1 + 37 \).
  
  \( \dfrac{74}{37} = 2 \text{ rest } 0\). Alltså \( 74 = 37 \cdot 2 + 0 \).
  
  Alltså \( SGF(111,629) = 37 \).
3. 11055 och 29614
  
  Vi får
  
  \( \dfrac{29614}{11055} = 2 \text{ rest } 7504\). Alltså \( 29614 = 11055 \cdot 2 + 7504 \).
  
  \( \dfrac{11055}{7504} = 1 \text{ rest } 3551 \). Alltså \( 11055 = 7504 \cdot 1 + 3351 \).
  
  \( \dfrac{7504}{3551} = 2 \text{ rest } 402 \). Alltså \( 7504 = 3551 \cdot 2 + 402 \).
  
  \( \dfrac{3551}{402} = 8 \text{ rest } 335 \). Alltså \( 3551 = 402 \cdot 8 + 335 \).
  
  \( \dfrac{402}{335} = 1 \text{ rest } 67 \). Alltså \( 402 = 335 \cdot 1 + 67 \).
  
  \( \dfrac{335}{67} = 5 \text{ rest } 0 \). Alltså \( 335 = 67 \cdot 5 + 0 \).
  
  Alltså \( SGF(11055,29614) = 5 \).
Delbarhet hos tal kan man även undersöka genom att förenkla uttrycket som det representerar, tex summan för två jämna tal efter varandra, \( 2n \) och \( 2n +2 \), kan vi undersöka genom att förenkla uttrycket. \( 2n + (2n+2) = 4n+2 = 2(n+1) \).

Eftersom det förenklade uttrycket innehåller en faktor 2, kan vi säga att summan är jämn, eller delbar med två.
1. Undersök summan av två på varandra följande udda tal. Med vilket tal är summan delbar?
  
  Talen är \(2n+1 \) och \( 2n+3 \).
  
  Summan är \( (2n+1)+(2n+3) = 4n+4 = 2\cdot 2 (n+1) \).
  
  Vi ser att summan är jämn, delbar med 2 och delbar med 4.
2. Undersök summan av tre på varandra följande tal. Men vilket tal är summan delbar? Är det en skillnad om vi börjar med ett jämnt eller udda?
  
  Vi börjar med jämt + udda + jämt.
  
  \( 2n + (2n+1) + 2(n+1) = 6n+3 = 3(2n+1) \).
  
  Vi får att talet är udda, och delbart med 3.
  
  Fallet udda, jämnt, udda.
  
  \( (2n+1)+(2n+2)+(2n+3) = 6n+6 = 2\cdot 3(n+1) \).
  
  Vi får att talet är delbart med 2, 3 och 6.
3. Undersök produkten av två på varandra följande heltal. Med vilket tal är produkten delbar?
  
  Vi får \( 2n \cdot 2(n+2) = 4n(n+2) \).
  
  Vi märker att produkten är delbar med 2, 4 och talet n som vi bygger upp våra heltal med.
4. Undersök produkten av två på varandra följande udda tal. Med vilket tal är produkten delbar?
  
  Vi får \( (2n+1) \cdot (2n+3) = 4n^2 +8n +3 \).
  
  Utgående från det här kan vi inte säga något om produkten.
Skriv en algoritm över hur du utnyttjar Euklides algoritm för att bestämma största gemensamma faktor för två tal.

Lösningen
Talet \( a \) är delbart med talet 28 och talet \( b \) är delbart med talet 21. Visa att
1. talet \( a + b \) är delbart med 7.
  
  Eftersom talet \( a \) är delbart med 28 är det också delbart med olika varianter av \( 2 \cdot 2 \cdot 7 \).
  
  För talet \( b \) gäller motsvarande, \( 21 = 3 \cdot 7 \).
  
  Då kommer summan av \( a + b \) innehålla faktorn 7, och vara delbart med 7.
2. talet \( ab \) är delbart med talet 12.
  
  Samma logik som ovan.
  
  Produkten \( ab \) innehåller produkten av alla primtalsuppdelningar. Också \( 2^2 \cdot 3 = 12 \).
Visa att talet \( (n+1)^2 -(n-1)^2 \) alltid är delbart med talet 4 för alla heltal \( n \).

De tal som vi undersöker är \( 4q \), \( 4q+1 \), \( 4q+2 \) och \( 4q+3 \).

\( 4q \) ger oss \( (4q+1)^2 -(4q-1)^2 = 16q^2+8q+1 -16q^2+8q-1 = 16 q = 4^2 q \). Här är faktor 4.

\( 4q+1 \) ger oss \( (4q+1+1)^2 - (4q+1-1)^2 = 16q^2+16q+4 - 16q^2 = 4(4q+1) \). Här är en faktor 4.

\( 4q+2 \) ger oss \( (4q+2+1)^2 -(4q+2-1)^2 = 16q^2 + 24q+9 -16q^2-8q-1 = 16q+8 = 4(4q+2) \). Här är en faktor 4.

\( 4q +3 \) ger oss \( (4q+3+1)^2 -(4q+3-1)^2 = 16q^2 +32q +16 -16q^2 -16q -4 = 16q +12 = 4(4q+3) \). Här är en faktor 4.

Alltså är \( (n+1)^2 -(n-1)^2 \) delbart med 4.

Om vi förenklar \( (n+1)^2 -(n-1)^2 = (n+1+(n-1))(n+1)-(n-1)) = 2n \cdot 2 = 4n \). Då är varenda tal som vi sätter in 4 gånger större och delbart med 4:a.
Visa att talet \( n(n+1)(2n+1) \) är delbart med talet 6 för alla heltal \( n \).

Vi skall undersöka med talen \( 6q, 6q+1, 6q+2, 6q+3, 6q+4 \) och \( 6q+5 \).

\( 6q \) ger \( 6q(6q+1)(2(6q)+1) = 6q(6q+1)(12q+1) \). Här är en faktor 6.

\( 6q + 1 \) ger \( (6q+1)(6q+1+1)(2(6q+1)+1) = (6q+1)(6q+2)(12q+3) = (6q+1)(72 q^2 + 42 q + 6) = (6q+1)6(12q^2+7q +1) \). Här är en faktor 6.

\( 6q+2 \) ger \( (6q+2)(6q+2+1)(2(6q+2)+1) = (6q+2)(6q+3)(12q+5) = (36q^2 + 30q+6)(12q+5) = 6(6q^2+5q+1)(12q+5) \). Här är en faktor 6.

\( 6q+3 \) ger \( (6q+3)(6q+3+1)(2(6q+3)+1) = (6q+3)(6q+4)(12q+7) = (36q^2 + 42q +12)(12q+5) = 6(6q^2+7q+2)(12q+5) \). Här är en faktor 6.

\( 6q+4 \) ger \( (6q+4)(6q+4+1)(2(6q+4)+1) = (6q+4)(6q+5)(12q+9) = (6q+5)(72q^2 + 102q +36) = (6q+5)6(12q^2+17q+6) \). Här är en faktor 6.

\( 6q+5 \) ger \( (6q+5)(6q+5+1)(2(6q+5)+1) = (6q+5)(6q+6)(12q+11) = (6q+5)6(q+1)(12q+11) \). Här är en faktor 6.
Skriv ett program för hur man bestämmer största gemensamma faktor för två tal genom att utnyttja Euklides algoritm.

Lösningen