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}\).
zadania z NWD
-
- Użytkownik
- Posty: 5
- Rejestracja: 17 maja 2010, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
-
- 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
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?
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?
-
- 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
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?
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?
-
- 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
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).
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).
- emelcia
- 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
Czy mógłby to ktoś wytłumaczyć?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?
Algorytm znam, ale nie wiem skąd wzięły Wam się te równości... Hmm?