Zawartość

• Kroki
• Metoda 1 z 2: Algorytm dzielnika
• Metoda 2 z 2: Czynniki pierwsze
• Porady

Największy wspólny dzielnik (GCD) dwóch liczb całkowitych to największa liczba całkowita dzieląca każdą z tych liczb. Na przykład gcd dla 20 i 16 wynosi 4 (zarówno 16, jak i 20 mają duże dzielniki, ale nie są one wspólne - na przykład 8 jest dzielnikiem 16, ale nie dzielnikiem 20). Istnieje prosta i systematyczna metoda znajdowania GCD, zwana „algorytmem Euklidesa”. W tym artykule dowiesz się, jak znaleźć największy wspólny dzielnik dwóch liczb całkowitych.

Kroki

Metoda 1 z 2: Algorytm dzielnika

1. 1 Pomiń wszelkie znaki minusa.
2. 2 Poznaj terminologię: przy dzieleniu 32 przez 5,
   • 32 - dywidenda
   • 5 - dzielnik
   • 6 - prywatny
   • 2 - reszta
3. 3 Określ większą z liczb. Będzie podzielna, a mniejsza liczba będzie dzielnikiem.
4. 4 Zapisz następujący algorytm: (dywidenda) = (dzielnik) * (iloraz) + (reszta)
5. 5 Umieść większą liczbę w miejscu dywidendy i mniejszą liczbę w miejscu dzielnika.
6. 6 Znajdź, ile razy większa liczba jest podzielona przez mniejszą i wpisz wynik zamiast ilorazu.
7. 7 Znajdź resztę i zapisz ją w odpowiedniej pozycji w algorytmie.
8. 8 Napisz algorytm ponownie, ale (A) zapisz poprzedni dzielnik jako nową dzielną i (B) poprzednią resztę jako nowy dzielnik.
9. 9 Powtarzaj poprzedni krok, aż reszta wynosi 0.
10. 10 Ostatni dzielnik będzie największym wspólnym dzielnikiem (NWD).
11. 11 Na przykład znajdźmy GCD dla 108 i 30:
12. 12 Zwróć uwagę, jak liczby 30 i 18 z pierwszego wiersza tworzą drugi wiersz. Następnie 18 i 12 tworzą trzeci rząd, a 12 i 6 tworzą czwarty rząd. Wielokrotności 3, 1, 1 i 2 nie są używane. Reprezentują one, ile razy dywidenda jest podzielna przez dzielnik, a zatem są unikatowe dla każdego wiersza.

Metoda 2 z 2: Czynniki pierwsze

1. 1 Pomiń wszelkie znaki minusa.
2. 2 Znajdź czynniki pierwsze liczb. Przedstaw je tak, jak pokazano na obrazku.
   • Na przykład dla 24 i 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2x3x3
   • Na przykład dla 50 i 35:
     • 50-2x5x5
     • 35-5x7
3. 3 Znajdź wspólne czynniki pierwsze.
   • Na przykład dla 24 i 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Na przykład dla 50 i 35:
     • 50 - 2x 5 x 5
     • 35- 5 x 7
4. 4 Pomnóż wspólne czynniki pierwsze.
   • Przez 24 i 18 lat pomnóż 2 oraz 3 i dostać 6... 6 jest największym wspólnym mianownikiem 24 i 18.
   • Nie ma co pomnożyć przez 50 i 35. 5 Jest jedynym wspólnym czynnikiem pierwszym i jest to NWD.
5. 5 Zrobiony!

Porady

• Jednym ze sposobów zapisania tego jest: dywidenda> mod dzielnik> = reszta; GCD (a, b) = b jeśli mod b = 0 i gcd (a, b) = gcd (b, a mod b) w przeciwnym razie.
• Jako przykład znajdźmy GCD (-77,91). Najpierw użyj 77 zamiast -77: GCD (-77,91) konwertuje na GCD (77,91). 77 to mniej niż 91, więc musimy je zamienić, ale zastanów się, jak działa algorytm, jeśli tego nie zrobimy. Obliczając 77 mod 91, otrzymujemy 77 (77 = 91 x 0 + 77). Ponieważ to nie jest zero, rozważamy sytuację (b, a mod b), to znaczy GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 to reszta). To nie jest zero, więc GCD (91,77) staje się GCD (77,14). 77 mod 14 = 7. To nie jest zero, więc GCD (77,14) staje się GCD (14,7). 14 mod 7 = 0 (od 14/7 = 2 bez reszty). Odpowiedź: NWD (-77,91) = 7.
• Opisana metoda jest bardzo przydatna do upraszczania ułamków. W powyższym przykładzie: -77/91 = -11/13, ponieważ 7 jest największym wspólnym mianownikiem -77 i 91.
• Jeśli a i b są równe zero, to każda niezerowa liczba jest ich dzielnikiem, więc w tym przypadku nie ma NWD (matematycy po prostu uważają, że największym wspólnym dzielnikiem 0 i 0 jest 0).