Matematyka.pl

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}\).

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. 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?

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).

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?

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