Dowod NWD

[dzejkej]

Udowodnic dla wszystkich liczb naturalnych \(\displaystyle{ n \in N}\) :
\(\displaystyle{ NWD(12n+17,7n+10)=1}\)

Potrzebuje jakas podpowiedz jak to zaczac.

-- 4 sty 2012, o 15:02 --

Mam pewna idee:
\(\displaystyle{ NWD(12n+17,7n+10)=1}\)
\(\displaystyle{ 12n+17 = 1 \cdot 7n + 10 + 5n + 7}\)
\(\displaystyle{ 7n + 10 = 1 \cdot 5n + 7 + 2n + 3}\)
\(\displaystyle{ 5n + 7 = 2 \cdot 2n + 3 + n + 1}\)
\(\displaystyle{ 2n + 3 = 2 \cdot n + 1 + 1}\)
\(\displaystyle{ n +1= n+1 \cdot 1+0}\)

[marcinz]

Chyba chodziło o NWD. Jeżeli wstawisz nawiasy w odpowiednich miejscach (np. \(\displaystyle{ 2n + 3 = 2 \cdot (n + 1) + 1}\)) to rozwiązanie jet ok.

[dzejkej]

Teraz dobrze:

\(\displaystyle{ NWD(12n+17,7n+10)=1}\)
\(\displaystyle{ 12n+17 = 1 \cdot (7n + 10) + 5n + 7}\)
\(\displaystyle{ 7n + 10 = 1 \cdot (5n + 7) + 2n + 3}\)
\(\displaystyle{ 5n + 7 = 2 \cdot (2n + 3) + n + 1}\)
\(\displaystyle{ 2n + 3 = 2 \cdot (n + 1) + 1}\)
\(\displaystyle{ n +1= 1 \cdot (n+1)}\)

Ale czy ja tu naprawde pokazalam to ci chcialam pokazac?

[marcinz]

Zastosowałaś zwykły algorytm Euklidesa, więc prawidłowo wyznaczyłaś NWD.

[dzejkej]

To juz koniec czy mozna to jeszcze dalej pociagnac, zeby bylo ladniej:

\(\displaystyle{ NWD(12n+17,7n+10)=1}\)
\(\displaystyle{ 12n+17 = 1 \cdot (7n + 10) + 5n + 7}\)
\(\displaystyle{ 7n + 10 = 1 \cdot (5n + 7) + 2n + 3}\)
\(\displaystyle{ 5n + 7 = 2 \cdot (2n + 3) + n + 1}\)
\(\displaystyle{ 2n + 3 = 2 \cdot (n + 1) + 1}\)
\(\displaystyle{ n +1= 1 \cdot (0n + 1) + n}\)
\(\displaystyle{ 1=0 \cdot (n + 1) + 1}\)
\(\displaystyle{ \Rightarrow 1=1}\)

Czy to juz zbedne?

[marcinz]

\(\displaystyle{ 2n + 3 = 2 \cdot (n + 1) + 1}\)
\(\displaystyle{ n +1= 1 \cdot (0n + 1) + n}\)

Ostatnia linijka jest zła (Tak się nie robi w algorytmie). Dobrze jest tak jak było na początku.