algorytm Euklidesa
-
pool
- Użytkownik
- Posty: 185
- Rejestracja: 11 lis 2007, o 11:41
- Płeć: Mężczyzna
- Lokalizacja: z google :]
- Podziękował: 78 razy
algorytm Euklidesa
Stosując algorytm Euklidesa wyznacz liczby całkowite x i y spełniające równość \(\displaystyle{ 966x-686y=70}\)
Ostatnio zmieniony 18 lis 2008, o 21:28 przez pool, łącznie zmieniany 1 raz.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
algorytm Euklidesa
Mamy:
\(\displaystyle{ 966= 1 686 + 280 \\
686 = 2 280 + 126 \\
280 = 2 126 + 28 \\
126 = 4 28 + 14 \\
28 = 2 14}\)
Zatem:
\(\displaystyle{ 14 = 126 - 4 28 = 126 - 4(280 - 2 126) = \\ = 9 126 - 4\cdot 280 = 9 (686 - 2 280) - 4 280 = \\ = 9 686 - 22 280 = 9 686 - 22(966 - 686) = \\ = 31 686 - 22 966}\)
A skoro \(\displaystyle{ 14=31 686 - 22 966}\), to:
\(\displaystyle{ 70 = 155 686 - 110 966}\)
czyli \(\displaystyle{ x=-110, y=155}\)
Q.
\(\displaystyle{ 966= 1 686 + 280 \\
686 = 2 280 + 126 \\
280 = 2 126 + 28 \\
126 = 4 28 + 14 \\
28 = 2 14}\)
Zatem:
\(\displaystyle{ 14 = 126 - 4 28 = 126 - 4(280 - 2 126) = \\ = 9 126 - 4\cdot 280 = 9 (686 - 2 280) - 4 280 = \\ = 9 686 - 22 280 = 9 686 - 22(966 - 686) = \\ = 31 686 - 22 966}\)
A skoro \(\displaystyle{ 14=31 686 - 22 966}\), to:
\(\displaystyle{ 70 = 155 686 - 110 966}\)
czyli \(\displaystyle{ x=-110, y=155}\)
Q.