A B. 4720. feladat (2015. május)

B. 4720. Figyelem! A feladat szövege a nyomtatott lapban hibásan jelent meg.

Legyenek $\displaystyle a$ és $\displaystyle n$ olyan pozitív egészek, amelyekre $\displaystyle a^n-1$ osztható $\displaystyle n$-nel. Bizonyítsuk be, hogy az $\displaystyle a+1$, $\displaystyle a^2+2$, ..., $\displaystyle a^n+n$ számok mind különböző maradékot adnak $\displaystyle n$-nel osztva.

(6 pont)

A beküldési határidő 2015. június 10-én LEJÁRT.

Megoldásvázlat. Az állítást $\displaystyle n$ szerinti teljes indukcióval bizonyítjuk. Ha $\displaystyle n=1$, akkor az állítás triviális. Tegyük tehát fel, hogy $\displaystyle n\ge2$, és az állítás igaz minden kisebb értékre. Mivel a feltétel szerint $\displaystyle a^n\equiv 1\pmod{n}$, az $\displaystyle a$ relatív prím az $\displaystyle n$-nel.

Legyen $\displaystyle k$ a legkisebb olyan pozitív egész, amire $\displaystyle a^k\equiv 1\pmod{n}$, azaz legyen $\displaystyle k$ az $\displaystyle a$ multiplikatív rendje modulo $\displaystyle n$. Mint jól ismert, az $\displaystyle 1,a,a^2,\dots$ sorozat periodikus modulo $\displaystyle n$, a legkisebb periódusa a $\displaystyle k$, és egy perióduson belül a modulo $\displaystyle n$ maradékok különböznek; mivel $\displaystyle a^n\equiv a^0=1\pmod{n}$, a $\displaystyle k$ osztója az $\displaystyle n$-nek. Továbbá, mivel a $\displaystyle 0$ maradék nem fordulhat elő, az is biztos, hogy $\displaystyle k<n$; tehát $\displaystyle k$ egy valódi osztója az $\displaystyle n$-nek.

Tudjuk, hogy az indukciós feltevés igaz a $\displaystyle k$ számra is, tehát az $\displaystyle a^1+1,a^2+2,\ldots,a^k+k$ számok különböző maradékot adnak modulo $\displaystyle k$.

Tekintsünk két különböző egész számot $\displaystyle 1$ és $\displaystyle n$ között; legyen $\displaystyle 1\le p,q\le n$. Azt kell megmutatnunk, hogy $\displaystyle a^p+p\not\equiv a^q+q\pmod{n}$. A $\displaystyle p,q$ számokat írjuk $\displaystyle p=kx+y$, $\displaystyle q=ku+v$ alakban, ahol $\displaystyle 1\le y,v\le k$ és $\displaystyle 0\le x,u<\frac{n}{k}$. Mivel $\displaystyle k$ az $\displaystyle a$ rendje modulo $\displaystyle n$, tudjuk, hogy $\displaystyle a^p=a^{kx+y}\equiv a^y\pmod{n}$ és hasonlóan $\displaystyle a^q\equiv a^v\pmod{n}$.

1. eset: $\displaystyle y\ne v$. Az indukciós feltevés miatt

$\displaystyle a^p+p \equiv a^y+y \not\equiv a^v+v\equiv a^q+q \pmod{k},$

így $\displaystyle a^p+p\not\equiv a^q+q\pmod{n}$, kész vagyunk.

2. eset: $\displaystyle y=v$. Mivel $\displaystyle p\ne q$, ezért $\displaystyle x\ne u$, és

$\displaystyle a^p+p \equiv a^y+kx+y = a^v+ku+v + k(x-u) \equiv a^q+q + k(x-u) \not\equiv a^q+q \pmod{n},$

az állítás most is teljesül.

Statisztika:

16 dolgozat érkezett.
6 pontot kapott:	Baran Zsuzsanna, Fekete Panna, Gál Boglárka, Gáspár Attila, Lajkó Kálmán, Nagy-György Pál, Németh 123 Balázs, Szebellédi Márton, Williams Kada.
5 pontot kapott:	Glasznova Maja.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2015. májusi matematika feladatai