Największy wspólny dzielnik dwóch liczb zespolonych

[klementa]

\(\displaystyle{ NWD(4-2i,9+3i)}\)

[kasiam1312]

to może się da obliczyc algorytmem Euklidesa .. nie wiem, sprawdź ;]

[max]

Hmm, jeśli ten największy wspólny dzielnik ma być największym wspólnym dzielnikiem w \(\displaystyle{ \mathbb{Z}}\) (jak się domyślam, bo w dowolnym ciele, w szczególności w \(\displaystyle{ \mathbb{C}}\) wszystkie elementy są ze sobą stowarzyszone, więc nwd nie ma tam zbyt ciekawego sensu), to faktycznie można skorzystać z tego, że jest to pierścień euklidesowy i spróbować czegoś na wzór algorytmu Euklidesa.
Ewentualnie skorzystać z tego, że \(\displaystyle{ \mathbb{Z}}\) jest dziedziną z jednoznacznością rozkładu (bo np jest dziedziną euklidesową), i zauważyć, że:
\(\displaystyle{ 4 - 2i = (1 - i)(1 + i)(2 - i)\\
9 + 3i = 3(1 + i)(2 - i)}\)
oraz \(\displaystyle{ 1 - i,\ 1 + i, \ 2 - i}\) są nierozkładalne w \(\displaystyle{ \mathbb{Z}}\), bo inaczej kwadraty ich modułów byłyby rozkładalne w \(\displaystyle{ \mathbb{Z}}\), ale są one liczbami pierwszymi. Również \(\displaystyle{ 3}\) jest nierozkładalne w \(\displaystyle{ \mathbb{Z}}\), bo \(\displaystyle{ 3}\) jest liczbą pierwszą oraz nie rozkłada się na sumę kwadratów dwóch liczb całkowitych, bo suma kwadratów może przystawać do \(\displaystyle{ 0, 1, 2}\) modulo \(\displaystyle{ 4}\).
Dalej zauważmy, że elementy \(\displaystyle{ 1 - i, 1 + i, 2 - i, 3}\) parami nie są stowarzyszone zatem \(\displaystyle{ NWD(4 - 2i, 9 + 3i) = (1 + i)(2 - i) = 3 + i}\), z dokładnością do relacji stowarzyszenia.

[max]

Dla \(\displaystyle{ a, b, c, d\in \mathbb{Z}, \ c^{2} + d^{2} \neq 0}\) chcemy znaleźć takie \(\displaystyle{ q, r\in \mathbb{Z},}\) żeby było:
\(\displaystyle{ a + bi = q(c + di) + r,}\) gdzie \(\displaystyle{ |r|^{2} < |c + di|^{2}.}\)
Zapiszmy najpierw:
\(\displaystyle{ \frac{a + bi}{c + di} = \frac{(a + bi)(c - di)}{c^{2} + d^{2}} = \frac{ac + bd}{c^{2} + d^{2}} + \frac{bc - ad}{c^{2} + d^{2}}i = A + B i}\)
Połóżmy teraz \(\displaystyle{ q:= \lfloor A\rceil + \lfloor B\rceil i, \ r:= a + bi - q(c+di)}\) gdzie \(\displaystyle{ \lfloor x \rceil}\) dla liczby rzeczywistej \(\displaystyle{ x}\) oznacza najbliższą \(\displaystyle{ x}\) liczbę całkowitą, tzn:
\(\displaystyle{ lfloor x
ceil:= egin{cases} k, x in left[k, k+frac{1}{2}
ight) \ k + 1, x in left[k+ frac{1}{2}, k+1
ight), kinmathbb{Z} end{cases}}\)
Zauważmy, że \(\displaystyle{ q, r\in \mathbb{Z}}\) oraz:
\(\displaystyle{ a + bi = (c + di)(A + Bi) = (c+di)(q + (A - \lfloor A \rceil) + (B - \lfloor B\rceil)i) =\\
= (c + di)q + (c+di)((A - \lfloor A \rceil) + (B - \lfloor B\rceil)i)}\)
zatem \(\displaystyle{ r = (c+di)((A - \lfloor A \rceil) + (B - \lfloor B\rceil)i),}\)
oraz \(\displaystyle{ |r|^{2} = (c^{2} + d^{2})((A - \lfloor A \rceil)^{2} + (B - \lfloor B\rceil)^{2})}\)
ale dla każdego \(\displaystyle{ x\in \mathbb{R}}\) jest \(\displaystyle{ |x - \lfloor x\rceil| \leqslant \tfrac{1}{2},}\) stąd
\(\displaystyle{ |r|^{2} \leqslant (c^{2} + d^{2})(\tfrac{1}{4} + \tfrac{1}{4}) < (c^{2} + d^{2}) = |c + di|^{2}.}\)
A więc wyznaczone przez nas \(\displaystyle{ q, r}\) są szukanymi ilorazem i resztą z dzielenia \(\displaystyle{ a + bi}\) przez \(\displaystyle{ c + di.}\)

[Agatka266]

A czy w tej klamrze na dole nawias z lewej strony nie powinien być domknięty?

[max]

Nie, bo ta klamerka jest dla \(\displaystyle{ x in [k, k+1)}\) jeśli \(\displaystyle{ x in [k+1, k+2)}\) to bierzemy zamiast \(\displaystyle{ k}\) liczbę całkowitą \(\displaystyle{ k+1.}\)

[Agatka266]

W takim razie ile wynosi \(\displaystyle{ [2.5]}\)? 2 czy 3?

[max]

Pardon, dopiero teraz zauważyłem, że pomyliłem lewą z prawą stroną:) Oczywiście masz rację.

[natasza123]

hej czy mógłby mi ktoś powiedzieć czy ta metoda zapisana w poście z 14 sty 2009, o 17:54 ma jakaś nazwę?