Matematické Fórum

Qwerrr · 08. 09. 2010 17:45 — Editoval Qwerrr (08. 09. 2010 18:58)

Jde nějak elegantně spočítat tento příklad:

Nalezněte všechna přirozená čísla m, pro které platí: $\varphi(m)=18$ ?

Jediné, co mě napadlo, byla metoda "hrubou silou": Jelikož $\varphi(m)$ pro $m>60$ nikdy není $\varphi(m)<19$ (To bych musel u toho příkladu dokázat), pak stačí ověřit pouze čísla do 60. Pokud je např. řešení 19, pak je řešení i jeho dvojnásobek, tj. 38=2.19 (dvojka se v eulerově funkci "zruší"). Prvočísla větší jak 19 není třeba ověřovat. Ale to není moc elegantní a vůbec ne v praxi na papíře použitelné, pokud by někdo zadal např. $\varphi(m)=99834$

Pavel Brožek · 08. 09. 2010 19:47

Nechť prvočíselný rozklad m vypadá následovně:

$m=\prod_{i=1}^{n}p_i^{k_i}$ .

Pak

(1) $\varphi(m)=\prod_{i=1}^{n}p_i^{k_i-1}(p_i-1)$ .

Víme, že $\varphi(m)=99834=2\cdot3\cdot7\cdot2377$ . Číslo 2377 tedy musí být obsaženo v nějakém činiteli na pravé straně rovnosti (1). Pokud by bylo obsaženo v nějakém $p_i^{k_i-1}$ , pak nutně $p_i=2377$ a rozklad $\varphi(m)$ musí obsahovat i číslo $2377-1=2376=2^3\cdot3^3\cdot11$ , což zřejmě neobsahuje. Proto 2377 musí být obsaženo v nějakém $p-1$ , tedy $p=2377a+1$ pro nějaké vhodné přirozené $a$ . $\varphi(m)$ musí být dělitelné $2377a$ , proto $a\in\{1,2,3,7,2\cdot3,2\cdot7,3\cdot7,2\cdot3\cdot7\}$ . Ověříme, že pro tato $a$ není $2377a+1$ prvočíslo a dostáváme tak, že rovnice nemá řešení.

Z tohoto postupu je na papíru nejtěžší zjistit, že 2377 je prvočíslo (při rozkládání 99834 na součin prvočísel) a ověřit, že $2\cdot3\cdot2377+1=14263$ není prvočíslo ( $14263=17\cdot839$ ).

Není to samozřejmě návod na obecný postup. Šlo to poměrně dobře vyřešit, protože 99834 mělo v prvočíselném rozkladu velké prvočíslo.

Matematické Fórum

#1 08. 09. 2010 17:45 — Editoval Qwerrr (08. 09. 2010 18:58)

Příklad na eulerovu funkci

#2 08. 09. 2010 19:47

Re: Příklad na eulerovu funkci

Zápatí