Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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 <17\), ugyanis, ha \(\displaystyle 2^{17}\) már hatjegyű, és így ha \(\displaystyle p,q\) valamelyike (mondjuk \(\displaystyle q\)) legalább 17 lenne, akkor \(\displaystyle N+M\) legalább hatjegyű lenne (hiszen már \(\displaystyle p^q\geq 2^{17}\) is legalább hatjegyű).

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

\(\displaystyle p\) 2 2 2 2 2 3 3 3 3 5 5 5 7 7 11
\(\displaystyle q\) 3 5 7 11 13 5 7 11 13 7 11 13 11 13 13
\(\displaystyle N+M\) 7 21 71 1035 4109 106 778 59170 531610 18026 9780266 nagy nagy nagy nagy

(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=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 két megfelelő választás van: \(\displaystyle p=11,q=3\) és \(\displaystyle p=7,q=5\).

Azaz \(\displaystyle M\) és \(\displaystyle N\) lehetséges értékei:
\(\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\).

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:

A C. 1524. feladat értékelése még nem fejeződött be.


A KöMaL 2019. januári matematika feladatai