A C. 1524. feladat (2019. január)

C. 1524. Legyenek \(\displaystyle N\) és \(\displaystyle M\) pozitív egész számok, továbbá \(\displaystyle p\) és \(\displaystyle q\) különböző prímszámok. Tegyük fel, hogy \(\displaystyle N+M\) ötjegyű, \(\displaystyle N\)-nek osztója a \(\displaystyle p\), és osztóinak száma \(\displaystyle q\), ugyanakkor \(\displaystyle M\) osztható \(\displaystyle q\)-val, és osztóinak száma \(\displaystyle p\). Határozzuk meg \(\displaystyle N\) és \(\displaystyle M\) lehetséges értékeit.

(5 pont)

A beküldési határidő 2019. február 11-én LEJÁRT.

Megoldás. Először nézzük \(\displaystyle N\)-et: \(\displaystyle N\)-nek osztója a \(\displaystyle p\), és osztóinak száma \(\displaystyle q\), azaz

\(\displaystyle p|N\)

és

\(\displaystyle d(N)=q= \prod\limits_{i=1}^r (1+ \alpha_{i}),\)

ahol \(\displaystyle \alpha_{i}\), a szokásos módon, az \(\displaystyle N\) szám prímtényezős felbontásában az \(\displaystyle i\)-edik prím kitevője (\(\displaystyle r\) pedig \(\displaystyle N\) különböző prímosztóinak száma). Tehát \(\displaystyle d(N)=q\) előáll, mint \(\displaystyle r\) darab 1-nél nagyobb egész szorzata. Mivel \(\displaystyle q\) prím, így \(\displaystyle r=1\), azaz csak egyetlen prímosztója van \(\displaystyle N\)-nek, ami nem más, mint \(\displaystyle p\). Ebből következik, hogy

\(\displaystyle N=p^{q-1}.\)

Hasonlóan kapjuk, hogy

\(\displaystyle M=q^{p-1}.\)

Az ily módon kapott \(\displaystyle M\) és \(\displaystyle N\) számokra teljesül minden feltétel, esetleg attól eltekintve, hogy az \(\displaystyle N+M\) szám ötjegyű.

Most meg kell néznünk, hogy mely \(\displaystyle p,q\) különböző prímekre lesz \(\displaystyle M+N\) ötjegyű. Rögtön adódik, hogy \(\displaystyle p, q <18\), ugyanis \(\displaystyle 2^{17}\) már hatjegyű, és így ha \(\displaystyle p,q\) valamelyike (mondjuk \(\displaystyle q\)) legalább 18 lenne, akkor \(\displaystyle N+M\) legalább hatjegyű lenne (hiszen már \(\displaystyle p^{q-1}\geq 2^{17}\) is legalább hatjegyű).

A szimmetria alapján vizsgáljuk a \(\displaystyle p<q\) eseteket.

(Nem szükséges az összes \(\displaystyle 2\leq p<q\leq 13\) esetet megvizsgálni, hiszen ha valamely \(\displaystyle p,q\) párra az \(\displaystyle N+M\) összeg már legalább hatjegyű, akkor, ha \(\displaystyle p,q\) valamelyikét - vagy mindkettőt - nagyobbra cserélnénk, továbbra is túl nagy összeget kapnánk.)

Tehát a \(\displaystyle p=2\), \(\displaystyle q=17\); \(\displaystyle p=3,q=11\) és \(\displaystyle p=5,q=7\) esetekben kapunk megfelelő, ötjegyű összeget. Ennek megfelelően a \(\displaystyle p<q\) megszorítás nélkül még három megfelelő választás van: \(\displaystyle p=17\), \(\displaystyle q=2\); \(\displaystyle p=11,q=3\) és \(\displaystyle p=7,q=5\).

Azaz \(\displaystyle M\) és \(\displaystyle N\) lehetséges értékei:
\(\displaystyle M=65536\) és \(\displaystyle N=17\), \(\displaystyle M=59049\) és \(\displaystyle N=121\), \(\displaystyle M=15625\) és \(\displaystyle N=2401\), \(\displaystyle M=121\) és \(\displaystyle N=59049\), \(\displaystyle M=2401\) és \(\displaystyle N=15625\), végül \(\displaystyle M=17\) és \(\displaystyle N=65536\).

Visszaellenőrizve láthatjuk, hogy ezekben az esetekben teljesülnek az oszthatóságra, osztókra vonatkozó feltételek, illetve hogy \(\displaystyle M+N\) ötjegyű.

Statisztika:

50 dolgozat érkezett.
5 pontot kapott:	Ajtai Boglárka, Debreczeni Tibor, Hordós Adél Zita, Jankovits András, Kis 194 Károly, Mészáros 916 Márton, Molnár 410 István, Nyitrai Boglárka, Pipis Panna, Rozgonyi Gergely, Sal Dávid, Sebe Anna, Székelyhidi Klára, Tóth Benedek, Varga Ákos.
4 pontot kapott:	Facskó Vince, Kovács 111 Bence, Kozák 023 Balázs, Laczkó Anna, Lénárd Kristóf, Majerusz Ádám, Rusvai Miklós, Szabó 677 Balázs István, Szigeti Donát.
3 pontot kapott:	13 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	5 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	3 dolgozat.

A KöMaL 2019. januári matematika feladatai