Matematické Fórum

smajdalf · 04. 06. 2013 11:07

Zdravím všechny,
tenhle příklad jsem měl včera u písemné SZZ z matematiky.

Zadání:
Najděte největší společný dělitel $D(3^{84}-1 \; ; \; 3^{35}-1)$ .

Já jsem se to pokoušel řešit pomocí kongruence asi nějak takto:
$84 = 7 \cdot 3 \cdot 2^2$
$35 = 7 \cdot 5$
$D(84;35)=7 \;\; \Rightarrow \;\; [84 \equiv 12 \; (\text{mod} \; 7) ] \wedge [35 \equiv 5 \; (\text{mod} \; 7)]$
a tak dál řešíme
$D(3^{12}-1 \; ; \; 3^{5}-1)$
a tak dále ...
Nakonec mi vyšlo $3^{5}-1$ .

Ale tenhle postup asi není správný, že?
Nemohl by mi někdo nastínit, jak to vyřešit pomocí Eukleidova algoritmu?

Díky.

OiBobik · 04. 06. 2013 11:50

↑ smajdalf:

Čau,

tohle se řeší standardně a pohodlně ne přímo eukl. algoritmem (kde požaduješ, aby v každém kroku zbytek po dělení byl ostře menší než dělitel), ale jeho mírně upravenou verzí. Myšlenka je ale stejná, a sice: V každém kroku vezmeš předchozí dělitel a zbytek a jedno dělíš druhým.

Takže zde

$3^{84}-1=3^{49}(3^{35}-1)+(3^{49}-1)$
Teď mám zbytek větší než dělitel. Ale tak nebudu si toho všímat a zkrátka ten zbytek opět vydělím stejným dělitelem:
$3^{49}-1=3^{14}(3^{35}-1)+(3^{14}-1)$
...
a takto pokračuju dál.

Vyšlo mi teda $3^7-1$ .

smajdalf · 04. 06. 2013 20:40

↑ OiBobik:

Aha, takže když máš zbytek větší než dělitel, tak to jakoby dělíš obráceně (nedělíš zbytkem, ale zbytek tím původním dělitelem).

Jinak je to naprosto triviální, až m překvapuje, že jsem na to nepřišel sám ;-/

Ale stejně díky za vysvětlení.

Ještě jsem zkoušel tohle:
$84 = 7 \cdot 3 \cdot 2^2$
$35 = 7 \cdot 5$
$D(84;35)=7 \; \Rightarrow \; D(3^{84}-1 \; ; \; 3^{35}-1)= 3^7-1$

Ještě jsem v sešitě našel podobný příklad:
$D(2^{63}-1 \; ; \; 2^{91}-1)=\;?$

Zase by se to dalo vyřešit podobně:
$D(63;91)=7 \; \Rightarrow \; D(2^{63}-1 \; ; \; 2^{91}-1)= 2^7-1$ ,

ale nevím, zdá se mi to až moc jednoduchý ;-D

Co ty na to?

OiBobik

↑ smajdalf:

Ale jako proč ne: všimni si, že když děláš ten pozměněný "dělící" eukl algoritmus na těch samotných číslech, tak vlastně děláš "odčítací" eukleidův algoritmus na těch exponentech; takže když najdeš nsd exponentů, 2^{nsd}-1 je nsd těch původních čísel.

Ono to vlastně dost souvisí s polynomy typu $x^k-1$ ... tam taky platí, že $NSD(x^k-1,x^l-1)=x^{NSD(k,l)}-1$ .

Je ale asi potřeba umět to takto nějak zdůvodnit.

smajdalf · 04. 06. 2013 21:05

↑ OiBobik:

Díky moc,
za pomoc.

;-)

Matematické Fórum

#1 04. 06. 2013 11:07

Algebra - NSD

#2 04. 06. 2013 11:50

Re: Algebra - NSD

#3 04. 06. 2013 20:40

Re: Algebra - NSD

#4 04. 06. 2013 21:00 — Editoval OiBobik (04. 06. 2013 21:01)

Re: Algebra - NSD

#5 04. 06. 2013 21:05

Re: Algebra - NSD

Zápatí