Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 1
Lekce 5: Modulární aritmetika- Co je to modulární aritmetika?
- Operátor modulo
- Výzva Modulo
- Kongruence modulo
- Kongruence modulo
- Relace ekvivalence
- Věta o dělení se zbytkem
- Modulární sčítání a odčítání
- Modulární sčítání
- Výzva modulo (sčítání a odčítání)
- Modulární násobení
- Modulární násobení
- Modulární mocnění
- Rychlé modulární umocňování
- Rychlé modulární umocňování
- Modulární inverze
- Euklidův algoritmus
Kongruence modulo
Kongruence Modulo
Někdy se můžeš setkat s výrazem:
Ten nám říká, že je kongruentní k modulo .
Prodiskutujeme význam kongruence modulo provedením myšlenkového experimentu s regulárním modulo operátorem.
Představme si, že počítáme mod 5 pro všechna celá čísla:
Označili jsme 5 řezů čísly 0, 1, 2, 3, 4. Poté jsme každé celé číslo vložili do řezu, který odpovídá hodnotě „celé číslo mod 5“.
Tyto řezy si představme jako chlívečky, které obsahují množiny čísel. Například číslo 26 jde do řezu označené 1, protože .
Výše je obrázek, který ukazuje některá čísla, jak bychom je nalezli v daných řezech.
Tyto řezy si představme jako chlívečky, které obsahují množiny čísel. Například číslo 26 jde do řezu označené 1, protože
Výše je obrázek, který ukazuje některá čísla, jak bychom je nalezli v daných řezech.
Bylo by užitečné mít způsob, kterým lze vyjádřit čísla obsažené v jednom konkrétním řezu. (Všimni si, že 26 je ve stejném řezu jako1, 6, 11, 16, 21 na obrázku výše).
Běžný způsob vyjádření, že dvě hodnoty patří do stejného řezu, je říct, že patří do stejné třídy ekvivalence.
Způsob, jakým se to pro „modulo C“ matematicky vyjadřuje, je:
Způsob, jakým se to pro „modulo C“ matematicky vyjadřuje, je:
Výraz výše čteme jako je kongruentní s modulo .
Prohlédněme si výraz blíže:
je symbol pro kongruenci, což znamená, že hodnoty a jsou prvky stejné třídy ekvivalence. označuje, jakou operací působíme na a .- Máme-li obě vlastnosti, pak nazýváme symbol “
” kongruence modulo .
Například
Všimni si, že je to rozdílné od : .
Vhled do kongruence modulo
Další vhled do významu kongruence modulo můžeme získat provedením stejného myšlenkového experimentu s přirozeným číslem .
Nejdříve označíme řezů takto: .
Poté každé celé číslo přiřadíme do odpovídajícího řezu, který odpovídá „celé číslo “.
Níže je obrázek, který ukazuje některé příklady hodnot, které nalezneme v každém řezu.
Nejdříve označíme
Poté každé celé číslo přiřadíme do odpovídajícího řezu, který odpovídá „celé číslo
Níže je obrázek, který ukazuje některé příklady hodnot, které nalezneme v každém řezu.
Pokud bychom se podívali do řezu označeného 0, našli bychom:
Pokud bychom se podívali do řezu označeného 1, našli bychom:
Pokud bychom se podívali do řezu označeného 2, našli bychom:
Pokud bychom se podívali do řezu označeného , našli bychom:
Z tohoto experimentu můžeme vyvodit klíčové pozorování:
Hodnoty v každém řezu jsou rovny číslu, kterým je řez označen, plus nebo minus nějaký násobek čísla .
To znamená, že rozdíl mezi libovolnými dvěma hodnotami v daném řezu je nějaký násobek čísla .
Toto pozorování nám pomůže pochopit ekvivalentní tvrzení a třídy ekvivalence.
Hodnoty v každém řezu jsou rovny číslu, kterým je řez označen, plus nebo minus nějaký násobek čísla
To znamená, že rozdíl mezi libovolnými dvěma hodnotami v daném řezu je nějaký násobek čísla
Toto pozorování nám pomůže pochopit ekvivalentní tvrzení a třídy ekvivalence.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.