Kezdőlap


Feladat:	N.143	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Braun Gábor
Füzet:	1998/január, 37 - 38. oldal		PDF \| MathML
Témakör(ök):	Euler-féle számelméleti függvény, Egységgyökök, Egész együtthatós polinomok, Műveletek polinomokkal, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1997/május: N.143

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.

Megmutatjuk, hogy végtelen sok ilyen $n$ létezik.
Legyen tetszőleges pozitív egész $k$ -ra $f_{k}$ az a polinom, amelynek gyökei a primitív $k$ -adik komplex egységgyökök, főegyütthatója pedig 1. (Ezt a polinomot hívják a $k$ -adik körosztási polinomnak. Az $f_{1} (x)$ polinomot $x - 1$ -nek definiáljuk.)
Az $f_{k}$ polinomoknak két fontos tulajdonságára lesz szükségünk:
(1) $f_{k}$ egész együtthatós;
(2) Tetszőleges $k$ pozitív egészre $\prod_{d ∣ k}^{} f_{d} (x) = x^{k} - 1$ .
Először a (2) tulajdonságot bizonyítjuk. Mindkét oldalon a polinomok főegyütthatója 1, ezért elég azt igazolnunk, hogy ugyanazok a gyökeik is. A jobb oldalon álló $x^{k} - 1$ polinom gyökei a $k$ -adik komplex egységgyökök (mindegyik egyszeres gyök). Tekintsünk egy $ε$ $n$ -edik egységgyököt. Azt kell belátnunk, hogy $ε$ a bal oldalon szereplő tényezők közül pontosan egynek gyöke. Az $f_{k}$ polinomok definíciója szerint egyetlenegy olyan $d$ pozitív egész létezik, amelyre $ε$ gyöke $f_{d}$ -nek: a legkisebb olyan szám, amelyre $ε^{d} = 1$ . Könnyű meggondolni, hogy azok az $m$ számok, amelyekre $ε^{m} = 1$ , $d$ többszörösei; speciálisan $n$ többszöröse $d$ -nek. Az $f_{d}$ polinom tehát szerepel (2) bal oldalán.
Az (1) tulajdonságot teljes indukcióval igazolhatjuk, a (2) tulajdonság felhasználásával. $k = 1$ -re az állítás igaz. Ha $f_{1}$ , $...$ , $f_{k - 1}$ mind egész együtthatós, akkor (2) alapján

\begin{matrix} f_{k} (x) = \frac{x^{k} - 1}{\prod_{d ∣ k, d < k}^{} f_{d} (x)} . \end{matrix}

A számláló és a nevező is egész együtthatós, továbbá a nevező főegyütthatója 1. Ebből a jól ismert polinomosztási algoritmus alapján következik, hogy a két polinom hányadosa,

f_{k} (x)

is egész együtthatós.
Keressük ezután az

n

számot

q_{1} q_{2} ... q_{s}

alakban, ahol

q_{1}

q_{2}

...

q_{s}

az első

s

darab 1997-nél nagyobb prímszám. A (2) tulajdonság szerint

\begin{matrix} 2^{n} - 1 = \prod_{d ∣ n}^{} f_{d} (2), \end{matrix}

és az (1) tulajdonság miatt a jobb oldalon mindegyik tényező egész. Ha mindegyik abszolút értéke kisebb lenne

2^{\frac{n}{1997}}

-nél, kész volnánk.
Ha

d

egy valódi osztója

n

-nek, azaz

d < n

, akkor

2^{d} - 1 = \prod_{δ ∣ d}^{} f_{δ} (2)

, emiatt

f_{d} (2)

osztója

2^{d} - 1

-nek, ezért

| f_{d} (2) | \leq 2^{d} - 1 < 2^{\frac{n}{1997}}

.
Azt kell tehát csak megvizsgálnunk, hogy

| f_{n} (2) | < 2^{\frac{n}{1997}}

teljesül-e. Legyenek az

n

-edik primitív egységgyökök

ε_{1}

ε_{2}

...

ε_{φ (n)}

. Ekkor

\begin{matrix} | f_{n} (2) | = \prod_{j = 1}^{φ (n)} | 2 - ε_{j} | < 3^{φ (n)} . \end{matrix}

Ha sikerülne

n

-et úgy választani, hogy

3^{φ (n)} < 2^{\frac{n}{1997}}

, azaz

\frac{φ (n)}{n} < \frac{1}{1997 \cdot log_{2} 3}

teljesüljön, kész volnánk.
A

φ

függvény egy jól ismert felírása szerint (lásd pl. Szalay Mihály: Számelmélet, 117. old.)

\begin{matrix} \frac{φ (n)}{n} = \prod_{j = 1}^{s} (1 - \frac{1}{q_{j}}) . \end{matrix}

Az is ismert (ugyanott, 153. old.), hogy tetszőleges

x \geq 2

valós számra

\begin{matrix} \prod_{p \leq x}^{} (1 - \frac{1}{p}) \leq \frac{1}{\sum_{k \leq x}^{} \frac{1}{k}} < \frac{1}{log x} . \end{matrix}

(A szorzat az

x

-nél nem nagyobb prímszámokon fut végig.) Ezt

x = q_{s}

-re alkalmazva

\begin{matrix} \prod_{p \leq q_{s}}^{} (1 - \frac{1}{p}) = \prod_{p \leq 1997}^{} (1 - \frac{1}{p}) \cdot \prod_{j = 1}^{s} (1 - \frac{1}{q_{j}}) < \frac{1}{log q_{s}}, \end{matrix}

vagyis

\begin{matrix} \frac{φ (n)}{n} = \prod_{j = 1}^{s} (1 - \frac{1}{q_{j}}) < \frac{1}{\prod_{p \leq 1997}^{} (1 - \frac{1}{p}) \cdot log q_{s}} . \end{matrix}

Ebből látszik, hogy

s

-et elég nagynak választva

\frac{φ (n)}{n}

tetszőlegesen kicsivé tehető.