Kezdőlap


Feladat:	Pontversenyen kívüli P.319	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	1981/október, 73. oldal		PDF \| MathML
Témakör(ök):	Euler-féle számelméleti függvény, Osztók összege függvény, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1979/április: Pontversenyen kívüli P.319

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.

Jelöljük $φ (n)$ -nel az $n$ -hez relatív prím, $n$ -nél kisebb természetes számok számát, $σ (n)$ -nel pedig $n$ osztóinak összegét. Határozzuk meg mindazokat a $k$ kitevőket, amelyekre

\begin{matrix} φ (σ (2^{k})) = 2^{k} \end{matrix}

(1)

teljesül.

(

Könnyítésül eláruljuk, hogy

641

osztója

(2^{32} + 1)

-nek.

Megoldás. Legyen

n

prímtényezős felbontása

p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot ... \cdot p_{s}^{α_{s}}

, ahol

p_{1}, p_{2}, ..., p_{s}

különböző prímszámok,

α_{1}, ..., α_{s}

pedig pozitív egészek. Ekkor

\begin{matrix} φ (n) = p_{1}^{α_{1} - 1} (p_{1} - 1) \cdot ... \cdot p_{s}^{α_{s} - 1} (p_{s} - 1) \end{matrix}

(2)

(lásd pl. Molnár Emil: Matematikai versenyfeladatok, 490. o.). Ha most

n

páratlan és

φ (n) = 2^{k}

, akkor (2) csak úgy állhat fenn, ha egyrészt

α_{1} = α_{2} = α_{s} = ... = 1

(mivel

p_{i}

páratlan), másrészt

p_{i} - 1 = 2^{β_{i}}

valamilyen pozitív egész

β_{i}

-vel. Tudjuk, hogy

2^{β_{i}} + 1

csak úgy lehet prímszám, ha

β_{i}

maga is kettőhatvány, az ilyen alakú számokat Fermat-féle prímeknek nevezzük. Azt kaptuk tehát, hogy

\begin{matrix} n = (2^{β_{1}} + 1) (2^{β_{2}} + 1) ... (2^{β_{s}} + 1), \end{matrix}

(3)

ahol

β_{i} = 2^{γ_{i}}, 0 ≦ γ_{1} < γ_{2} < ... < γ_{s}

, valamint

2^{β_{i}} + 1

prímszám. (3)-ban a szorzást elvégezve

\begin{matrix} n = 1 + 2^{β_{1}} + 2^{β_{2}} + 2^{β_{1} + β_{2}} + ... + 2^{β_{s}} + 2^{β_{s} + β_{1}} + ... + 2^{β_{s} + ... + β_{1}} . \end{matrix}

(4)

Itt összesen

2^{s}

tag szerepel, s mivel a

β_{i}

-k különböző kettőhatványok, azért a kitevőben álló számok mind különbözők. Ez azt jelenti, hogy

n

kettes számrendszerbeli alakjában hátulról számított

0

-ik,

β_{1}

-edik,

β_{2}

-edik,

... (β_{1} + β_{2} + ... + β_{s})

-edik helyén áll

1

-es, a többi helyen nulla.
Térjünk most vissza az (1) összefüggéshez. Mivel

2^{k}

osztói

1

2

2^{2}

...

2^{k}

, ezért

\begin{matrix} n = σ (2^{k}) = 1 + 2 + 2^{2} + ... + 2^{k} \end{matrix}

páratlan szám, melynek kettes számrendszerbeli alakjában az utolsó

k + 1

helyen

1

-es áll. Ezért

φ (n) = 2^{k}

csak úgy állhat fönn, ha

n

egyúttal a (4) alatti alakban is írható. S mivel egy számot kettes számrendszerben csak egyféleképpen lehet felírni, ez azt jelenti, hogy a

β_{1} < β_{2} < β_{1} + β_{2} < ... β_{1} + β_{2} + ... + β_{s}

számoknak meg kell egyezniük az

1

2

...

k

számokkal. Ez pedig, mivel

β_{i}

kettőhatvány, csak akkor lehetséges, ha

β_{1} = 2^{0}, β_{2} = 2^{1}, ..., β_{s} = 2^{s - 1}, ...

, és

k = 2^{s} - 1

. Ugyanakkor

2^{β_{i}} + 1 = 2^{2^{i - 1}} + 1

-nek prímszámnak kell lennie minden

1 ≦ i ≦ s

-re. A feladathoz adott útmutatás szerint

2^{32} + 1 = 2^{2^{5}} + 1

nem prímszám, így csak az

s = 1, 2, 3, 4

és

5

esetek jönnek szóba, vagyis

k

szóba jövő értékei

1

3

7

15

és

31

. S mivel

2^{2^{i - 1}} + 1

prímszám, ha

i ≦ 5

, azért

k

-nak ezek az értékei valóban teljesítik (1)-et.