A B. 4744. feladat (2015. november)

B. 4744. Legyen \(\displaystyle n\) nemnegatív egész szám. Határozzuk meg a 7 kitevőjét a \(\displaystyle 3^{7^n} + 4^{7^n}\) prímtényezős alakjában.

Javasolta: Williams Kada (Szeged, Radnóti M. Gimn.)

(5 pont)

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

Megoldás. Az \(\displaystyle n\) szerinti indukcióval megmutatjuk, hogy

Ha \(\displaystyle n=0\), akkor \(\displaystyle 3^{7^n} + 4^{7^n}=7\), és így \(\displaystyle (*)\) triviálisan teljesül.

Tegyük most fel, hogy \(\displaystyle (*)\) teljesül valamilyen \(\displaystyle n\) nemnegatív egészre, és vizsgáljuk a rákövetkező kitevőt. Feltevésünk szerint \(\displaystyle 3^{7^n} + 4^{7^n} = 7^{n+1} A\) valamilyen alkalmas, \(\displaystyle 7\)-tel nem osztható \(\displaystyle A\) számmal. A tagok hetedik hatványának összegét a binomiális tétel segítségével kifejtve:

\(\displaystyle 3^{7^{n+1}} + 4^{7^{n+1}} = \big(3^{7^n}\big)^7 + \big(4^{7^n}\big)^7 = \big(3^{7^n}\big)^7 + \big(7^{n+1}A-3^{7^n}\big)^7 = \)

Az első tag, \(\displaystyle \binom71 \big(7^{n+1}A\big) \big(3^{7^n}\big)^6 = 7^{n+2}A\cdot 3^{6\cdot 7^n}\) osztható \(\displaystyle 7^{n+2}\)-vel, de nem osztható \(\displaystyle 7^{n+3}\)-mal.

A második tag, \(\displaystyle -\binom72 \big(7^{n+1}A\big)^2 \big(3^{7^n}\big)^5= -7^{2n+3}A^2\cdot 3^{5\cdot 7^n+1}\) osztható \(\displaystyle 7^{n+3}\)-mal.

A további tagok mind oszthatók \(\displaystyle (7^{n+1})^3=7^{3n+3}\)-mal, így oszthatók \(\displaystyle 7^{n+3}\)-mal.

Az (1)-ben szereplő összegben tehát mindegyik tag osztható \(\displaystyle 7^{n+2}\)-vel, és egy kivétellel mindegyik osztható a következő hatvánnyal, \(\displaystyle 7^{n+3}\)-mal is, de az első tag nem osztható \(\displaystyle 7^{n+3}\)-mal. Ezért az (1) összeg prímtényezős felbontásában a \(\displaystyle 7\) kitevője \(\displaystyle n+2\), ami bizonyítja \(\displaystyle (*)\)-ot az \(\displaystyle n+1\) kitevőre.

Megjegyzés. A megoldás során bizonyított \(\displaystyle (*)\) összefüggés egy általánosabb tény speciális esete:

Lemma (Lifting The Exponent Lemma, LTE). Legyen \(\displaystyle p\) prímszám, és bármely \(\displaystyle m\ne0\) egészre jelölje \(\displaystyle v_p(m)\) a \(\displaystyle p\) kitevőjét az \(\displaystyle m\) prímtényezős felbontásában, továbbá legyen \(\displaystyle a\) és \(\displaystyle b\) két különöző egész, amelyekre \(\displaystyle a\equiv b\not\equiv 0\pmod p\). Ha \(\displaystyle p\) páratlan, vagy pedig \(\displaystyle p=2\) és \(\displaystyle 4|a-b\), akkor tetszőleges \(\displaystyle n\) pozitív egészre

\(\displaystyle v_p(a^n-b^n)=v_p(a-b)+v_p(n). \)

(A \(\displaystyle p=2\), \(\displaystyle v_2(a-b)=1\) kivételes esetben \(\displaystyle v_2(a^n-b^n)\) bármilyen \(\displaystyle v_2(n)+1\)-nél nagyobb érték lehet.)

A lemma fontos szerepet játszik például a Zsigmondy-tétel bizonyításában, de számos versenyfeladat megoldását (pl. IMO 1990/3) le lehet egyszerűsíteni a segítségével.

Megjegyzés. Két elég gyakori hibát követtek el a megoldók. Az egyik, hogy indukciós bizonyításban az \(\displaystyle n=0\) esetet megnézték, de utána a bizonyításban kihasználták, hogy \(\displaystyle n\ge1\), pedig emiatt meg kellett volna nézni az \(\displaystyle n=1\) esetet is. Erre általában 1 pontot vontunk le.

Egy másik gyakori hiba volt, hogy szorzattá bontás után az egyik tagról be kellett volna látni, hogy 7-tel osztható, de 49-cel nem. Utóbbiról többen megfeledkeztek, vagy 7-es maradékkal próbálták kihozni, de ez helytelen megközelítés volt. Ezért általában 2 pontot vontunk le.

Szintén gyakori probléma volt, hogy a versenyzők bizonyítás nélkül mondtak ki komolyabb állításokat (például, hogy egy nagy binomiális együtthatóban mi a 7 kitevője). Ha ez volt a kulcs, akkor a megoldásra 1-2 pontnál többet nem tudtunk adni.

Statisztika:

82 dolgozat érkezett.
5 pontot kapott:	Andó Angelika, Barabás Ábel, Baran Zsuzsanna, Bindics Boldizsár, Bodolai Előd, Borbényi Márton, Busa 423 Máté, Cseh Kristóf, Czirkos Angéla, Döbröntei Dávid Bence, Gál Hanna, Gáspár Attila, Glasznova Maja, Hansel Soma, Horváth András János, Horváth Miklós Zsigmond, Janzer Orsolya Lili, Kerekes Anna, Klász Viktória, Kocsis Júlia, Kovács 246 Benedek, Lajkó Kálmán, Matolcsi Dávid, Molnár-Sáska Zoltán, Nagy Kartal, Németh 123 Balázs, Polgár Márton, Schrettner Bálint, Schrettner Jakab, Szabó 417 Dávid, Szakály Marcell, Szécsényi Nándor, Tóth Viktor, Vágó Ákos, Váli Benedek, Vankó Miléna, Zsigri Bálint.
4 pontot kapott:	Bukva Balázs, Imolay András, Keresztes László, Keresztfalvi Bálint, Krausz Gergely, Nagy Dávid Paszkál, Vághy Mihály.
3 pontot kapott:	12 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	12 versenyző.
0 pontot kapott:	7 versenyző.
Nem versenyszerű:	3 dolgozat.

A KöMaL 2015. novemberi matematika feladatai