Znajdź najwiekszy współny dzielnik liczb a i b.

[m]

\(\displaystyle{ a=2 \cdot 10^{100} \\
b=5 \cdot 10^{100}+7}\)

Jak znalezć \(\displaystyle{ NWD(a,b)}\) . Normalny algorytm euklidesa nic tu nie da, a ten z liczbami mod jest ciężko zastosować (chyba).

[Yavien]

NWD(a,b) dzieli zarówno liczbę a, jak i liczbę b. Dzielnikami a są wyłącznie odpowiednie potęgi (i iloczyny ich) 2 i 5
Żadna z liczb 2, 5, nie dzieli liczby b.
Zatem NWD(a,b)=1

[m]

Błąd. Miało być
\(\displaystyle{ a=2 \cdot 10^{100} + 1\\
b=5 \cdot 10^{100} + 7}\)
I jak teraz będzie bo nie wiem.

[półpasiec]

niech \(\displaystyle{ d}\) bedzie tym dzielnikiem, skoro \(\displaystyle{ d|a}\) i \(\displaystyle{ d|b}\), to \(\displaystyle{ d|5a}\) i \(\displaystyle{ d|2b}\) i dalej \(\displaystyle{ d|2b-5a=9}\). A wiec \(\displaystyle{ d=1}\) albo \(\displaystyle{ 3}\) albo \(\displaystyle{ 9}\). Ale \(\displaystyle{ 9}\) nie dzieli \(\displaystyle{ a}\), co latwo wynika z reszt z dzielenia, natomiast \(\displaystyle{ 3}\) dzieli \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\), wiec \(\displaystyle{ d=3}\)

[withdrawn]

czym jest \(\displaystyle{ a}\) i \(\displaystyle{ b}\) ? calymi tymi liczbami i czemu akurat \(\displaystyle{ 2b-5a = 14}\) ?

-- 26 sie 2011, o 23:10 --

prosilabym o wyjasnienie powyzszych pytan.
ja probowalam to jakos z euklidesa ale dochodze do pewnego momentu i nie wiem co dalej, moze ktos wie i pomoze, bowiem:)

\(\displaystyle{ \left( 5 \cdot 10^{100} + 7\right) = 2 \cdot \left(2 \cdot 10^{100} +1\right) + \left(10^{100} + 5\right) \\ \left( 2 \cdot 10^{100} +1\right) = 1 \cdot \left(10^{100} + 5\right) + \left(10^{100} - 4\right) \\ \left(10^{100} + 5\right) = \left(10^{100} -4\right) + 9 \\ \left(10^{100} - 4\right) =\,\ldots}\)?

[macciej91]

\(\displaystyle{ a}\) i \(\displaystyle{ b}\) to są liczby z treści zadania. W rozwiązaniu półpaścia, chodzi o to, że skoro duże liczby dziela się przez wybrany dzielnik \(\displaystyle{ d}\) to ich kombinacja liniowa również się przez niego dzieli. Dlatego szukasz jak najprostszej kombinacji liniowej, żeby sprawdzić jak najmniejszą liczbę przypadków ręcznie.