Teorie čísel

BI-SPOL.21-8

08.1 Teorie čísel:

Dělitelnost

#definice Dělitelnost

Nechť . Řekneme, že  dělí , značíme , jestliže existuje  takové, že V takovém případě říkáme, že  je (celočíselný) dělitel  a  je (celočíselný) násobek  případně také, že  je dělitelné .
Pokud  nedělí , píšeme . Samotné | nazýváme relací dělitelnosti.

#definice Celočíselný podíl a zbytek po dělení

Číslo  nazveme celočíselný podíl (po dělení  číslem ). Číslo  nazveme zbytkem po (celočíselném) dělení  číslem  a značíme jej

#definice Společný dělitel

Buďte . Číslo je společný dělitel čísel jestliže

#definice Největší společný dělitel

Buďte . Číslo je největší společný dělitel čísel , značíme , pokud je jejich společný dělitel a současně je celočíselným násobkem každého jejich společného dělitele, tedy pokud

#definice Společný násobek

Buďte . Číslo je společný násobek čísel jestliže

#definice Nejmenší společný násobek

Buďte . Číslo je nejmenší společný násobek čísel , značíme , pokud je jejich násobek dělitel a současně dělí každý další společný násobek, tedy pokud

#definice Nesoudělnost

Buďte . Čísla nazýváme nesoudělná jestliže . V opačném případě jsou soudělná.

REA

Pro vstup dvou čísel je výstupem a Bezoutovy koeficienty takové že
Pasted image 20260607164425.png

  • Před začátkem je nutné napsat čísla do modrého rámečku, větší je vlevo a na prvním řádku
  1. První krok říká kolikrát se vejde 52 do 126
  2. Zbytek po dělení
  3. Výsledek
  4. Výsledek
  5. Kolikrát se vejde 22 do 52
  6. Opakují se kroky 2-5 dokud není zbytek po dělení není nula
  7. V řádku nad 0 je a koeficienty

LDR

#definice Lineární diofantická rovnice

Lineární diofantická rovnice (pro dvě neznámé) je libovolná rovnice typu
kde  pro dvě neznámé . Nehrozí-li zmatení, můžeme vynechat přívlastek lineární, případně lze zkrátit na LDR.

  • LDR má alespoň jedno řešení právě když

Množina řešení LDR


  • Nechť  a dvojice  je řešením rovnice . Potom množina všech celočíselných řešení této rovnice je což lze ekvivalentně zapsat také jako
    #definice Homogení a partikulární řešení LDR

    Uvažujme lineární diofantickou rovnici , která má nějaké řešení . Obdobně jako v lineární algebře definujeme

    • partikulární řešení: to je ono , nazvat tak můžeme jakékoli řešení,
    • přidružená homogenní rovnice: to je LDR .

Prvočísla

#definice Prvočísla a čísla složená

Přirozená čísla  rozdělujeme podle počtu dělitelů do tří tříd:

  • Číslo které má jediného dělitele, sebe sama.
  • Prvočísla, která mají právě dva dělitele, sebe sama a číslo
  • Čísla složená to jsou všechna ostatní čísla

Modulární aritmetika

#definice Kongruence modulo

Nechť . Pokud , říkáme, že  je kongruentní s  modulo  a píšeme V opačném případě  není kongruentní s  modulo  a píšeme .
Samotné  nazýváme relací kongruence modulo . Číslo  nazýváme modulo nebo modul. Obvykle uvažujeme pouze .

#definice Množina zbytků a operace na ní

Nechť . Jako  označíme množinu všech zbytků modulo , Na  zavádíme operace sčítání a násobení modulo : kde operace  jsou standardní operace sčítání a násobení celých čísel.

#definice Aditivní inverze v

Buďte Číslo nazveme aditivní inverzí (, opačný prvek), právě když

#definice Multiplikativní inverze v

Buďte Číslo nazveme multiplikativní inverzí (), právě když

  • multiplikativní inverze existuje, právě když a je jediná.
    #veta Krácení v modulu

    Nechť , označme . Pak platí ekvivalence: Speciálně, pro  platí  právě tehdy, když v kongruenci je krácení i rozšiřování číslem  ekvivalentní úprava (beze změny modula).

Malá Fermatova věta

#veta Malá Fermatova věta

Buď prvočíslo a takové přirozené číslo, které není násobkem (tedy ).
Potom platí:

#tvrzeni Výpočet multiplikativní inverze pomocí MFV

Pokud je prvočíslo a , pak je multiplikativní inverzí čísla .

Tedy:

Eulerova věta a funkce

#definice Eulerova funkce

Eulerova funkce udává počet přirozených čísel menších nebo rovných , která jsou nesoudělná s , tj.

*(velké okolo množiny značí mohutnost, tedy počet prvků)

Pasted image 20260607174454.png

Eulerova věta

Nechť a je číslo nesoudělné s (tedy ). Potom platí:
kde je Eulerova funkce.

#tvrzeni Výpočet multiplikativní inverze pomocí EV

Pokud je a číslo je nesoudělné s , pak je multiplikativní inverzí čísla .

Tedy:

Lineární kongruence

#definice Úloha lineární kongruence

Řešením lineární kongruence rozumíme nalezení všech celých čísel splňujících
kde a

#veta Řešení lineární kongruence

Buďte a .
Kongruence má řešení právě tehdy, když .

ji řeší právě tehdy, když existuje takové, že řeší lineární diofantickou rovnici .
Všechna řešení lineární kongruence v jsou pak

Čínská věta o zbytcích

#veta Čínská věta o zbytcích

Uvažujme soustavu lineárních kongruencí

kde jsou navzájem nesoudělná, tedy pro každá .

Řešení této soustavy vždy existuje a všechna řešení jsou kongruentní modulo (tedy v je řešení určení jednoznačně), kde

Dále definujeme

(tedy jako součin všech modulů kromě -tého)

Pasted image 20260607175636.png

#veta Zobecněná Čínská věta o zbytcích

Uvažujme soustavu lineárních kongruencí

kde . Tato soustava má řešení právě tehdy, když dělí pro všechna .

Pokud řešení existuje, je určeno jednoznačně v modulu , resp. v
*(viz lcm)

Pasted image 20260607175645.png

Vytvořeno: 27. 5. 2026, 11:57
Poslední aktualizace: 9. 6. 2026, 12:18