Inhoud

• Stappen
• Deel 1 van 4: Hoe een vergelijking te schrijven
• Deel 2 van 4: Hoe het algoritme van Euclides te schrijven
• Deel 3 van 4: Hoe een oplossing te vinden met behulp van het algoritme van Euclides
• Deel 4 van 4: Vind oneindig veel andere oplossingen

Om een ​​lineaire Diophantische vergelijking op te lossen, moet u de waarden van de variabelen "x" en "y" vinden, die gehele getallen zijn. Een integere oplossing is complexer dan normaal en vereist een specifieke reeks acties. Eerst moet je de grootste gemene deler (GCD) van de coëfficiënten berekenen en dan een oplossing vinden. Als je eenmaal één geheeltallige oplossing voor een lineaire vergelijking hebt gevonden, kun je een eenvoudig patroon gebruiken om een ​​oneindig aantal andere oplossingen te vinden.

Stappen

Deel 1 van 4: Hoe een vergelijking te schrijven

1. 1 Schrijf de vergelijking op in standaardvorm. Een lineaire vergelijking is een vergelijking waarin de exponenten van de variabelen niet groter zijn dan 1. Om zo'n lineaire vergelijking op te lossen, schrijft u deze eerst in standaardvorm. De standaardvorm van een lineaire vergelijking ziet er als volgt uit: ${ displaystyle Ax + Door = C}$, waar ${ weergavestijl A, B}$ en ${ weergavestijl C}$ - hele getallen.
   • Als de vergelijking in een andere vorm wordt gegeven, breng deze dan naar de standaardvorm met behulp van elementaire algebraïsche bewerkingen. Bijvoorbeeld, gegeven de vergelijking ${ weergavestijl 23x + 4j-7x = -3j + 15}$... Geef vergelijkbare termen en schrijf de vergelijking als volgt: ${ weergavestijl 16x + 7y = 15}$.
2. 2 Vereenvoudig de vergelijking (indien mogelijk). Als je de vergelijking in standaardvorm schrijft, kijk dan naar de coëfficiënten ${ weergavestijl A, B}$ en ${ weergavestijl C}$... Als deze kansen een GCD hebben, deel dan alle drie de kansen erdoor. De oplossing voor zo'n vereenvoudigde vergelijking is ook de oplossing voor de oorspronkelijke vergelijking.
   • Als bijvoorbeeld alle drie de coëfficiënten even zijn, deel ze dan door ten minste 2. Bijvoorbeeld:
     • ${ weergavestijl 42x + 36y = 48}$ (alle leden zijn deelbaar door 2)
     • ${ weergavestijl 21x + 18y = 24}$ (nu zijn alle leden deelbaar door 3)
     • ${ weergavestijl 7x + 6y = 8}$ (deze vergelijking kan niet meer worden vereenvoudigd)
3. 3 Controleer of de vergelijking kan worden opgelost. In sommige gevallen kun je meteen stellen dat de vergelijking geen oplossingen heeft. Als de coëfficiënt "C" niet deelbaar is door de GCD van de coëfficiënten "A" en "B", heeft de vergelijking geen oplossingen.
   • Als bijvoorbeeld beide coëfficiënten ${ weergavestijl A}$ en ${ weergavestijl B}$ even zijn, dan is de coëfficiënt ${ weergavestijl C}$ moet gelijk zijn. Maar als ${ weergavestijl C}$ vreemd, dan is er geen oplossing.
     • De vergelijking ${ weergavestijl 2x + 4y = 21}$ geen integere oplossingen.
     • De vergelijking ${ weergavestijl 5x + 10y = 17}$ er zijn geen oplossingen voor gehele getallen omdat de linkerkant van de vergelijking deelbaar is door 5 en de rechterkant niet.

Deel 2 van 4: Hoe het algoritme van Euclides te schrijven

