Problem C. 1524. (January 2019)

C. 1524. Let \(\displaystyle N\) and \(\displaystyle M\) be positive integers, and let \(\displaystyle p\) and \(\displaystyle q\) denote different primes. Assume that \(\displaystyle N+M\) is a five-digit number, \(\displaystyle N\) is divisible by \(\displaystyle p\) and the number of its divisors is \(\displaystyle q\), while \(\displaystyle M\) is divisible by \(\displaystyle q\) and the number of its divisors is \(\displaystyle p\). Determine all possible values of \(\displaystyle N\) and \(\displaystyle M\).

(5 pont)

Deadline expired on February 11, 2019.

Sorry, the solution is available only in Hungarian. Google translation

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ű.

Statistics:

50 students sent a solution.
5 points:	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 points:	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 points:	13 students.
2 points:	1 student.
1 point:	4 students.
0 point:	5 students.
Not shown because of missing birth date or parental permission:	3 solutions.

Problems in Mathematics of KöMaL, January 2019