wyznaczanie wszystkich liczb takich, że....
: 7 lut 2011, o 13:02
Witam. Mam pewien "mały" problem z takim zadankiem.
Należy wyznaczyć wszystkie liczby całkowite x, y takie, że \(\displaystyle{ 31x+13y=1}\)
Doszedłem do tego, żeby rozwiązać to w ten sposób, że:
\(\displaystyle{ 31 = 2*13 +5
13=2*5 + 3
5=1*3 + 2
3=1*2 + 1
2=1*2+0}\)
i tu właśnie pojawia się problem, a mianowicie rozszerzony algorytm euklidesa:
\(\displaystyle{ 1=3-(1*2)=3-(1*(5-(1*3)))=3-(1*(5-(1*(13-2*5))))=3-(1*(5-(1*(13-2*(31-2*13)))))}\)
Nie mam pojęcia co z tym dalej zrobić, o ile wogóle dobrze to robię.... Należałoby to chyba jakoś pogrupować... ale jak? Prosiłbym o dość proste wytłumaczenie ;D
Pozdrawiam
Należy wyznaczyć wszystkie liczby całkowite x, y takie, że \(\displaystyle{ 31x+13y=1}\)
Doszedłem do tego, żeby rozwiązać to w ten sposób, że:
\(\displaystyle{ 31 = 2*13 +5
13=2*5 + 3
5=1*3 + 2
3=1*2 + 1
2=1*2+0}\)
i tu właśnie pojawia się problem, a mianowicie rozszerzony algorytm euklidesa:
\(\displaystyle{ 1=3-(1*2)=3-(1*(5-(1*3)))=3-(1*(5-(1*(13-2*5))))=3-(1*(5-(1*(13-2*(31-2*13)))))}\)
Nie mam pojęcia co z tym dalej zrobić, o ile wogóle dobrze to robię.... Należałoby to chyba jakoś pogrupować... ale jak? Prosiłbym o dość proste wytłumaczenie ;D
Pozdrawiam