Największy wspólny dzielnik

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Największy wspólny dzielnik

Post autor: max123321 »

Największy wspólny dzielnik liczb naturalnych \(\displaystyle{ a, b, c}\) jest równy \(\displaystyle{ 1}\). Udowodnij, że jeżeli zachodzi równość
\(\displaystyle{ ab = c(b − a),}\)
to liczba \(\displaystyle{ b-a}\) jest kwadratem liczby całkowitej.

Jak to zrobić? Może mi ktoś pomóc?
Ostatnio zmieniony 23 paź 2022, o 23:24 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Mateusz5324
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 26 sty 2023, o 18:37
Płeć: Mężczyzna
wiek: 15
Lokalizacja: Kraków
Pomógł: 3 razy

Re: Największy wspólny dzielnik

Post autor: Mateusz5324 »

Zacznijmy od tego, że \(\displaystyle{ c=0}\). Wynika to z faktu iż dla \(\displaystyle{ c \neq 0}\) po przekształceniu uzyskamy \(\displaystyle{ \frac{ab}{c}=b-a}\). Jako że największy wspólny dzielnik \(\displaystyle{ a,b,c}\) jest równy \(\displaystyle{ 1}\), to w szczególności \(\displaystyle{ c}\) nie może dzielić \(\displaystyle{ ab}\) bez reszty, więc \(\displaystyle{ \frac{ab}{c}}\) będzie liczbą niecałkowitą, a \(\displaystyle{ b-a}\) całkowitą, czyli uzyskaliśmy sprzeczność. Co dowodzi, że \(\displaystyle{ c=0}\). Wiedząc to prawa strona równania jest równa \(\displaystyle{ 0}\), więc \(\displaystyle{ a=0 \vee b=0}\). Rozważmy oba przypadki. Dla \(\displaystyle{ a=0}\) mamy \(\displaystyle{ a=0 \wedge c=0}\), jednakże aby największy wspólny dzielnik \(\displaystyle{ a,b,c}\) mógł wynosić \(\displaystyle{ 1}\), i aby liczby \(\displaystyle{ a,b,c}\) należały do naturalnych, to \(\displaystyle{ b=1}\). Teraz rozwarzmy \(\displaystyle{ 2}\) przypadek, w którym \(\displaystyle{ b=0}\). Dla tego przypadku mamy \(\displaystyle{ b=0 \wedge c=0}\), podobnie jak w poprzednim przypadku, aby największy wspólny dzielnik tych liczb mógłby być równy \(\displaystyle{ 1}\) i wszytskie z nich należały do naturanlych, to \(\displaystyle{ a=1}\). Co pozwala nam twierdzić, że istnieją tylko 2 trójki liczb \(\displaystyle{ a,b,c}\) spełnające warunki zadania, a są to \(\displaystyle{ (1,0,0)}\) i \(\displaystyle{ (0,1,0)}\). Dla pierwszej z nich \(\displaystyle{ b-a=0-1=-1}\), a dla drugiej \(\displaystyle{ b-a=1-0=1}\). Tutaj jednak napotykamy problem, bo jeśli i można(a nawet trzeba) się zgodzić, że liczba \(\displaystyle{ 1}\) jest kwadratem liczby całkowitej, to nie można tego powiedzieć o drugim wyniku, czyli \(\displaystyle{ -1}\), która nie jest kwadratem liczby całkowitej. Podsumowując \(\displaystyle{ b-a= \pm 1}\), ale niekoniecznie jest kwadratem liczby całkowitej. Mam nadzieję, że pomogłem :).
PS. Jeśli coś w moim rozwiązaniu jest dla Ciebie niezrozumiałe, to napisz, a postaram się lepiej wytłumaczyć.
3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

Re: Największy wspólny dzielnik

Post autor: 3a174ad9764fefcb »

Mateusz5324 pisze: 9 lut 2023, o 01:50 Jako że największy wspólny dzielnik \(\displaystyle{ a,b,c}\) jest równy \(\displaystyle{ 1}\), to w szczególności \(\displaystyle{ c}\) nie może dzielić \(\displaystyle{ ab}\) bez reszty, więc \(\displaystyle{ \frac{ab}{c}}\) będzie liczbą niecałkowitą
Czy największy wspólny dzielnik liczb \(2,3,6\), to nie jest \(1\)?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Największy wspólny dzielnik

Post autor: Premislav »

To jest całkiem proste. Z równości \(\displaystyle{ ab=c(b-a)}\) wynika, że wszystkie dzielniki pierwsze liczby \(\displaystyle{ b-a}\) są też dzielnikami pierwszymi liczby \(\displaystyle{ ab}\), a więc liczby \(\displaystyle{ a}\) lub liczby \(\displaystyle{ b}\). Jeśli pewna liczba pierwsza \(\displaystyle{ p}\) dzieli \(\displaystyle{ b}\), lecz nie dzieli \(\displaystyle{ a}\), to \(\displaystyle{ p\nmid(b-a)}\), analogicznie w przypadku gdy \(\displaystyle{ p}\) dzieli \(\displaystyle{ a}\), lecz nie dzieli \(\displaystyle{ b}\). Weźmy teraz taką liczbę pierwszą \(\displaystyle{ p}\), że \(\displaystyle{ p|a\wedge p|b}\). Powiedzmy, źe \(\displaystyle{ v_p(a)=x, \ v_p(b)=y}\) (innymi słowy, \(\displaystyle{ p^x|a \wedge p^{x+1}\nmid a}\) i analogicznie \(\displaystyle{ p^y|b\wedge p^{y+1}\nmid b}\). Liczba \(\displaystyle{ p}\) nie dzieli \(\displaystyle{ c}\), gdyż w przeciwnym razie byłoby \(\displaystyle{ \NWD(a,b,c)\ge p}\), a z założenia \(\displaystyle{ \NWD(a,b,c)=1}\). Stąd \(\displaystyle{ p^{x+y}|(b-a)}\) (bo \(\displaystyle{ p^{x+y}|ab \wedge \NWD\left(p^{x+y}, c\right)=1}\)) i \(\displaystyle{ p^{x+y+1}\nmid (b-a)}\).
Zapiszmy \(\displaystyle{ a=p^x \cdot a', \ b=p^y\cdot b'}\), gdzie \(\displaystyle{ p\nmid a', \ p\nmid b'}\). Przypuśćmy nie wprost, że \(\displaystyle{ x<y}\): wówczas
\(\displaystyle{ b-a=p^x\left(b'p^{y-x}-a'\right)}\) i naturalnie \(\displaystyle{ p\nmid p^{y-x}b'-a'}\), zatem \(\displaystyle{ x+y=v_p(b-a)\le x}\), sprzeczność.
Analogicznie wykluczamy \(\displaystyle{ x>y}\); musi być więc \(\displaystyle{ x=y}\).
Pozostaje przypomnieć, że \(\displaystyle{ p^{x+y+1}\nmid|(b-a)}\), bo \(\displaystyle{ p^{x+y+1}\nmid ab}\).
Zatem:
1) jedyne dzielniki pierwsze liczby \(\displaystyle{ b-a}\) to wspólne dzielniki pierwsze liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\);
2) dzielą one \(\displaystyle{ b}\) z takim samym wykładnikiem, co \(\displaystyle{ a}\), i w ogóle nie dzielą \(\displaystyle{ c}\).
Zatem \(\displaystyle{ b-a=\prod p_i^{2x_{i}}=\left(\prod p_i^{x_i}\right)^2}\), tj. \(\displaystyle{ b-a}\) jest pełnym kwadratem, c.n.d.
ODPOWIEDZ