1. 1 Begrijp het algoritme van Euclides. Het is een reeks herhaalde delingen waarbij de vorige rest wordt gebruikt als de volgende deler. De laatste deler die de getallen integraal deelt, is de grootste gemene deler (GCD) van de twee getallen.
   • Laten we bijvoorbeeld de GCD van de nummers 272 en 36 vinden met behulp van het algoritme van Euclid:
     • ${ weergavestijl 272 = 7 * 36 + 20}$ - Deel het grotere getal (272) door het kleinere (36) en let op de rest (20);
     • ${ weergavestijl 36 = 1 * 20 + 16}$ - deel de vorige deler (36) door de vorige rest (20). Let op het nieuwe residu (16);
     • ${ weergavestijl 20 = 1 * 16 + 4}$ - deel de vorige deler (20) door de vorige rest (16). Let op het nieuwe residu (4);
     • ${ weergavestijl 16 = 4 * 4 + 0}$ - Deel de vorige deler (16) door de vorige rest (4). Aangezien de rest 0 is, kunnen we zeggen dat 4 de GCD is van de oorspronkelijke twee getallen 272 en 36.
2. 2 Pas het algoritme van Euclides toe op de coëfficiënten "A" en "B". Wanneer u de lineaire vergelijking in standaardvorm schrijft, bepaalt u de coëfficiënten "A" en "B" en past u het algoritme van Euclides daarop toe om de GCD te vinden. Bijvoorbeeld, gegeven een lineaire vergelijking ${ weergavestijl 87x-64y = 3}$.
   • Hier is het algoritme van Euclides voor coëfficiënten A = 87 en B = 64:
     • ${ weergavestijl 87 = 1 * 64 + 23}$
     • ${ weergavestijl 64 = 2 * 23 + 18}$
     • ${ weergavestijl 23 = 1 * 18 + 5}$
     • ${ weergavestijl 18 = 3 * 5 + 3}$
     • ${ weergavestijl 5 = 1 * 3 + 2}$
     • ${ weergavestijl 3 = 1 * 2 + 1}$
     • ${ weergavestijl 2 = 2 * 1 + 0}$
3. 3 Vind de grootste gemeenschappelijke factor (GCD). Aangezien de laatste deler 1 was, zijn GCD 87 en 64 1. Dus 87 en 64 zijn priemgetallen ten opzichte van elkaar.
4. 4 Analyseer het resultaat. Wanneer u de ggd-coëfficiënten vindt ${ weergavestijl A}$ en ${ weergavestijl B}$, vergelijk het met de coëfficiënt ${ weergavestijl C}$ de oorspronkelijke vergelijking. Indien ${ weergavestijl C}$ deelbaar door gcd ${ weergavestijl A}$ en ${ weergavestijl B}$, de vergelijking heeft een geheeltallige oplossing; anders heeft de vergelijking geen oplossingen.
   • Bijvoorbeeld, de vergelijking ${ weergavestijl 87x-64y = 3}$ kan worden opgelost omdat 3 deelbaar is door 1 (ggd = 1).
   • Stel bijvoorbeeld dat GCD = 5. 3 is niet deelbaar door 5, dus deze vergelijking heeft geen oplossingen voor gehele getallen.
   • Zoals hieronder wordt getoond, als een vergelijking één gehele oplossing heeft, heeft deze ook een oneindig aantal andere gehele oplossingen.

Deel 3 van 4: Hoe een oplossing te vinden met behulp van het algoritme van Euclides

1. 1 Nummer de stappen voor het berekenen van GCD. Om de oplossing van een lineaire vergelijking te vinden, moet u het Euclidische algoritme gebruiken als basis voor het substitutie- en vereenvoudigingsproces.
   • Begin met het nummeren van de stappen voor het berekenen van de GCD. Het rekenproces ziet er als volgt uit:
     • ${ displaystyle { text {Stap 1}}: 87 = (1 * 64) +23}$
     • ${ displaystyle { text {Stap 2}}: 64 = (2 * 23) +18}$
     • ${ displaystyle { text {Stap 3}}: 23 = (1 * 18) +5}$
     • ${ displaystyle { text {Stap 4}}: 18 = (3 * 5) +3}$
     • ${ displaystyle { text {Stap 5}}: 5 = (1 * 3) +2}$
     • ${ displaystyle { text {Stap 6}}: 3 = (1 * 2) +1}$
     • ${ displaystyle { text {Stap 7}}: 2 = (2 * 1) +0}$
