Nieskracalność ułamka [wykazać]

[patry93]

Witam

Liczby całkowite \(\displaystyle{ a,b,c,d}\) spełniają warunek \(\displaystyle{ ad-bc=1}\). Wykaż, że ułamek \(\displaystyle{ \frac{a^{2}+b^{2}}{ac+bd}}\) jest nieskracalny.

Wiem, że aby ułamek był nieskracalny, to \(\displaystyle{ NWD(a^{2}+b^{2} \ , \ ac+bd) = 1}\), lecz nie mam pomysłu co robić dalej.... :/

Z góry dziękuję za odpowiedzi.

[Sylwek]

Z warunku \(\displaystyle{ ad-bc=1}\) wynika, że \(\displaystyle{ (a,b)=(a,c)=(d,b)=(d,c)=1}\), gdyż jakby miały jakiś wspólny dzielnik d>1, to prawa strona też byłaby podzielna przez d - ale jest ona jedynką - sprzeczność.

Mamy zatem:
\(\displaystyle{ (a^2+b^2,ac+bd) (a^2c+b^2c,a^2c+abd)}\) (nwd rośnie lub jest takie samo, gdyż domnożyliśmy nowe liczby).

Ale (z Euklidesa):
\(\displaystyle{ (a^2c+b^2c,a^2c+abd)=(a^2c+b^2c,a^2c+abd-a^2c-b^2c)=(a^2c+b^2c,abd-b^2c)=(a^2c+b^2c,b(ad-bc))=(a^2c+b^2c,b)=1}\)
- gdyż b jest względnie pierwsze z \(\displaystyle{ a^2c}\).

Czyli \(\displaystyle{ (a^2+b^2,ac+bd) 1}\), do oznacza, że: \(\displaystyle{ (a^2+b^2,ac+bd)=1}\).

Zanim o coś zapytasz, przeanalizuj dokładnie całe rozwiązanie

[liu]

Przypomnijmy sobie, ze na to, aby dwie liczby k,l byly wzglednie pierwsze potrzeba i wystarcza, aby rownanie \(\displaystyle{ xk + yl=1}\) mialo rozwiazanie w liczbach calkowitych x,y. Warunek z tresci zadania oznacza, ze

\(\displaystyle{ \det ft[ \begin{array}{cc} a & b \\ c & d \end{array}\right] = 1}\). Oznaczmy te macierz przez A
Zwrocmy ponadto uwage na fakt, ze \(\displaystyle{ \det A = \det A^T}\), gdzie T oznacza transpozycje macierzy. Zatem
\(\displaystyle{ 1 = \det A \det A^T = \det AA^t = \det ft[ \begin{array}{cc} a^2 + b^2 & ac+bd \\ ac+bd & c^2 + d^2 \end{array}\right] = (c^2+d^2)(a^2+b^2) - (ac+bd)(ac+bd)}\),
czyli rownanie z poczatkowej uwagi dla \(\displaystyle{ k=a^2+b^2, l=ac+bd}\) ma rozwiazanie w liczbach calkowitych, czyli liczby te sa wzglednie pierwsze.

Wykazalismy tutaj troche wiecej, mianowicie rowniez to, ze ulamek \(\displaystyle{ \frac{c^2+d^2}{ac+bd}}\) jest nieskracalny.

[patry93]

Z warunku ad-bc=1 wynika, że (a,b)=(a,c)=(d,b)=(d,c)=1, gdyż jakby miały jakiś wspólny dzielnik d>1, to prawa strona też byłaby podzielna przez d - ale jest ona jedynką - sprzeczność.

Domyślam się, że pary liczb, które podałeś w nawiasach oznaczają NWD tych dwóch liczb, tak?
Nie rozumiem skąd wziąłeś to, że NWD tych par musi się równać 1... skąd wiadomo, że jeśli jedna para miałaby dzielnik >1 to równość nie zajdzie?

Mamy zatem:
(a^2+b^2,ac+bd) (a^2c+b^2c,a^2c+abd) (nwd rośnie lub jest takie samo, gdyż domnożyliśmy nowe liczby).

Kompletnie nie rozumiem dlaczego domnożyliśmy nowe liczby, dlaczego akurat tak i dlaczego tam? :/

Ale (z Euklidesa):

Tzn.? To jest z jakiegoś twierdzenie Euklidesa?

Zanim o coś zapytasz, przeanalizuj dokładnie całe rozwiązanie

Nie rozumiem dlaczego to napisałeś... Czyżby chodziło o zadanie z kolorowaniem? Jeśli tak, to powiem Ci, że nadal nie zrozumiałem tego, co napisałeś... aktualnie próbuję zrozumieć indukcję, więc może niebawem pojmę Twoje rozwiązanie.

[ Dodano: 4 Października 2008, 17:09 ]
liu - ojej, niestety takie rozwiązanie nie dla mnie Gdzie tam mi do macierzy...

[liu]

qwertyuiopp, chodzi tutaj zapewne o algorytm Euklidesa, ktory mowi w sumie tyle, ze
\(\displaystyle{ NWD(a,b) = NWD(a-b,b)}\)

A co do rozwiazania, to przepraszam, nie zwrocilem uwagi na wiek. Ale da sie to chyba jakos przetlumaczyc na jezyk bez macierzy, kwestia tego, ze ja akurat tak wpadlem na to rozwiazanie Sprobuj moze rozbic jakos \(\displaystyle{ (ad-bc)^2}\) na sume wyrazen \(\displaystyle{ costam\cdot (a^2+b^2)}\) i \(\displaystyle{ innecostam (ac+bd)}\)

[limes123]

\(\displaystyle{ (a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2\iff (a^2+b^2)(c^2+d^2)=(ac+bd)^2+1}\) czyli jesli \(\displaystyle{ (a^2+b^2,ac+bd)=d}\) to d dzieli 1 ckd

[Sylwek]

Domyślam się, że pary liczb, które podałeś w nawiasach oznaczają NWD tych dwóch liczb, tak?

Tak, \(\displaystyle{ NWD(a,b)}\) oznaczamy \(\displaystyle{ (a,b)}\).

dlaczego domnożyliśmy nowe liczby, dlaczego akurat tak i dlaczego tam

Odpowiedź na wszystkie 3: w celu rozwiązania zadania (kwestia tego co i gdzie domnożyć, to kwestia wyczucia, gdzie możemy później wykorzystać założenie zadania).

Tzn.? To jest z jakiegoś twierdzenie Euklidesa?

Poczytaj o Algorytmie Euklidesa.

P.S. Rozwiązanie post wyżej najbardziej elementarne.