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