Kezdőlap


Feladat:	N.70	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Gyarmati Katalin , Izsák Ferenc , Pap Gyula , Póczos Barnabás , Tóth Gábor Zsolt , Valkó Benedek
Füzet:	1996/február, 103. oldal		PDF \| MathML
Témakör(ök):	Euler-Fermat-tételek, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1995/május: N.70

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.

A feladatot először abban a speciális esetben oldjuk meg, amikor $c$ és $d$ relatív prímek. Az $a$ , $b$ , $c$ , $d$ számok különbözősége helyett csupán annyit kötünk ki, hogy nem lehet $c$ és $d$ értéke is $1$ .
Tegyük fel, hogy az $a c^{n} + b d^{n}$ alakú pozitív egészeknek összesen csak véges sok prímosztója van. Legyenek ezek $p_{1}$ , $p_{2}$ , $...$ , $p_{m}$ . Válasszunk mindegyik $p_{i}$ -hez egy olyan $α_{i}$ pozitív egészet, hogy $a$ , $b$ és $a + b$ egyike se legyen osztható $p^{α_{i}}$ -vel.
Azt állítjuk, hogy ha $n$ elég nagy és osztható $φ (p_{i}^{α_{i}})$ -vel, akkor $a c^{n} + b d^{n}$ nem osztható $p_{i}^{α_{i}}$ -vel. ( $φ$ az Euler-féle függvény: $φ (n)$ az $n$ -nél nem nagyobb, $n$ -hez relatív prím pozitív egészek száma.) A lehetséges eseteket két részre osztjuk.
I. eset: ha sem $c$ , sem $d$ nem osztható $p_{i}$ -vel. Legyen $n = k φ (p_{i}^{α_{i}})$ . Az Euler‐Fermat tétel szerint

\begin{matrix} c^{n} = {(c^{k})}^{φ (p_{i}^{α_{i}})} \equiv 1 mod p_{i}^{α_{i}} és d^{n} = {(d^{k})}^{φ (p_{i}^{α_{i}})} \equiv 1 mod p_{i}^{α_{i}}, \end{matrix}

ezért

\begin{matrix} a c^{n} + b d^{n} \equiv a + b mod p_{i}^{α_{i}} . \end{matrix}

α_{i}

definíciója szerint

a + b

nem osztható

p_{i}^{α_{i}}

-nel.
II. eset: ha

c

vagy

d

osztható

p_{i}

-vel. Az állítás szimmetriája miatt feltehetjük, hogy

c

osztható

p_{i}

-vel. Mivel

c

és

d

relatív prímek, ebben az esetben

d

nem osztható

p_{i}

-vel. Ha

n \geq α_{i}

, akkor

c^{n}

osztható

p_{i}^{α_{i}}

-nel, és ‐ ismét felhasználva az Euler‐Fermat tételt ‐

\begin{matrix} a c^{n} + b d^{n} \equiv a \cdot 0 + b \cdot 1 = b mod p_{i}^{α_{i}} . \end{matrix}

Mivel

b

nem osztható

p_{i}^{α_{i}}

-nel, kész vagyunk.
Legyen most

P = φ (p_{1}^{α_{1}}) φ (p_{2}^{α_{2}}) ... φ (p_{m}^{α_{m}})

. Ha

n

elég nagy és osztható

P

-vel, akkor

a c^{n} + b d^{n}

nem osztható

p_{i}^{α_{i}}

-nel semmilyen

i

-re sem, tehát prímtényezős felbontásban a

p_{i}

kitevője kisebb, mint

α_{i}

. Mivel az indirekt feltevés szerint más prímosztója nincs, ebből következik, hogy

\begin{matrix} a c^{n} + b d^{n} \leq p_{1}^{α_{1} - 1} p_{2}^{α_{2} - 1} ... p_{m}^{α_{m} - 1} . \end{matrix}

Ez azonban ellentmondás, mert

c

és

d

közül valamelyik legalább 2, így az

a c^{n} + b d^{n}

sorozat szigorúan monoton nő, és végtelenhez tart.
Hátravan még az általános eset vizsgálata, amikor

c

és

d

különböző, nem feltétlenül relatív prím számok. Legyen

c

és

d

legnagyobb közös osztója

q

;

c = c_{1} q

d = d_{1} q

, ahol

c_{1}

és

d_{1}

relatív prímek. Ezekkel a jelölésekkel

\begin{matrix} a c^{n} + b d^{n} = q^{n} (a c_{1}^{n} + b d_{1}^{n}) . \end{matrix}

Mivel

c_{1}

és

d_{1}

relatív prímek, a második tényező lehetséges értékeinek, mint láttuk, összesen végtelen sok prímosztója van.

Gyarmati Katalin (Fazekas M. Főv. Gyak. Gimn., III. o.t.)