Společní dělitelé

V tomto případě je několik společných dělitelů. Třeba 2,5,7,10 o co jde přesněji?

nevím jak to myslíš ale pokud čísllo např 210 jde dělit : 2, 5, 10

140 jde taky dělit: 2,5,10

obecně lze říct že číslo končíci 0 např. těch 210: jde dělit vždycky 10 a 5

Ono není nějak zvláštní výhoda v hledání společného dělitele, aniž bychom trvali na tom, že musí být největší. Nicméně může to mít smysl. ČÍsla, která "NEMAJÍ SPOLEČNÉHO DĚLITELE" (ROZUMNĚJ JINÉHOO NEŽ SAMOZŘEJMOU JEDNIČKU), SE NAZÝVAJÍ "NESOUDĚLNÁ" A MAJÍ NĚKTERÉ DŮLEŽITÉ VLASTNOSTI, SE KTERÝMI (omlouvám se za capslock, ale nechce se mi to přepisovat) se můžeme setkat v teorii čísel, při práci s kongruencemi, aplikace mají i v kryptologii.

Jinak, k hledání největšího společného dělitele se používají hlavně dvě metody. Jedna z nich je rozklad na prvočísla, při níž obě zkoumaná čísla rozložíme na soubor prvočísel a největší společný dělitel pak je součin všech prvočísel, společných oběma rozkladům. I tuto metodu lze použít ke zjištění, zda nejsou dvě čísla nesoudělná, stačí, když mají oba rozklady společné aspoň jedno prvočíslo. Ovšem k potvrzení, že jsou nesoudělná, musíme tuto metodu dotáhnout do konce, a zjistit, že neexistuje žádné prvočíslo, společné oběma rozkladům (jinými slovy, největší společný dělitel je 1). Z teoretického hlediska lze tuto metodu použít vždy, ovšem hledání rozkladu hodně velkých čísel (a to je právě případ kryptologie) může dělat velké, ale opravdu velké problémy. (Jedna z šifrovacích metod je třeba založena na tom, že najdeme dvě veliká prvočísla a k zašífrování použijeme jejich součin, tzv. veřejný klíč. (Ono je to ještě trochu složitější, ale pro představu to snad stačí.) Takže každý, kdo zná ten součin, může zprávu zašifrovat, ale rozluštit ji může jen ten, kdo zná obě prvočísla. A ten součin je mnohem delší, než obě prvočísla. A jestliže nalézt, dejme tomu, dvě šesticiferná prvočísla (a pak je znásobit) může být sice obtížné, ale realizovatelné, tak pokus o rozklad dvanácticiferného součinu není lineárně (tedy například dvakrát) obtížnější, ale exponenciálně , což ztěžuje prolomení té šifry a při dosti velkých klíčových prvočíslech může být prakticky nemožné.

A k otázce: mám-li dvě veliká čísla, mohu hledat prvočíselný rozklad a i když ho nezvládnu komplet, stačí najít jedno prvočíslo oběma rozkladům společné a je to. Ovšem, když je ne a ne najít...

Druhá metoda se opírá o fakt, že když větší číslo vydělím celočíselně ("se zbytkem") tím menším, tak společní dělitelé obou čísel jsou zároveň společní dělitelé menšího z obou (dělitele) a toho zbytku. Tímto postupem zredukujeme úlohu na analogickou, ale s menšími čísly, a tedy ji zjednodušíme. A děláme-li to dostatečně dlouho, nakonec se dobereme výsledku (tzv. Euklidův algoritmus). A samozřejmě, heldáme-li netriviálního, ale ne nutně největšího společného dělitele, stačí se zastavit v okamžiku, kdy zkoumaná číslea jsou tak malá, že ho tam uvitíme. Možná by tohle mohla být odpověď na váš dotaz?