Największy wspólny dzielnik Jakub: Dzień dobry, mam problem ze specyficznym zadanie, proszę o pomoc: Udowodnij, że dla dowolnych liczb Naturalnych x,y,z gdzie nie równają się one 0, zachodzi: NWD(x,NWD(y,z)) = NWD(z,NWD(x,y))

Jakub: Ktoś potrafi to może zrobić? Myślałem nad algorytmem Euklidesa, ale nie wiem jakby mógł się tutaj przydać

Blee: Niech: NWD(y,z) = k ⇔ y = k*a ∧ z = k*b ∧ NWD(a,b) = 1 (oczywiście k,a,b ∊Z) NWD(x,k) = n ⇔ x = n*c ∧ k = n*d ∧ NWD(c,d) = 1 (oczywiście n,c,d ∊Z) wtedy NWD(x,y) = NWD(n*c, n*d*a) = n*f gdzie c = f*g ∧ a = f*h ∧ NWD(g,h) = 1 NWD(z , n*f) = NWD( k*b , n*f) = NWD( n*d*b , n*f) = n ponieważ NWD(d,c) = 1 więc NWD(d,f) = 1 oraz NWD(a,b) = 1 więc NWD(c,b) = 1 więc NWD(f,b) = 1 c.n.w.

Blee: Szczerze mówiąc to nie wiem na ile 'mocny' jest taki dowód

jc: A gdyby pokazać, że NWD(x, NWD(y,z))=NWD(x,y,z)? wtedy równość byłaby oczywista. d|NWD(x,y,z) ⇔ d|x, d|y, d|z ⇔ d|x i d|NWD(y,z) ⇔ d|NWD(x,NWD(y,z))

Jakub: hymmm, dziękuję za odpowiedzi, ale jc, czy d|NWD(x,y,z) ⇔ d|x, d|y, d|z ⇔ d|x i d|NWD(y,z) ⇔ d|NWD(x,NWD(y,z)) pokazuje nam na pewno, że NWD(x, NWD(y,z))=NWD(x,y,z)? Czy tylko, że d dzieli i NWD(x, NWD(y,z)) i NWD(x,y,z)

jc: Może faktycznie? Ale jestem pewny, że równość NWD(x, NWD(y,z))=NWD(x,y,z) jest prawdziwa i na pewno łatwa do udowodnienia.

jc: L=nwd(x,y,z) ⇒L|x i L|y i L|z ⇒L|x i L|nwd(y,z) ⇒ L|nwd(x, nwd(y,z)) nwd(x,y,z) | nwd(x, nwd(y,z)) podobnie nwd(x, nwd(y,z)) | nwd(x,y,z) stąd równość Przyjąłem jako fakt, że jeśli d|a, i d|b, to d|nwd(a,b). Wynika to z faktu, że nwd(a,b)=ka+mb dla pewnych k,m.

Jakub: to ma sens, dzięki wielkie

Jakub: czyli k i m to ułamki?

jc: k i m to liczby całkowite.