2. 2 Besteed aandacht aan de laatste stap, waar er een rest is. Herschrijf de vergelijking voor deze stap om de rest te isoleren.
   • In ons voorbeeld is de laatste stap met rest stap 6. De rest is 1. Herschrijf de vergelijking in stap 6 als volgt:
     • ${ weergavestijl 1 = 3- (1 * 2)}$
3. 3 Isoleer de rest van de vorige stap. Dit proces is een stapsgewijze "beweging omhoog". Elke keer isoleert u de rest in de vergelijking in de vorige stap.
   • Isoleer de rest van de vergelijking in stap 5:
     • ${ weergavestijl 2 = 5- (1 * 3)}$ of ${ weergavestijl 2 = 5-3}$
4. 4 Vervang en vereenvoudig. Merk op dat de vergelijking in stap 6 het nummer 2 bevat, en in de vergelijking in stap 5 is het nummer 2 geïsoleerd. Dus in plaats van "2" in de vergelijking in stap 6, vervangt u de uitdrukking in stap 5:
   • ${ weergavestijl 1 = 3-2}$ (vergelijking van stap 6)
   • ${ weergavestijl 1 = 3- (5-3)}$ (in plaats van 2 is een uitdrukking vervangen)
   • ${ weergavestijl 1 = 3-5 + 3}$ (geopende haakjes)
   • ${ weergavestijl 1 = 2 (3) -5}$ (vereenvoudigd)
5. 5 Herhaal het vervangings- en vereenvoudigingsproces. Herhaal het beschreven proces, waarbij u in omgekeerde volgorde door het Euclidische algoritme gaat. Elke keer herschrijft u de vergelijking uit de vorige stap en voegt u deze toe aan de laatste vergelijking die u krijgt.
   • De laatste stap waar we naar keken was stap 5. Ga dus naar stap 4 en isoleer de rest in de vergelijking voor die stap:
     • ${ weergavestijl 3 = 18- (3 * 5)}$
   • Vervang deze uitdrukking door "3" in de laatste vergelijking:
     • ${ weergavestijl 1 = 2 (18-3 * 5) -5}$
     • ${ weergavestijl 1 = 2 (18) -6 (5) -5}$
     • ${ weergavestijl 1 = 2 (18) -7 (5)}$
6. 6 Ga verder met het vervangings- en vereenvoudigingsproces. Dit proces wordt herhaald totdat u de eerste stap van het Euclidische algoritme bereikt. Het doel van het proces is om de vergelijking te schrijven met de coëfficiënten 87 en 64 van de oorspronkelijke op te lossen vergelijking. In ons voorbeeld:
   • ${ weergavestijl 1 = 2 (18) -7 (5)}$
   • ${ weergavestijl 1 = 2 (18) -7 (23-18)}$ (vervangt de uitdrukking uit stap 3)
     • ${ weergavestijl 1 = 2 (18) -7 (23) +7 (18)}$
     • ${ weergavestijl 1 = 9 (18) -7 (23)}$
   • ${ weergavestijl 1 = 9 (64-2 * 23) -7 (23)}$ (vervangt de uitdrukking uit stap 2)
     • ${ weergavestijl 1 = 9 (64) -18 (23) -7 (23)}$
     • ${ weergavestijl 1 = 9 (64) -25 (23)}$
   • ${ weergavestijl 1 = 9 (64) -25 (87-64)}$ (vervangt de uitdrukking uit stap 1)
     • ${ weergavestijl 1 = 9 (64) -25 (87) +25 (64)}$
     • ${ weergavestijl 1 = 34 (64) -25 (87)}$
7. 7 Herschrijf de resulterende vergelijking in overeenstemming met de oorspronkelijke coëfficiënten. Wanneer u terugkeert naar de eerste stap van het Euclidische algoritme, zult u zien dat de resulterende vergelijking twee coëfficiënten van de oorspronkelijke vergelijking bevat. Herschrijf de vergelijking zodat de volgorde van de termen overeenkomt met de coëfficiënten van de oorspronkelijke vergelijking.
   • In ons voorbeeld is de oorspronkelijke vergelijking ${ weergavestijl 87x-64y = 3}$... Herschrijf daarom de resulterende vergelijking zodat de coëfficiënten op één lijn worden gebracht.Besteed speciale aandacht aan de coëfficiënt "64". In de oorspronkelijke vergelijking is deze coëfficiënt negatief en in het Euclidische algoritme is deze positief. Daarom moet de factor 34 negatief worden gemaakt. De uiteindelijke vergelijking wordt als volgt geschreven:
     • ${ displaystyle 87 (-25) -64 (-34) = 1}$
