to chyba jest znane, ale nie pamietam skąd to jest:
wyznacz wszystkie pary liczb całkowtych o własności \(\displaystyle{ ab-1\mid a^2+b^2}\)
[Teoria liczb] wszystkie pary liczb całkowtych
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
Sylwek
- Użytkownik
- Posty: 2692
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 160 razy
- Pomógł: 664 razy
[Teoria liczb] wszystkie pary liczb całkowtych
Rozwiążę w naturalnych metodą nieskończonego schodzenia. W całkowitych trzeba się trochę bardziej pobawić, tzn. gdy a jest ujemne oraz b dodatnie, to trzeba znaleźć takie a,b, że: \(\displaystyle{ ab+1|a^2+b^2}\), co się robi analogicznie jak poniżej przedstawiony sposób, więc nie powinieneś mieć problemów.
Zatem niech \(\displaystyle{ a,b \ge 1}\), mamy oczywiście też: \(\displaystyle{ ab-1>0}\).
Niech dla pewnego \(\displaystyle{ k}\) będzie prawdą: \(\displaystyle{ a^2+b^2=k(ab-1)=kab-k}\) (np. dla a=2, b=1, k=5 jest OK, zatem takie k istnieje). Niech \(\displaystyle{ (a,b)=(x,y)}\) będzie parą o najmniejszej sumie, która spełnia powyższe równanie. Dla ustalenia uwagi (ponieważ jest symetria między zmiennymi a i b) niech będzie też: \(\displaystyle{ x \le y}\)
Teraz największa sztuczka zadania, zauważmy, że jeśli \(\displaystyle{ (a,b)=(x,y)}\) spełnia to równanie, to: \(\displaystyle{ (a,b)=(x,kx-y)}\) też je spełnia (można wstawić: \(\displaystyle{ (a,b)=(x,y-t)}\) i wyjdzie: \(\displaystyle{ t=2y-kx}\), sztuczkę warto zapamiętać).
Jako, że x+y było minimum, to:
\(\displaystyle{ x+y \le x+(kx-y) \Rightarrow 2y<kx \Rightarrow 2y^2<kxy \Rightarrow \\ \Rightarrow 2y^2-k = kxy-k=x^2+y^2 \Rightarrow y^2-k \le x^2 \Rightarrow x^2+y^2-k \le 2x^2 \Rightarrow \\ \Rightarrow kxy-k-k \le 2x^2}\)
Ale skoro \(\displaystyle{ y \ge x}\), to: \(\displaystyle{ 2x^2 \ge kxy-2k \ge kx^2-2k \Rightarrow x^2(2-k) \ge -2k}\)
Przypadki: \(\displaystyle{ k=1, k=2}\) można sprawdzić ręcznie (dokładniej: równanie \(\displaystyle{ a^2+b^2=k(ab-1)}\) dla \(\displaystyle{ k=1}\) czy \(\displaystyle{ k=2}\) nie ma rozwiązań naturalnych). Zatem niech \(\displaystyle{ k \ge 3}\). Wówczas przekształcając ostatnią nierówność:
\(\displaystyle{ x^2(2-k) \ge -2k \iff x^2 \le \frac{-2k}{2-k} = \frac{2k}{k-2} = 2+\frac{4}{k-2} \le 2+\frac{4}{3-2}=6}\)
Zatem: \(\displaystyle{ x^2 \le 6 \iff x \in \lbrace 1,2 \rbrace}\).
Gdy \(\displaystyle{ x=1}\), to wyjściowa podzielność to: \(\displaystyle{ y-1|y^2+1=(y-1)(y+1)+2 \Rightarrow y-1|2 \Rightarrow y=2 \vee y=3}\) - w obu przypadkach otrzymujemy: \(\displaystyle{ k=5}\).
Gdy \(\displaystyle{ x=2}\), to: \(\displaystyle{ 2y-1|y^2+4|4y^2+16=(2y-1)(2y+1)+17 \Rightarrow 2y-1|17 \Rightarrow y=1 \vee y=9}\), tutaj także w obu przypadkach \(\displaystyle{ k=5}\).
Zatem \(\displaystyle{ k=5}\) to jedyne możliwe rozwiązanie. Wszystkie rozwiązania równania: \(\displaystyle{ a^2+b^2=5ab-5}\) też się wyznacza metodą nieskończonego schodzenia, jednak już mi się nie chce pisać
Zatem niech \(\displaystyle{ a,b \ge 1}\), mamy oczywiście też: \(\displaystyle{ ab-1>0}\).
Niech dla pewnego \(\displaystyle{ k}\) będzie prawdą: \(\displaystyle{ a^2+b^2=k(ab-1)=kab-k}\) (np. dla a=2, b=1, k=5 jest OK, zatem takie k istnieje). Niech \(\displaystyle{ (a,b)=(x,y)}\) będzie parą o najmniejszej sumie, która spełnia powyższe równanie. Dla ustalenia uwagi (ponieważ jest symetria między zmiennymi a i b) niech będzie też: \(\displaystyle{ x \le y}\)
Teraz największa sztuczka zadania, zauważmy, że jeśli \(\displaystyle{ (a,b)=(x,y)}\) spełnia to równanie, to: \(\displaystyle{ (a,b)=(x,kx-y)}\) też je spełnia (można wstawić: \(\displaystyle{ (a,b)=(x,y-t)}\) i wyjdzie: \(\displaystyle{ t=2y-kx}\), sztuczkę warto zapamiętać).
Jako, że x+y było minimum, to:
\(\displaystyle{ x+y \le x+(kx-y) \Rightarrow 2y<kx \Rightarrow 2y^2<kxy \Rightarrow \\ \Rightarrow 2y^2-k = kxy-k=x^2+y^2 \Rightarrow y^2-k \le x^2 \Rightarrow x^2+y^2-k \le 2x^2 \Rightarrow \\ \Rightarrow kxy-k-k \le 2x^2}\)
Ale skoro \(\displaystyle{ y \ge x}\), to: \(\displaystyle{ 2x^2 \ge kxy-2k \ge kx^2-2k \Rightarrow x^2(2-k) \ge -2k}\)
Przypadki: \(\displaystyle{ k=1, k=2}\) można sprawdzić ręcznie (dokładniej: równanie \(\displaystyle{ a^2+b^2=k(ab-1)}\) dla \(\displaystyle{ k=1}\) czy \(\displaystyle{ k=2}\) nie ma rozwiązań naturalnych). Zatem niech \(\displaystyle{ k \ge 3}\). Wówczas przekształcając ostatnią nierówność:
\(\displaystyle{ x^2(2-k) \ge -2k \iff x^2 \le \frac{-2k}{2-k} = \frac{2k}{k-2} = 2+\frac{4}{k-2} \le 2+\frac{4}{3-2}=6}\)
Zatem: \(\displaystyle{ x^2 \le 6 \iff x \in \lbrace 1,2 \rbrace}\).
Gdy \(\displaystyle{ x=1}\), to wyjściowa podzielność to: \(\displaystyle{ y-1|y^2+1=(y-1)(y+1)+2 \Rightarrow y-1|2 \Rightarrow y=2 \vee y=3}\) - w obu przypadkach otrzymujemy: \(\displaystyle{ k=5}\).
Gdy \(\displaystyle{ x=2}\), to: \(\displaystyle{ 2y-1|y^2+4|4y^2+16=(2y-1)(2y+1)+17 \Rightarrow 2y-1|17 \Rightarrow y=1 \vee y=9}\), tutaj także w obu przypadkach \(\displaystyle{ k=5}\).
Zatem \(\displaystyle{ k=5}\) to jedyne możliwe rozwiązanie. Wszystkie rozwiązania równania: \(\displaystyle{ a^2+b^2=5ab-5}\) też się wyznacza metodą nieskończonego schodzenia, jednak już mi się nie chce pisać