Najwiekszy wspolny dzielnik

[soku11]

Prosze o porzadne rozwiazanie tego zadanka, gdyz nawet nie wiem jak sie za nie zabrac
Wykaż, że jeśli x i y są dowolnymi liczbami naturalnymi, z których co najmniej jedna jest różna od zera, to dla dowolnej liczby całkowitej k zachodzi równość: NWD(x,y)=NWD(x-ky,y).

Z gory dziekuje POZDRO

[Tomasz Rużycki]

Sprobuj indukcyjnie.

A poza tym to raczej teoria liczb, zapewne moderatorzy zechca przeniesc watek.

[soku11]

Nie za bardzo wiem jak to zrobic indukcja Prosze o jakies dluzsze wypowiedzi potwierdzone najlepiej jakimis obliczeniami, itp POZDRO

[max]

Niewprost:

Niech:
\(\displaystyle{ NWD(x, y) = q\\
NWD(x - ky, y) = p}\)

Dla przykładu załóżmy, że \(\displaystyle{ p > q}\).

Oczywiście jest:
\(\displaystyle{ y \equiv 0 \pmod{p}\\
x - ky \equiv 0 \pmod{p}}\)
czyli (mnożymy pierwszą kongruencję stronami razy k i dodajemy stronami do drugiej):
\(\displaystyle{ x \equiv 0 \pmod{p}}\)
zatem zarówno \(\displaystyle{ x}\) jak i \(\displaystyle{ y}\) dzielą się przez \(\displaystyle{ p}\), co jest sprzeczne z założeniami:
\(\displaystyle{ NWD(x, y) = q \ \vee \ p > q}\).
Otrzymana sprzeczność dowodzi, że nie może być \(\displaystyle{ p > q}\), podobnie wykazujemy, że nie może być też \(\displaystyle{ p < q}\), a zatem jest \(\displaystyle{ p = q}\)

[soku11]

Dzieki ale nic z tego zapisu nie rozumiem Nie wiem co to jest mod a tym bardziej kongruencja... Mimo wszystko dzieki Sa jakies inne mozliwosci rozwiazania?? POZDRO

[Tomasz Rużycki]

\(\displaystyle{ a\equiv b\pmod{c}\Longleftrightarrow c|a-b}\).

[max]

A jeśli dalej jest niejasne, to rozumowanie z kongruencjami można zapisać bez nich, w taki opisowy sposób:

Skoro \(\displaystyle{ y}\) jest podzielne przez \(\displaystyle{ p}\), to liczba \(\displaystyle{ ky}\) też jest podzielna przez \(\displaystyle{ p}\), więc ponieważ \(\displaystyle{ x - ky}\) jest również podzielne przez \(\displaystyle{ p}\), to także \(\displaystyle{ x}\) jest podzielne przez \(\displaystyle{ p}\)

[soku11]

OK Teraz ju zrozumiem. Plus dla ciebie POZDRO