Kilka zadań z NWW i NWD

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
Tristan
Użytkownik
Użytkownik
Posty: 2353
Rejestracja: 24 kwie 2005, o 14:28
Płeć: Mężczyzna
Podziękował: 27 razy
Pomógł: 557 razy

Kilka zadań z NWW i NWD

Post autor: Tristan »

1. Pokazać, że \(\displaystyle{ NWD(a,b) NWW(a,b)=ab}\). Czy ten fakt jest prawdziwy dla trzech liczb naturalnych?
2. Udowodnić, że dla dowolnych liczb naturalnych \(\displaystyle{ a,b,c}\) zachodzą równości:
a) \(\displaystyle{ NWW(a,b,c)=\frac{ abc NWD(a,b,c) }{ NWD(a,b) NWD(a,c) NWD(b,c)}\)
b) \(\displaystyle{ NWD(a,b) NWD(a,c) NWD(b,c) NWW(a,b) NWW(a,c) NWW(b,c)=(abc)^2}\)

Ja naprawdę widzę, że jeżeli pokażemy 1. to 2.b) wychodzi natychmiast - ale dla pewności daję, bo może ja źle widzę...

3. Wykazać, że jeśli liczby \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są względnie pierwsze, to \(\displaystyle{ NWD(11a+2b, 18a+5b)}\) jest równy 1 lub 19.
Awatar użytkownika
Lorek
Użytkownik
Użytkownik
Posty: 7150
Rejestracja: 2 sty 2006, o 22:17
Płeć: Mężczyzna
Lokalizacja: Ruda Śląska
Podziękował: 1 raz
Pomógł: 1322 razy

Kilka zadań z NWW i NWD

Post autor: Lorek »

Niech
\(\displaystyle{ \large a=2^{a_2}\cdot 3^{a_3}\cdot 5^{a_4}\cdots p^{a_p}\\b=2^{b_2}\cdot 3^{b_3}\cdot 5^{b_4}\cdots p^{b_p}}\)
(rozkład tych liczb na czynniki pierwsze)
wtedy
\(\displaystyle{ \large NWD(a,b)=2^{min(a_2,b_2)}\cdot 3^{min(a_3,b_3)}\cdots p^{min(a_p,b_p)}\\NWW(a,b)=2^{max(a_2,b_2)}\cdot 3^{max(a_3,b_3)}\cdots p^{max(a_p,b_p)}}\)
Czyli
\(\displaystyle{ \large NWD\cdot NWW=2^{min(a_2,b_2)}\cdot 2^{max(a_2,b_2)}\cdots p^{min(a_p,b_p)}\cdot p^{max(a_p,b_p)}=\\=2^{min(a_2,b_2)+max(a_2,b_2)}\cdots p^{min(a_p,b_p)+max(a_p,b_p)}}\)
korzystając z tego, że \(\displaystyle{ \large min(p,q)+max(p,q)=p+q}\)otrzymujemy

\(\displaystyle{ \large 2^{min(a_2,b_2)+max(a_2,b_2)}\cdots p^{min(a_p,b_p)+max(a_p,b_p)}=2^{a_2+b_2}\cdots p^{a_p+b_p}=2^{a_2}\cdots p^{a_p}\cdot 2^{b_2}\cdots p^{b_p}=ab}\)
W podobny sposób można udowodnić, że to nie jest spełnione dla 3 liczb naturalnych, bo
\(\displaystyle{ min(p,q,r)+max(p,q,r)\neq p+q+r}\),
no chyba, że przynajmniej 2 z tych liczb są zerami, ale wtedy mamy taką sytuację NWD(a,b,c)=NWD(1,1,c)=1 i NWW(a,b,c)=NWW(1,1,c)=c i abc=c
Ja naprawdę widzę, że jeżeli pokażemy 1. to 2.b) wychodzi natychmiast
Dobrze widzisz
Awatar użytkownika
DEXiu
Użytkownik
Użytkownik
Posty: 1174
Rejestracja: 17 lut 2005, o 17:22
Płeć: Mężczyzna
Lokalizacja: Jaworzno
Pomógł: 69 razy

Kilka zadań z NWW i NWD

Post autor: DEXiu »

2.a) też wychodzi natychmiast (chyba )
Awatar użytkownika
Tristan
Użytkownik
Użytkownik
Posty: 2353
Rejestracja: 24 kwie 2005, o 14:28
Płeć: Mężczyzna
Podziękował: 27 razy
Pomógł: 557 razy

Kilka zadań z NWW i NWD

Post autor: Tristan »

1. Dziękuję
2. Ja nie widzę tego, że 2a) od razu też wychodzi - mógłbyś pokazać?
3. Mógłby ktoś looknąć na zadanie trzecie? Przekształcam to algorytmem Euklidesa, ale jakoś do niczego nie dochodzę.
Awatar użytkownika
DEXiu
Użytkownik
Użytkownik
Posty: 1174
Rejestracja: 17 lut 2005, o 17:22
Płeć: Mężczyzna
Lokalizacja: Jaworzno
Pomógł: 69 razy

Kilka zadań z NWW i NWD

Post autor: DEXiu »

OK. Jednak nie jest takie natychmiastowe. Nie będę wszystkiego rozpisywał tak jak Lorek ale zasada identyczna:
Przyjmijmy, że pewna liczba \(\displaystyle{ p\in\mathbb{P}}\) występuje w rozkładach liczb \(\displaystyle{ a,\,b,\,c}\) odpowiednio w potęgach \(\displaystyle{ \alpha,\,\beta,\,\gamma}\). Aby udowodnić prawdziwość równości 2.a) wystarczy że pokażemy, że:
\(\displaystyle{ \max\{\alpha,\beta,\gamma\}=\alpha+\beta+\gamma+\min\{\alpha,\beta,\gamma\}-\min\{\alpha,\beta\}-\min\{\alpha,\gamma\}-\min\{\beta,\gamma\}}\)
Ponieważ \(\displaystyle{ \alpha,\,\beta,\,\gamma}\) zmieniają się w poszczególnych składnikach cyklicznie (występuje symetria ról), możemy przyjąć bez straty ogólności, że \(\displaystyle{ \alpha\leq\beta\leq\gamma}\). Teraz podstawiamy co trzeba do równości i wychodzi co należało
Ostatnio zmieniony 20 paź 2007, o 17:11 przez DEXiu, łącznie zmieniany 1 raz.
ODPOWIEDZ