Z následujících tvrzení vyberte ty, jejichž důkaz by byl nekompletní, kdybychom vynechali sekci 1.2 (o základní větě aritmetiky). Jinými slovy, vytrasujte, zda se někde v důkazu, včetně všech použitých tvrzení, někde vyskytuje lemma 1.5 nebo existence či jednoznačnost prvočíselných rozkladů.

Všechny odpovědi jsou správně. 
Jednou kritickou ingrediencí je krácení v kongruenci. 
V čínské větě o zbytcích navíc používáme úvahu, že když každé m_i dělí číslo X, tak součin m_i také dělí číslo X, a k této úvaze jsou také potřeba jednoznačné rozklady. Protipříklad v Z[sqrt5]: m1=1+sqrt5, m2=-1+sqrt5, m3=2, X=4, všechna mi jsou po dvou nesoudělná.

Na druhou stranu, striktně vzato, ty úvahy lze provést i pomocí výsledků sekce 1.1 (Bézout). Uznám oba typy odpovědí.


***

Buď a číslo soudělné s číslem 30. Pak a^8 mod 30	

není nikdy rovno 1	

Je-li NSD(a,30)=k, pak k musí dělit i výsledek. Takže pokud k>1, výsledek nebude 1.

***

Kolik řešení má soustava kongruencí x = 3 (mod 10) , x = 8 (mod 15) v intervalu {0,...,1499} ? Napište přirozené číslo bez dalšího komentáře.

50

Pozor, čínská věta se přímo neaplikuje z důvodu soudělnosti. Počet řešení může klidně vyjít 0, nebo taky hodně - musí se ta soustava kongruencí vyřešit. 
V tomto konkrétním případě vyjde jedno řešení v intervalu 0..29, plus jakýkoliv násobek 30, celkem tedy 1500/30=50 řešení v daném intervalu.

***

Bob zapomněl, že RSA není problém prolomit, když je N malé, a zveřejnil klíč N=1022117 a e=5. Odchytili jste zašifrovanou zprávu 666666. Napište původní zprávu. 

502183

S touto úlohou problémy nebyly.