Kezdőlap


Cím:	Egy érdekes számelméleti tétel
Szerző(k):	Zábrádi Gergely
Füzet:	1998/január, 16 - 17. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Pósa Lajos tanár úr szakkörén kaptam a következő feladatot: Osszuk fel a természetes számok halmazát két olyan diszjunkt részhalmazra, hogy az egyikben ne legyen végtelen számtani sorozat, a másikban pedig ne legyen három tagú számtani sorozat. A feladatra létezik egyszerű és viszonylag kevés matematikai ismeretet igénylő konstrukció, de én egy másik úton indultam el, amelyiken nem lehet eljutni az egyszerű megoldáshoz. Megpróbáltam egy olyan természetes számokból álló halmazt létrehozni, amelyben nincs három tagú számtani sorozat, de bármely egész számokból álló végtelen számtani sorozatból tartalmaz legalább egy elemet. Ha ilyen halmaz létezik, ekkor ez a halmaz és komplementerhalmaza kielégíti a feladat követelményeit, mert ha a komplementerhalmaz tartalmazna egy végtelen számtani sorozatot, akkor a konstruált halmazunkban nem lenne egy elem sem ebből a végtelen számtani sorozatból. Hosszas próbálkozások után eljutottam egy olyan halmazhoz, amelyben a $4^{n} + n$ alakú számok vannak, ahol $n$ tetszőleges pozitív egész. Amikor megpróbáltam bizonyítani, hogy ez a konstrukció megfelel a feltételeknek, egy érdekes ‐ számomra eddig ismeretlen ‐ számelméleti tételt találtam, amit be is bizonyítottam:

Tétel: Minden

a

c > 0

és

b \geq 0

adott egész számok esetén végtelen sok megoldása van az alábbi kongruenciának:

\begin{matrix} a^{x} + x \equiv b (mod c) \end{matrix}

(Ez a tétel azért érdekes számomra, mert állítása egyszerű, és nincs különösebb feltétel az adott számokra. Számelméleti tételeknél általában szokott valami olyan feltétel lenni az adott számokra, hogy kettő kozülük relatív prím, vagy hogy közülük kettő legnagyobb közös osztájának többszöröse egy harmadik. Ennél a tételnél nincs ilyen feltétel.)

Bizonyítás. Az

a^{n}

mértani sorozat elemeinek

c

-vel való osztási maradéka egy idő után ciklikus, mert egy szám

a

-szorosának maradéka csak a szám maradékától függ. Legyen a ciklus hossza (ahány szám ismétlődik)

d

. Ekkor

\begin{matrix} a^{i + d k} \equiv a^{i} (mod c) \end{matrix}

minden

k

és elég nagy

i

pozitív egészre. Legyen

e

d

-nek és

c

-nek a legnagyobb közös osztója. Ebből következik, hogy

d

többszörösei minden

e

-vel osztható maradékot felvesznek modulo

c

. Belátjuk, hogy

c > e

. Az biztos, hogy

e

nem lehet nagyobb, mint

c

, hiszen osztója. Tegyük fel, hogy

c = e

. Ekkor

d

többszöröse

c

-nek. Mivel

a^{n}

-nek

c

-vel való osztási maradékai a cikluson belül nem lehetnek egyenlőek (különben rövidebb lenne a ciklus), azért a ciklus hossza legfeljebb

c

(ennyi maradék van). Tehát

c = d

. Így valamilyen

n

-re

c

osztója

a^{n}

-nek, mert minden maradék benne van a ciklusban. Ez azt jelenti, hogy az összes ennél nagyobb

a

-hatvány osztható

c

-vel. Tehát

d = c = 1

.
Az állítást

c

szerinti teljes indukcióval bizonyítjuk. Az állítás nyilvánvalóan igaz, ha

c = 1

. Feltesszük, hogy

c > 1

, és minden

c

-nél kisebb egészre igaz az állitás. Tehát

e

-re is, mert

c > 1

esetén

c > e

. Tehát léteznek olyan elég nagy

n_{0}

n_{1}

n_{2}

...

n_{e - 1}

számok, hogy

\begin{matrix} a^{n_{i}} + n_{i} \equiv i (mod e) \end{matrix}

minden

i = 0

, 1, 2,

...

e - 1

-re (annyira, hogy közülük a legkisebbnél már elkezdődik

a^{n}

ciklusa modulo

c

. Ilyen van, mert indukciós feltevésünk szerint végtelen sok, tehát tetszőlegesen nagy

n_{i}

is van). Ebből következik, hogy

\begin{matrix} a^{n_{i} + k d} + n_{i} + k d \equiv a^{n_{i}} + n_{i} + k d (mod c) \end{matrix}

minden pozitív

k

egészre,

\begin{matrix} a^{n_{i}} + n_{i} \equiv e l + i \end{matrix}

valamilyen

l

pozitív egészre, mert

e

osztója

c

-nek; és

k d

felvesz minden

e

-vel osztható maradékot modulo

c

. Ekkor

a^{n_{i} + k d} + n_{i} + k d

előállít minden

e m + i

alakú maradékot modulo

c

, ahol

m

tetszőleges nemnegatív egész, és

k

végigfut a nemnegatív egészeken. Mivel

i

végigfut a 0; 1; 2;

...

;

e - 1

számokon, azért

a^{n} + n

előállít minden

c

-vel való osztási maradékot. Tehát az

a^{x} + x \equiv b (mod c)

kongruencia megoldható minden

a

b

és

c > 0

nemnegatív egészre. Ezzel az állítást igazoltuk.

Zábrádi Gergely
Győr, Révai Miklós Gimnázium, 10. o.t.