Kezdőlap


Feladat:	1977. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Ivanyos Gábor
Füzet:	1977/november, 121 - 123. oldal		PDF \| MathML
Témakör(ök):	Indirekt bizonyítási mód, Skatulyaelv, Konstruktív megoldási módszer, Maradékos osztás, Maradékosztályok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1977/szeptember: 1977. évi Nemzetközi Matematika Diákolimpia 13. 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.

Az alábbiakban közöljük Ivanyos Gábornak a 3. feladatra adott megoldását, amelyért a zsüritől különdíjat kapott.^{$^{*}$}

Feladat: Legyen

n

adott,

2

-nél nagyobb természetes szám! Jelöljük

V_{n}

-nel azt a halmazt, amelynek elemei:

1 + k n

, ahol

k = 1, 2, ...

. Egy

m \in V_{n}

számot

V_{n}

-ben felbonthatatlannak mondunk, ha nincsenek olyan

p, q \in V_{n}

számok, amelyekre

p q = m

.
Bizonyítsuk be, hogy van olyan

r \in V_{n}

szám, amely több, mint egyféleképpen állítható elő

V_{n}

-ben felbonthatatlan számok szorzataként! (Azokat a felbontásokat, amelyek csak a

V_{n}

-ből vett tényezők sorrendjében különböznek egymástól, azonosaknak vesszük.)

Megoldás. a) Először azt fogjuk bizonyítani, hogy végtelen sok olyan prímszám van, amely

n

-nel osztva

1

-től különböző maradékot ad.
Tegyük fel, hogy csak véges sok van, és szorozzuk ezeket össze. Az így kapott szorzatot szorozzuk meg még

n

-nel, majd vonjunk ki belőle

1

-et. (

n > 2

miatt ez nem

1

maradékot ad

((mod n))

.). Az így kapott szám nem osztható a véges sok prím egyikével sem, tehát összes prímtényezői

(1 + m n)

alakúak lehetnek csak, azaz előállítható

(1 + m n)

alakú számok szorzataként. Azonban az

(1 + m n)

alakú számok szorzata szintén ilyen alakú, s a mi számunk nem

1

maradékot ad

((mod n))

, tehát ellentmondásra jutottunk.
Ebből következik, hogy létezik végtelen sok olyan prímszám, amely

n

-nel osztva nem

1

-et ad maradékul, tehát alkalmazható az adott bizonyítás.
b) Ismeretes, hogy végtelen sok prímszám van, ebből, és hogy

((mod n))

véges sok maradékosztály van, következik, hogy van olyan maradékosztály

((mod n))

, amelybe legalább

2 (n + 1)

prím esik.
Legyenek ezek

\begin{matrix} p_{1}, p_{2}, ..., p_{n}, p_{n + 1}, p_{n + 2} = q_{1}, p_{n + 3} = q_{2}, ..., q_{n + 1} = p_{2 n + 2}, \end{matrix}

melyek tehát

((mod n))

ugyanazt az

a

maradékot adják.
Segédtétel: van olyan

α \leq n

kitevő, hogy

\begin{matrix} a^{α} \equiv 1 ((mod n)) . \end{matrix}

Tekintsük az

a^{1}, a^{2}, ..., a^{n}, a^{n + 1}

hatványokat, a skatulyaelv szerint van köztük kettő, amely azonos maradékosztályba esik, azaz van olyan

n + 1 \geq α_{1} > α_{2}

természetes számpár, hogy

\begin{matrix} a^{α_{1}} \equiv a^{α_{2}} ((mod n)), \end{matrix}

azaz

\begin{matrix} n | a^{α_{2}} (a^{α_{1} - α_{2}} - 1) . \end{matrix}

a

maradékot

((mod n))

legalább

2 (n + 1)

prím ad, tehát van ezek között olyan, amely

n

-hez relatív prím, azaz

(a, n) = 1

.
Így csakis

n | a^{α_{1} - α_{2}} - 1

lehet, azaz

a^{α} \equiv 1 ((mod n))

n ≧ α = α_{1} - α_{2} ≧ 1

(egész) mellett.
c) Legyen a legkisebb ilyen

α

kitevő az

r

(ilyen létezik, mert

α ≦ n

miatt az ilyen

α

számok véges sokan vannak).
Ekkor

\begin{matrix} P = p_{i_{1}} p_{i_{2}} ... p_{i_{r}} = a^{r} \equiv 1 ((mod n)), \end{matrix}

tehát

P \in V_{n}

P

V_{n}

-ben felbonthatatlan, mert

1

-től és

P

-től különböző osztói

p_{j_{1}} p_{j_{2}} ... p_{j_{1}} \equiv a^{i} ((mod n))

, de

r

minimális volta miatt

a^{i} ≢ 1 ((mod n))

, tehát a felírt szorzat nem eleme

V_{n}

-nek, így az egyetlen lehetséges felbontás

1 \cdot P

lenne, de

1 < 1 + m n

(m n = 1, 2, ...)

miatt

1 \notin V_{n}

. Mivel a

a ≢ 1 ((mod n))

, ezért

r > 1

.
Válasszunk két

V_{n}

feletti felbonthatatlan számot:

\begin{matrix} P = p_{1} p_{2} ... p_{r}, Q = q_{1} q_{2} ... q_{r}, \end{matrix}

ekkor

P Q \in V_{n}

és

\begin{matrix} P Q = p_{1} p_{2} ... p_{r} q_{1} q_{2} ... q_{r} = q_{1} q_{2} ... p_{r} p_{1} q_{2} ... q_{r} = P' Q' . \end{matrix}

(P' = q_{1} p_{2} ... p_{r}, Q' = p_{1} q_{2} ... q_{r})

r > 1

miatt

P' \neq P

Q' \neq Q

. Az előbb láttuk hogy

P'

és

Q' V_{n}

-ben felbonthatatlan, így beláttuk a feladat állítását.

^{$^{*}$}A megoldás megszövegezése helyenként nem elég csiszolt, de ez érthető is. A rövid versenyidő nem ad lehetőséget arra, hogy a megoldók gondolataikat szépen fogalmazzák meg. Az értékelésnél itt az ötletek szépségét és egyszerűségét jutalmazzák a bírálók. (A szerk.)