Feladat: Gy.2345 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1986/december, 451 - 452. oldal  PDF  |  MathML 
Témakör(ök): Lineáris kongruencia-rendszerek, Szorzat, hatvány számjegyei, Számjegyekkel kapcsolatos feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1986/május: Gy.2345

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. Az A2 utolsó 5 jegye pontosan akkor azonos az A5 jegyével, ha A2-A legalább 5 nullára végződik, azaz 105|A2-A.
Ez pontosan akkor igaz, ha 25|A2-A és 55|A2-A, hiszen 105=25⋅55, másrészt 25 és 55 relatív prímek, így a szorzatuk pontosan akkor osztója (A2-A)-nak, ha maguk is azok.
Másfelől A2-A=(A-1) ugyancsak relatív prím tényezők szorzata, ami azt jelenti, hogy 2|A pontosan akkor teljesül, ha 2∤A-1, és ha 5|A(A-1), akkor ugyanez az 5-re is igaz. Az A és az A-1 tényezők közül tehát pontosan az egyik osztható 25-nel és 55-nel is. Ez a tényező nem lehet mindkét esetben ugyanaz, hisz ekkor a 25⋅55=105-nel is osztható volna, ami nem lehet, mert a keresett A ötjegyű szám és így kisebb, mint 105.
Így két eset lehetséges:
 
1. 25|A   és   55|A-1;
2. 25|A-1és55|A.
 
Lapunk ez évi márciusi számában jelent meg Kós Géza cikke a "Kínai maradék tétel polinomokra'' címmel. A továbbiakban a cikkben kimondott "eredeti'' kínai maradéktételt használjuk fel. Eszerint:
 
Ha m1,m2,...,mk páronként relatív prím egész számok és az a1,a2,...,ak tetszőleges egész számok, akkor az M≡ai(modmi) kongruenciáknak van közös M megoldása, és a megoldások kongruensek modulo m1⋅m2⋅...⋅mk.
Esetünkben k=2,m1=25,m2=55, az előírt maradékok az első esetben 0 és 1, a másodikban pedig 1 és 0. A tétel szerint mindkét esetben pontosan egy 105-nél kisebb megoldás van és a cikkben eljárást találunk a megoldás előállítására is. A fent kimondott tétel jelöléseivel a megoldás
 
M=∑j=1kajbjm1⋅m2⋅...⋅mkmj

 

alakú, ahol a bj számokra bj⋅m1⋅m2⋅...⋅mkmj≡1(modmj).
Most a b1,b2 értékekre a b1⋅55≡(mod25) és a b2⋅25≡1(mod55) kongruenciáknak kell fennállniuk.
A fenti kongruenciákat megoldva ‐ erről lásd pl.
Niven-Zuckermann: Bevezetés a számelméletbe című könyvét (Műszaki Könyvkiadó, 1978) 34‐36. oldal ‐ kapjuk, hogy b1=29 és b2=293.
Az 1. esetben innen A=0⋅b1⋅m2+1⋅b2⋅m1=293⋅32=9376, a másodikban pedig A=1⋅b1⋅m2+0⋅b2⋅m1=29⋅3125=90625 adódik.
Az első megoldás, a 9376 nem valódi ötjegyű szám (noha 105|A2-A;93762=87909376), így a feladat szövege szerint nem tekinthető megoldásnak.
Tehát egyetlenegy olyan ötjegyű A szám van, amelyre az A2 utolsó 5 jegyéből álló szám éppen az A: a 90625.
 

II. megoldás. Vizsgáljuk a kérdést általában: nevezzük n-jegyű "rímelőnek'' azokat a legfeljebb n-jegyű A számokat, amelyek négyzetében az utolsó n jegyből álló szám éppen az A. Az első megoldáshoz hasonlóan A pontosan akkor ilyen, ha 10n|A2-A.
Vegyük észre, hogy a fenti A nem feltétlenül valódi n-jegyű szám; megfelelő számú vezető 0-val például az 1 minden n-re rímelő. Feladatunk a valódi ötjegyű rímelő számok előállítása.
Ha A n-jegyű rímelő szám (n>1), akkor első jegyét ‐ ez lehet 0 is ‐ a-val jelölve A=10n-1⋅a+B alakú, ahol B legfeljebb (n-1)-jegyű. Ekkor
 
A2-A=102n-2⋅a2+10n-1⋅a(2B-1)+B2-B.

 
Mivel a fenti felbontás első két tagja osztható 10n-1-nel, az összeg pedig 10n-nel, ‐ hiszen A rímelő ‐ ezért 10n-1|B2-B, tehát a B egy (n-1)-jegyű rímelő szám.
Megfordítva, minden egyes (n-1) jegyű rímelő B számhoz létezik egy és csak egy 0≤a≤9 egész, amelyre 10n-1⋅a+B n-jegyű rímelő. Tekintsük ugyanis a (B2-B):10n-1 hányados ‐ ami feltételünk szerint egész ‐ maradékát 10-zel osztva. Mivel (2B-1,10)=1 ‐ a 2B-1 páratlan és 5-tel sem osztható, ha 10n-1|B(B-1), hisz ilyenkor 5|B vagy 5|B-1 ‐, a (2B-1)-et a 0,1,2,...,9 számokkal rendre megszorozva a tíz darab szorzat minden egyes maradékot kiad 10-zel osztva. Megkapjuk tehát azt is, amely a (B2-B):10n-1 hányadost 10-zel osztható számmá egészíti ki.
A fentiek alapján az egyjegyű rímelő számokból kiindulva rendre megkaphatjuk a 2,3,4,5-jegyűeket is.
Az egyjegyű rímelő számok a 0,1,5 és a 6. Az első két esetben 10n|02-0, illetve 10n|12-1 minden n-re, ezért minden újabb lépésben a 0 az alkalmas kezdő számjegy: ilyenkor nem kapunk valódi rímelő számokat.
Az 5-re és a 6-ra végződő számok esetében a számolás egyszerűen adódik, ugyanis az ilyen számokra 2A-1 utolsó jegye 9, illetve 1. Így az (A2-A):10n utolsó jegyét b-vel jelölve a (2A-1)-nek a b-t 10-zel osztható számmá kiegészítő többszöröse az első esetben b⋅9, a másodikban pedig (10-b)⋅1. Ennek megfelelően az 5-ből kiindulva minden egyes újabb szám első jegye (A2-A):10n utolsó jegye, a 6 esetében pedig az ezt 10-re kiegészítő szám.
 
1111n111A(A2-A):10n11utolsó jegye11111115112211112516311162510411062519519062511           111111n111A(A2-A):10n11utolsó jegy11111116113211117617311137611411937610510937611

 

Látható, hogy a 6-ból indulva nem kaptunk valódi ötjegyű számot; a feladat egyetlen megoldása tehát az A=90625.
 

Megjegyzés. Mindkét megoldásból kiderül, hogy ha n>1, akkor legfeljebb két olyan valódi n-jegyű A szám van, amelyre az A2 utolsó n jegyéből álló szám éppen az A.