Wykaż podzielność liczb

[SuperM4n]

Witam,
mam polecenie: "Niech \(\displaystyle{ a,b}\) i \(\displaystyle{ c}\) będą dodatnimi liczbami naturalnymi. Wykazać, ze jeśli \(\displaystyle{ c|a}\) i \(\displaystyle{ c|b}\), to \(\displaystyle{ c|(a,b)}\), gdzie \(\displaystyle{ (a,b)}\) jest największym wspólnym dzielnikiem liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\)."


Z \(\displaystyle{ c|a}\) wynika, że \(\displaystyle{ a=ck}\)
Z \(\displaystyle{ c|b}\) wynika, że \(\displaystyle{ b=cl}\)
Z \(\displaystyle{ (a,b)=d}\) wynika, że \(\displaystyle{ d|a}\) i \(\displaystyle{ d|b}\), czyli \(\displaystyle{ a=di}\) i \(\displaystyle{ b=dj}\). Liczba \(\displaystyle{ d}\) jest również NWD, a więc każdy inny dzielnik \(\displaystyle{ a}\) i \(\displaystyle{ b}\) musi być mniejszy bądź równy \(\displaystyle{ d}\). Niestety, nie potrafię całości połączyć, aby rozwiązać zadanie. Czy ktoś mógłby mnie naprowadzić?

[Zahion]

\(\displaystyle{ c | di}\) i \(\displaystyle{ c | dj}\) oraz wiemy, że \(\displaystyle{ \left( i,j\right) = 1}\)

[SuperM4n]

Nie do końca rozumiem, skąd wiadomo, ze \(\displaystyle{ (i,j)=1}\) i nie jest pewny, jak to wykorzystać.

[Zahion]

Z określenia liczb \(\displaystyle{ a, b}\). Gdyby liczby \(\displaystyle{ i, j}\) miały jakiś wspólny dzielnik, załóżmy z góry, że jest to ich największy wspólny dzielnik, przykładowo \(\displaystyle{ k}\), to \(\displaystyle{ NWD\left( a,b\right)= dk}\), natomiast mamy inne założenie. Można założyć przeciwnie, że \(\displaystyle{ c}\) nie dzieli \(\displaystyle{ d}\), wtedy musi być \(\displaystyle{ c | i}\) oraz \(\displaystyle{ c | j}\), gdzie już zauważyliśmy, że \(\displaystyle{ \left( i, j\right) = 1}\), a tutaj już wystarczy kilka słów.

[SuperM4n]

Przepraszam, ale wciąż czegoś nie zauważam. Po podstawieniu jest \(\displaystyle{ di=ck}\) oraz \(\displaystyle{ dj=cl}\). Czyli \(\displaystyle{ (i,j) = 1}\) oznacza, że \(\displaystyle{ i}\) oraz \(\displaystyle{ j}\) są w tych równaniach równe \(\displaystyle{ 1}\)?

[Zahion]

Nie. Nie muszą być równe \(\displaystyle{ 1}\). Z warunku \(\displaystyle{ c|i}\) mamy, że w rozkładzie liczby \(\displaystyle{ c}\) na czynniki pierwsze występuje co najmniej jedna taka liczba pierwsza \(\displaystyle{ p_{i}}\), że \(\displaystyle{ p_{i} | i}\). Dalej z warunku \(\displaystyle{ c | j}\) mamy, że \(\displaystyle{ p_{i} | j}\), ale przecież \(\displaystyle{ \left( i, j\right) = 1}\), więc \(\displaystyle{ p_{i} = 1}\) i dochodzimy do faktu, że \(\displaystyle{ c = 1}\), a gdybyśmy założyli na początku, że \(\displaystyle{ c > 1}\) to mielibyśmy sprzeczność. Więc musi zachodzić \(\displaystyle{ c | d}\).