zadania z NWD

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
pastorczyk
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 17 maja 2010, o 21:09
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

zadania z NWD

Post autor: pastorczyk »

Jakby ktoś mógł rzucić okiem i naprowadzić mnie na rozwiązaniem byłbym rad. Pewnie nie jest to aż takie trudne, ale jednak mi nie idzie.

1. \(\displaystyle{ a,b \in \mathbb{Z}, c \in \mathbb{N}}\). Udowodnij, że \(\displaystyle{ NWD(ac, bc) = NWD(a,b) \cdot c}\).

2. WYkaż, że \(\displaystyle{ NWD(5a + 4b,4a+3b) = 1 \Longleftrightarrow NWD(a,b) = 1}\).
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

zadania z NWD

Post autor: patry93 »

Napisz, jak Ci "nie idzie", tzn. co masz i gdzie się zatrzymujesz.
1. Czy widzisz, dlaczego to twierdzenie jest prawdziwe (tak, hm... na intuicję?). Jeśli tak, to reszta jest kwestią drobnych rachunków. Jeśli nie - pomyśl jak zadana równość ma się do definicji NWD.
2. Znasz algorytm Euklidesa?
pastorczyk
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 17 maja 2010, o 21:09
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

zadania z NWD

Post autor: pastorczyk »

1. No właśnie na intuicję wydaję się jasne, a takich rzeczy (w moim mniemaniu) dość trudno się dowodzi. Powiedzmy, że \(\displaystyle{ NWD(ac, bc) = d}\), czyli można napisać, że \(\displaystyle{ \exists x,y: ac = dx \ i \ bc = dy}\) ale jakoś nie widzę, żeby mnie to gdziekolwiek prowadziło. Intuicyjnie wszystko jest jasne i nietrudno znaleźć jakiś prosty przykład, ale jakoś mnie to nie zbliża do rozwiązania.

2. Algorytm Euklidesa znam, ale nie widzę jak miałbym go tutaj zastosować. \(\displaystyle{ NWD(5a + 4b, 4a + 3b) = NWD(4a + 3b, a + b) = NWD(a + b, a) = NWD(a,b) = 1}\). Czy gdzieś pobłądziłem?
pawels
Użytkownik
Użytkownik
Posty: 304
Rejestracja: 5 wrz 2009, o 20:15
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 3 razy
Pomógł: 33 razy

zadania z NWD

Post autor: pawels »

Drugie ok.

Co do pierwszego to niech \(\displaystyle{ d=(a,b)}\). Wówczas istnieją takie \(\displaystyle{ a_1,b_1}\), że \(\displaystyle{ a_1\perp b_1}\) i \(\displaystyle{ da_i=a}\) oraz \(\displaystyle{ db_1=b}\). Wówczas mamy \(\displaystyle{ ca=cda_1}\) i \(\displaystyle{ cdb_1=cb}\). Przypuśćmy, że \(\displaystyle{ (ac,bc)=d_1>cd}\). Wówczas \(\displaystyle{ cd\mid d_1}\), czyli istnieje \(\displaystyle{ d_2>1}\), takie \(\displaystyle{ d_1=cd\cdot d_2}\). Skoro \(\displaystyle{ d_1}\) jest dzielnikiem \(\displaystyle{ cda_1}\) i \(\displaystyle{ cdb_1}\), to \(\displaystyle{ d_2}\) jest dzielnikiem \(\displaystyle{ a_1}\) i \(\displaystyle{ b_1}\)- otrzymana sprzecznosć kończy dowód.

Skorzystałem z dwóch prostych faktów:

1. Jeżeli \(\displaystyle{ a,b,x\in\mathbb{Z}}\) i \(\displaystyle{ x\mid a}\) oraz \(\displaystyle{ x\mid b}\), to \(\displaystyle{ x\mid (a,b)}\).
2. Jeżeli \(\displaystyle{ x,y,z\in\mathbb{Z}}\) i \(\displaystyle{ xz\mid yz}\), to \(\displaystyle{ x\mid y}\).

Jeżeli uważasz, że któryś wymaga dowodu to mogę dopisać (są bardzo proste).
Awatar użytkownika
emelcia
Użytkownik
Użytkownik
Posty: 136
Rejestracja: 15 lis 2009, o 11:15
Płeć: Kobieta
Lokalizacja: Gdańsk
Podziękował: 3 razy
Pomógł: 14 razy

zadania z NWD

Post autor: emelcia »

pastorczyk pisze: 2. Algorytm Euklidesa znam, ale nie widzę jak miałbym go tutaj zastosować. \(\displaystyle{ NWD(5a + 4b, 4a + 3b) = NWD(4a + 3b, a + b) = NWD(a + b, a) = NWD(a,b) = 1}\). Czy gdzieś pobłądziłem?
Czy mógłby to ktoś wytłumaczyć?
Algorytm znam, ale nie wiem skąd wzięły Wam się te równości... Hmm?
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

zadania z NWD

Post autor: Zordon »

\(\displaystyle{ NWD(x,y)=NWD(x,x-y)}\)
jesli tylko \(\displaystyle{ x\neq 0}\)
ODPOWIEDZ