Kezdőlap


Feladat:	1991. évi Nemzetközi Matematika Diákolimpia 12. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Szendrői Balázs
Füzet:	1991/november, 338. oldal		PDF \| MathML
Témakör(ök):	Számtani sorozat, Legnagyobb közös osztó, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1991/szeptember: 1991. évi Nemzetközi Matematika Diákolimpia 12. feladata

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.

Legyen $a_{2} - a_{1} = a_{3} - a_{2} = ... = a_{k} - a_{k - 1} = d$ . Mivel $d > 0$ , ezért $a_{1} < a_{2} < ... < a_{k}$ . Mivel minden pozitív egész $n$ -re $(n - 1, n) = 1$ , ezért $a_{k} = n - 1$ , továbbá nyilván $a_{1} = 1$ .

I. Legyen először

n

páratlan. Ekkor

(n - 2, n) = 1

. (Ugyanis

x | n

és

x | n - 2

esetén

x | 2

, de

n

páratlan, így

x = 1

, ezért

a_{k - 1} = n - 2

. Így viszont

d = 1

és ekkor minden

n

-nél kisebb pozitív egész relatív prím

n

-hez, azaz

n

-nek nincs nála kisebb valódi osztója; így

n

prím, ahogy a feladat állítja.

II. Legyen most

n

páros, és írjuk fel

n = 2^{α} \cdot n_{1}

alakban, ahol

α \geq 1

és

n_{1}

páratlan.
a) Ha

n_{1} = 1

, akkor

n 2

-hatvány, ahogy állítottuk; ekkor a feltétel nyilván teljesül, hiszen az

a_{i}

-k éppen az

n

-nél kisebb páratlan számok és

d = 2

.
b) Ha

n_{1} = 3

volna, akkor

n > 6

miatt

a_{1} = 1, a_{2} = 5, a_{3} = 7

és

a_{2} - a_{1} \neq a_{3} - a_{2}

, ez pedig lehetetlen.
c) Legyen végül

n_{1} \geq 5

. Megmutatjuk, hogy ekkor

n_{1} - 2

és

n_{1} - 4

szerepel az

a_{i}

-k között. Tegyük fel ugyanis, hogy

x | 2^{α} n_{1}

és

x | n_{1} - 2

. Ekkor

x | 2^{α} n_{1} = 2^{α} (n_{1} - 2) + 2^{α + 1}

miatt

x | 2^{α + 1}

. De

x

páratlan, így

x = 1

, azaz

(n_{1} - 2, 2^{α} n_{1}) = 1

. Hasonlóan

(n_{1} - 4, 2^{α} n_{1}) = 1

. Nyilván

n_{1} - 3

nem szerepel az

a_{i}

-k között, hiszen páros; így

d = 2

. De ekkor

n_{1}

is szerepel az

a_{i}

-k között (az

a_{i}

-k rendre

1,3,5, ..., n_{1} - 2, n_{1}, ...

). Ez viszont ellentmondás, mert

(n_{1}, n) = n_{1} > 1

.
Beláttuk tehát, hogy

n

prím vagy

2

-hatvány, a bizonyítást befejeztük.