Kezdőlap


Feladat:	1990. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Pataki János
Füzet:	1990/november, 340. oldal		PDF \| MathML
Témakör(ök):	Nevezetes azonosságok, Euler-Fermat-tételek, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1990/szeptember: 1990. é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.

$n = 3$ nyilván megoldás, hiszen $2^{3} + 1 = 9$ osztható $3^{2} = 9$ -cel. Megmutatjuk, hogy más megoldás nem létezik.
Írjuk ehhez az $n$ -et $3^{k} \cdot d$ alakba ( $k \geq 0$ , $3$ és $d$ relatív prímek). Ekkor

\begin{matrix} 2^{n} + 1 = 2^{3^{k} d} + 1 = (2^{d} + 1) \prod_{i = 0}^{k - 1} (2^{2 \cdot 3^{i} d} - 2^{3^{i} d} + 1) . \end{matrix}

(*)

Mivel minden páratlan

t

egészre

2^{2 t} - 2^{t} + 1

osztható 3-mal, de nem osztható 9-cel, ezért (1) jobb oldalán a

k

-tényezős szorzat 3-nak pontosan a

k

-adik hatványával osztható.
Ha most a fenti alakú szám megoldás, azaz

n^{2} = {(3^{k} d)}^{2}

osztója

2^{n} + 1

-nek, akkor a ,,hiányzó'' 3-as tényezőket az (1)-beli szorzat első tényezőjének kell tartalmaznia:

\begin{matrix} 3^{k} | 2^{d} + 1, \end{matrix}

ami csak a

k = 0

, vagy 1 esetekben lehetséges, hiszen

(d,3) = 1

miatt

9 ∤ 2^{d} + 1

.
Megmutatjuk, hogy

d

értéke csak 1 lehet. Tegyük fel, hogy

d > 1

és legyen a

d

legkisebb prímosztója

p

, ami legalább 5, másfelől

(p - 1, d) = 1

.
A feltétel miatt

\begin{matrix} p | 2^{n} + 1, \end{matrix}

(2)

a kis Fermat-tételből pedig

\begin{matrix} p | 2^{p - 1} - 1 \end{matrix}

következik. Így a

\begin{matrix} 2^{2 n} \equiv 1 (mod p) \end{matrix}

és

\begin{matrix} 2^{p - 1} \equiv 1 (mod p) \end{matrix}

kongruenciákból

\begin{matrix} 2^{m} \equiv 1 (mod p) \end{matrix}

(3)

következik, ahol

m = (2 n, p - 1)

.
Mivel

2 n | 2 \cdot 3 d

és

(p - 1, d) = 1

, ezért szükségképpen

m | 6

, azaz (3) szerint a

p

prímszám az

1

3

7

63

számok valamelyikének 3-nál nagyobb prímtényezője, ami csak úgy lehetséges, ha

p = 7

. Ez viszont lehetetlen, ugyanis (2) alapján ekkor

7 | 2^{n} + 1

, ami egyetlen pozitív egész

n

kitevővel sem teljesül. A

d

tehát valóban nem lehet 1-nél nagyobb.
A feladat feltétele így csak azokra az

n = 3^{k} d

számokra teljesülhet, amelyekre

k \leq 1

és

d = 1

. Ha

k = 0

, akkor

n = 1

, ha pedig

k = 1

, akkor

n = 3