MaA 11 Algoritmer och talteori

6. Diofantisk ekvation

Då vi vill lösa ekvationen \( 87x-64y = 3 \). märker vi att vi får talpar som uppfyller ekvationen.

För att lösa den utnyttjar vi divisionsekvationen och gör följande:

\( \begin{array}{rcl} 87 & = & 1 \cdot 64 +23 \\ 64 & = & 2 \cdot 23 +18 \\ 23 & = & 1 \cdot 18 +5 \\ 18 & = & 3 \cdot 5 + 3 \\ 5 & = & 1\cdot 3 +2 \\ 3 & = & 1 \cdot 2 +1 \\ 2 & = & 2\cdot 1 +0 \\ \end{array} \)

Det betyder att sgf(87,64)=1. Och för att lösa ekvationen fortsätter vi på följande sätt:

Vi börjar från näst sista raden, eftersom vi har en rest.

\( \begin{array}{rcl} 1 & = & 3 - 2 \\ 1 & = & 3 - (5- 3) = 2 \cdot 3 -5 \\ 1 & = & 2 (18 -3 \cdot 5) -5 = 2 \cdot 18 -7 \cdot 5 \\ 1 & = & 2 \cdot 18 -7(23 - 18) = -7 \cdot 23 +9 \cdot 18 \\ 1 & = & -7 \cdot 23 +9(64 -2\cdot 23)=9 \cdot 64 -25 \cdot 23 \\ 1 & = & 9 \cdot 64 -25 (87 - 64) = 34 \cdot 64 -25 \cdot 87\\ 1 & = & (-25) \cdot 87 - (-34) \cdot 64 \\ \end{array} \)

Eftersom vi skall ha \( =3 \) multiplicerar vi hela ekvationen med 3. Vi får alltså

\( \begin{array}{rcl} 3\cdot 1 & = & - 25 \cdot 3 \cdot 87 - (-34) \cdot 3 \cdot 64 \\ 3 & = & - 75 \cdot 87 - (-102) \cdot 64 \\ \end{array} \)

Alltså är \( x=-75 \) och \( y=-102 \) en lösning.

Sedan söker vi resten av lösningarna.

\( x = -75 + (-64) = -139 \) och \( y=-102 -87 = -189 \). Vi testar talparet: \( 87(-139)-64(-189)=3\).

Alltså stämmer det.

Då kan vi uttrycka lösningarna som \( x = -75 -64n \) och \( y=-102 -87n\) där \( n \) är ett heltal.

En diofantisk ekvation är en ekvation vars lösningar är talpar. För att bestämma dessa talpar så löser vi dem som ovan eller så finns det färdiga forlmer i tabellböcker.

Uppgifter

  1. Lös följande diofantiska ekvationer.
    1. \( 11x+13y=4 \)

      Vi får

      \( \begin{array}{rcl} 13 & = & 1 \cdot 11 + 2 \\ 11 & = & 5 \cdot 2 + 1 \\ 2 & = & 2 \cdot 1 + 0 \\ \end{array} \)

      Sedan fortsätter vi med

      \( \begin{array}{rcl} 1 & = & 11 - 5 \cdot 2 \\ 1 & = & 11 - 5 (13-11) \\ 1 & = & 11 + 5 \cdot 11 -5 \cdot 13 \\ 1 & = & 11 \cdot 6 + 13(-5) \\ \end{array} \)

      Eftersom vår ekvation har \( \ldots = 4 \) tar vi \( 1 = 11 \cdot 6 + 13(-5) \) gånger 4. Vi får \( 4 = 11 \cdot 24 +13 (-20) \).

      Då vet vi att \( x = 24 \) och \( y = -20 \) är en lösning.

      Kandidaterna för resten lösningar är \( x = 24 \pm 13n \) och \( y = -20\pm 11n \).

      Vi testar och kommer fram till

      \( \left\{ \begin{array}{l} x = 24 +13n \\ y = -20 -11n\\ \end{array} \right. \)

      Märk att följande fungerar också

      \( \left\{ \begin{array}{l} x = 24 -13n \\ y = -20 +11n\\ \end{array} \right. \)

    2. \( 5x+10y=21 \)

      Saknar lösning för att 21 är inte delbart med SGF(5, 10)

    3. \( 7x+21y=28 \)

      Vi får

      \( \left\{ \begin{array}{l} x = -8 +3n \\ y = 4 - 1n \\ \end{array} \right. \)

  2. Bestäm heltalslösningarna för följande ekvationer.
    1. \( 5x+10y=85 \)

      Vi får

      \( \left\{ \begin{array}{l} x = -17+ 2n \\ y = 17 - 1n \\ \end{array} \right. \)

    2. \( 3x+5y=8 \)

      Vi får

      \( \left\{ \begin{array}{l} x = 16 +5n \\ y = -8 - 3n \\ \end{array} \right. \)

    3. \( 221x+238y=1156 \)

      Vi får

      \( \left\{ \begin{array}{l} x=68 +13n \\ y = -68 - 14n \\ \end{array} \right. \)

  3. Lös ekvationen \( 98x+35 y = 14 \).

    \( x=-2+5n \) och \( y=6-14n \), där \( n \in \mathbf{Z}\).

  4. Lös ekvationen \( 98x+35 y = 13 \).

    Går inte. Vi får att sgf(98,35)=7 och 7 är inte en faktor i 13 så ekvationen saknar lösningar.

  5. Lös ekvationen \( 77x +91y=168 \).

    \( x=144+13n \) och \( y=-120-11n \), där \( n \in \mathbf{Z} \).

  6. Den diofantiska ekvationen \( 13x + 31y = 44 \) har en lösning \( (1, 1) \). Skriv den generella lösningen.

    Vi får

    \( \left\{ \begin{array}{l} x = 1 +31n \\ y = 1-13n \\ \end{array} \right. \)

  7. I en husdjursaffär finns på en avdelning fiskar, papegojor och möss. Cecilia ville göra sin far svarslös genom att fråga hur många det fanns av vardera slaget om antalet huvuden var 28 och antalet fötter 20. Hjälp fadern att lösa uppgiften!

    (Bilda två ekvationssystem och jobba vidare från dem.)

    \( x+y+z=28 \) och \( 2y+4x =20 \) vilket ger

    \( \left\{ \begin{array}{rcl} x & = & 28-n \\ y & = & -10+2n \\ z & = & 10-n \\ \end{array} \right. \)

    Eftersom \( x,y \) och \( x \) är heltal måste \( n \) vara 6,7,8 eller 9. Alltså (22,2,4), (21,4,3), (20,6,2) eller (19,8,1).

  8. För vilka värden på \( a \) i intervallet \( 11 < a < 19 \) saknar ekvationen \( 84x+990y=a \) lösningar?

    sgf(84,990)=6. Alltså måste \( a \) innehålla faktorn 6. \( a = 12 \) eller \( 18 \).