szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 18 kwi 2007, o 23:33 
Użytkownik

Posty: 6607
Prosze o porzadne rozwiazanie tego zadanka, gdyz nawet nie wiem jak sie za nie zabrac :)
Wykaż, że jeśli x i y są dowolnymi liczbami naturalnymi, z których co najmniej jedna jest różna od zera, to dla dowolnej liczby całkowitej k zachodzi równość: NWD(x,y)=NWD(x-ky,y).

Z gory dziekuje :) POZDRO
Góra
Instytut Matematyczny, Uniwersytet Wrocławski
Mężczyzna Offline
PostNapisane: 19 kwi 2007, o 00:04 
Gość Specjalny
Avatar użytkownika

Posty: 2973
Lokalizacja: Suchedniów/Kraków
Sprobuj indukcyjnie.

A poza tym to raczej teoria liczb, zapewne moderatorzy zechca przeniesc watek. :)
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2007, o 14:05 
Użytkownik

Posty: 6607
Nie za bardzo wiem jak to zrobic indukcja :( Prosze o jakies dluzsze wypowiedzi potwierdzone najlepiej jakimis obliczeniami, itp :) POZDRO
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2007, o 15:46 
Gość Specjalny
Avatar użytkownika

Posty: 3306
Lokalizacja: Lebendigentanz
Niewprost:

Niech:
NWD(x, y) = q\\
NWD(x - ky, y) = p

Dla przykładu załóżmy, że p > q.

Oczywiście jest:
y \equiv 0 \pmod{p}\\
x - ky \equiv 0 \pmod{p}
czyli (mnożymy pierwszą kongruencję stronami razy k i dodajemy stronami do drugiej):
x \equiv 0 \pmod{p}
zatem zarówno x jak i y dzielą się przez p, co jest sprzeczne z założeniami:
NWD(x, y) = q \ \vee \ p > q.
Otrzymana sprzeczność dowodzi, że nie może być p > q, podobnie wykazujemy, że nie może być też p < q, a zatem jest p = q
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2007, o 22:48 
Użytkownik

Posty: 6607
Dzieki ale nic z tego zapisu nie rozumiem :( Nie wiem co to jest mod a tym bardziej kongruencja... Mimo wszystko dzieki :) Sa jakies inne mozliwosci rozwiazania?? POZDRO
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2007, o 00:07 
Gość Specjalny
Avatar użytkownika

Posty: 2973
Lokalizacja: Suchedniów/Kraków
a\equiv b\pmod{c}\Longleftrightarrow c|a-b.
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2007, o 15:55 
Gość Specjalny
Avatar użytkownika

Posty: 3306
Lokalizacja: Lebendigentanz
A jeśli dalej jest niejasne, to rozumowanie z kongruencjami można zapisać bez nich, w taki opisowy sposób:

Skoro y jest podzielne przez p, to liczba ky też jest podzielna przez p, więc ponieważ x - ky jest również podzielne przez p, to także x jest podzielne przez p
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2007, o 21:45 
Użytkownik

Posty: 6607
OK :) Teraz ju zrozumiem. Plus dla ciebie :P POZDRO
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Największy wspólny dzielnik - zadanie 2  marta147  5
 Największy wspólny dzielnik  alexandra  1
 Największy wspólny dzielnik - zadanie 18  jezarek  4
 Najwiekszy wspólny dzielnik - zadanie 12  freevolity  4
 Największy wspólny dzielnik - zadanie 15  Justyna2010  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com