8. 8 Pas de juiste vermenigvuldiger toe om een ​​oplossing te vinden. Merk op dat in ons voorbeeld GCD = 1, dus de uiteindelijke vergelijking is 1. Maar de oorspronkelijke vergelijking (87x-64y) is 3. Daarom moeten alle termen in de uiteindelijke vergelijking met 3 worden vermenigvuldigd om de oplossing te krijgen:
   • ${ displaystyle 87 (-25 * 3) -64 (-34 * 3) = 1 * 3}$
   • ${ weergavestijl 87 (-75) -64 (-102) = 3}$
9. 9 Noteer de gehele oplossing van de vergelijking. De getallen die worden vermenigvuldigd met de coëfficiënten van de oorspronkelijke vergelijking zijn de oplossingen van die vergelijking.
   • Schrijf in ons voorbeeld de oplossing als een coördinatenpaar: ${ weergavestijl (x, y) = (- 75, -102)}$.

Deel 4 van 4: Vind oneindig veel andere oplossingen

1. 1 Begrijp dat er oneindig veel oplossingen zijn. Als een lineaire vergelijking één gehele oplossing heeft, dan moet deze oneindig veel gehele oplossingen hebben. Hier is een snel bewijs (in algebraïsche vorm):
   • ${ displaystyle Ax + Door = C}$
   • ${ weergavestijl A (x + B) + B (y-A) = C}$ (als u "B" optelt bij "x" en "A" van "y" aftrekt, verandert de waarde van de oorspronkelijke vergelijking niet)
2. 2 Noteer de oorspronkelijke x- en y-waarden. Het sjabloon voor het berekenen van de volgende (oneindige) oplossingen begint met de enige oplossing die je al hebt gevonden.
   • In ons voorbeeld is de oplossing een paar coördinaten ${ weergavestijl (x, y) = (- 75, -102)}$.
3. 3 Voeg de "B"-factor toe aan de "x"-waarde. Doe dit om de nieuwe x-waarde te vinden.
   • In ons voorbeeld, x = -75 en B = -64:
     • ${ weergavestijl x = -75 + (- 64) = - 139}$
   • Dus de nieuwe waarde "x": x = -139.
4. 4 Trek de "A"-factor af van de "y"-waarde. Om ervoor te zorgen dat de waarde van de oorspronkelijke vergelijking niet verandert, moet u bij het optellen van een getal bij "x" een ander getal van "y" aftrekken.
   • In ons voorbeeld, y = -102 en A = 87:
     • ${ weergavestijl y = -102-87 = -189}$
   • Dus de nieuwe waarde voor "y": y = -189.
   • Het nieuwe paar coördinaten wordt als volgt geschreven: ${ weergavestijl (x, y) = (- 139, -189)}$.
5. 5 Controleer de oplossing. Om te controleren of het nieuwe coördinatenpaar een oplossing is voor de oorspronkelijke vergelijking, vult u de waarden in de vergelijking in.
   • ${ weergavestijl 87x-64y = 3}$
   • ${ displaystyle 87 (-139) -64 (-189) = 3}$
   • ${ weergavestijl 3 = 3}$
   • Aangezien aan de gelijkheid is voldaan, is de beslissing correct.
6. 6 Schrijf uitdrukkingen op om veel oplossingen te vinden. De "x"-waarden zijn gelijk aan de oorspronkelijke oplossing plus een veelvoud van de "B"-factor. Dit kan worden geschreven als de volgende uitdrukking:
   • x (k) = x + k (B), waarbij "x (k)" de reeks "x" -waarden is en "x" de originele (eerste) waarde van "x" die je hebt gevonden.
     • In ons voorbeeld:
     • ${ displaystyle x (k) = - 75-64k}$
   • y (k) = y-k (A), waarbij y (k) de verzameling y-waarden is en y de originele (eerste) y-waarde is die je hebt gevonden.
     • In ons voorbeeld:
     • ${ weergavestijl y (k) = - 102-87k}$