Dwa zadania z teorii liczb z NWD.

[tortoise]

Witam
Jeżeli ktoś znalazłby chwilkę wolnego czasu, to prosiłbym o krótką pomoc /wskazówka, rada - nie chcę gotowego rozwiązania. Na razie./ do dwóch zadań. Niestety na wykładzie nie mogłem wszystkiego zapisać i mam wątpliwości.

1. Znaleźć parę liczb \(\displaystyle{ (u, v): u \neq 5 \vee v \neq 7}\), że\(\displaystyle{ NWD(1492, 1066)=1492u + 1066v}\).

Dodam, że doszedłem do rozwiązania \(\displaystyle{ u=5, v=-7}\), które jest jednak niezgodne z założeniem.

2. Dowieść, że\(\displaystyle{ NWD(a _{1},...,a _{k}) = NWD[NWD(a _{1},a _{2}),a _{3},...,a _{k})]}\)

Pozdrawiam

[Lider Artur]

a) algorytm Euklidesa. Poczytaj trochę na ten temat, na pewno znajdziesz sposób wskazania innych liczb.

[eMaerthin]

b) własność NWD: Gdy dane mamy liczby naturalne \(\displaystyle{ a,b}\), wtedy:
\(\displaystyle{ a=NWD(a,b)\cdot c}\),
\(\displaystyle{ b=NWD(a,b)\cdot d}\)
oraz \(\displaystyle{ NWD(c,d)=1}\)

(Otrzymane w powyższy sposób liczby naturalne \(\displaystyle{ c}\) i \(\displaystyle{ d}\) są już względnie pierwsze).