Společní dělitelé

Od: Datum: 12.03.14 16:59 odpovědí: 11 změna: 13.03.14 10:25

Prosím Vás, jak zjístím společné dělite, například čísel 210 a 140. Nemyslím největšího společného dělitele ale nevím jestli se to nějak dělá přes to. Díky za odpovědi předem


Seznam odpovědí:
 
moment čekejte prosím, probíhá přenos dat...
Zobrazení struktury odpovědí v otázce
Skrytí struktury odpovědí v otázce
Zobrazení struktury odpovědí v otázce

 

Odpovědi na otázku:
Datum: 12.03.14 17:03
avatar

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

Ohodnoceno: 2x
 
Datum: 12.03.14 17:05

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

Ohodnoceno: 2x
 
Datum: 12.03.14 18:39
avatar

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?

Ohodnoceno: 1x
 
Od: hm®
Datum: 12.03.14 19:35
avatar

Mohu se na něco zeptat? Pro nalezení největšího spol. dělitele jsem se kdysi někde dozvěděl i postup: od většího číslo odečteme menší; pak vezmem výsledek a to menší číslo a zopakujem postup. Tak pokračujem do té doby, dokud nedostanem čísla stejná a to je pak i hledaný nejv. spol. dělitel původních čísel. Jedná se o variantu toho Eukleidova algoritmu?

doplněno 13.03.14 09:17:

pro: @kartaginec

Děkuji. Dneska mi to připadá celkem jasné, ale včera nějak ne. :)

doplněno 13.03.14 09:52:

Obávám se, že menšítka a většítka se tu občas perou s tagy pro html. Výsledky těchto bojů nejsou uspokojivé.

Ohodnoceno: 1x
 
Datum: 12.03.14 19:59
avatar

V podstatě ano. Dělení se zbytkem je vlastně opakované odčítání menšího čísla od většího, dokud to jde, takže popsaný postup je fakticky Euklidův algoritmus bez dělení.

Jinak skončit jde, jak říkáte, když vyjdou stejná čísla a to bude výsledek, anebo (přivariantě s dělením je to možná logičtější) když vujde nula (dělíme beze zbytku) a výsledek je to číslo před tím.

doplněno 13.03.14 09:29:

Jinak ke srovnátí těch dvou přístupů: algoritmus s celočíselnám dělením pracuje rychleji a je vhodný pro počítače, které celočíselné dělení umějí(příkazi jsou: celošíselné a/b značíme q = a DIV b, zbytek po celočíselném dělení r = a mod b, tedy

a = q*b + r

Na druhou stranu to odčítání je jednodušší na pochopení a pro ruční výpočet pohodlnější.

Euklidův algoritmus s celočíselným dělením (pro hledání největšího společného dělitele NSD dvou kladných čísel) pak vypadá asi takto:

1, označ větší ze zkoumaných čísel a, menší označ b,

2. spočítej zbytek a MOD b = r; je zřejmě r

Ohodnoceno: 0x
 
Od: luke237
Datum: 13.03.14 09:50
Problem je znak "mensi nez" nasledovane "b" je HTML znacka pro "tucny text", proto take mate ten Vas text od toho tretiho bodu vytisteny tucne.
Ohodnoceno: 0x
 
Od: luke237
Datum: 13.03.14 09:51
Jeste ukoncim ten tucny text, at se to tady porad nemota.
Ohodnoceno: 0x
 
Od: luke237
Datum: 13.03.14 09:52
Aha, tak ono to takhle asi nefunguje *bzum*
Ohodnoceno: 0x
 
Od: luke237
Datum: 13.03.14 09:53
>>>> Jeste jeden pokus ...
Ohodnoceno: 0x
 
Od: luke237
Datum: 13.03.14 09:54
Tak napopate se mi to konecne podarilo odblokovat *zed*
Ohodnoceno: 0x
 
Datum: 13.03.14 10:25
avatar

Tak konečne to chápu, akorát moc nevím, co s tím. Konec konců nejen b je součástí html tagu. Leda bych zkusil nerovnost obrátit a psát b větší než r. s většítkem tedy b> r. Tak schválně.

Ohodnoceno: 0x
 

 

 

 

 

Přihlásit se k odběru odpovědí z této otázky:

Neneseme odpovědnost za správnost informací a za škodu vzniklou jejich využitím. Jednotlivé odpovědi vyjadřují názory jejich autorů a nemusí se shodovat s názorem provozovatele poradny Poradte.cz

 
Copyright © 2004-2016 Poradna Poradte.cz. Všechna práva na poradně Poradte.cz vyhrazena.