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