Kezdőlap


Feladat:	N.36	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Csörnyei Marianna , Futó Gábor , Gyarmati Katalin , Szeidl Ádám
Füzet:	1995/február, 102 - 103. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Euler-féle számelméleti függvény, Magasabb fokú kongruenciák, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1994/május: N.36

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A feladatbeli törtek száma legyen $q n + r$ , ahol $q$ és $r$ egészek, $0 \leq r < n$ . Ekkor az Euler-féle $φ$ függvénnyel^{$^{*}$} $φ (n)$ az $n$ -nél nem nagyobb, $n$ -hez relatív prím pozitív egészek számát jelöli (az ún. Euler-féle $φ$ függvény). $φ (a^{n} - 1) = q n + r$ , vagyis

\begin{matrix} a^{r} = a^{r} \cdot 1^{q} \equiv a^{r} {(a^{n})}^{q} = a^{q n + r} = q^{φ (a^{n} - 1)} \equiv 1 (mod a^{n} - 1), \end{matrix}

azaz

a^{n} - 1 ∣ a^{r} - 1

. Ez csak

r = 0

esetén lehetséges, vagyis a törtek száma ‐

q n

‐ osztható

n

-nel.

Futó Gábor (Fazekas M. Főv. Gyak. Gimn., IV. o.t.) dolgozata alapján

^{$^{*}$}*