Problem C. 1703. (January 2022)

C. 1703. The natural numbers \(\displaystyle a\) and \(\displaystyle b\) each have only digits of \(\displaystyle 1\) in decimal notation. Prove that if \(\displaystyle a\) and \(\displaystyle b\) are not relatively prime then the sums of their digits, \(\displaystyle S(a)\) and \(\displaystyle S(b)\) are not relatively prime either.

(5 pont)

Deadline expired on February 10, 2022.

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

Megoldás. Mivel \(\displaystyle a\) és \(\displaystyle b\) minden számjegye 1-es, ezért \(\displaystyle a=\frac{10^{S(a)}-1}{9}\) és \(\displaystyle b=\frac{10^{S(b)}-1}{9}\) (hiszen \(\displaystyle S(a)\), illetve \(\displaystyle S(b)\) éppen \(\displaystyle a\), illetve \(\displaystyle b\) jegyeinek száma). Tegyük fel, hogy \(\displaystyle a\) és \(\displaystyle b\) nem relatív prímek, legyen \(\displaystyle d>1\) az \(\displaystyle a\) és \(\displaystyle b\) számok egy közös osztója. Ekkor

\(\displaystyle 9d\mid 10^{S(a)}-1\text{ és }9d\mid 10^{S(b)}-1.\)

Tekintsük a 10-hatványok \(\displaystyle 9d\)-vel adott osztási maradékainak sorozatát. A \(\displaystyle 10^0=1\) maradéka 1, a \(\displaystyle 10^1=10\) maradéka pedig nem 1, mert \(\displaystyle 9d>9\). Mivel \(\displaystyle 9d\mid 10^{S(a)}-1\), ezért az 1-en kívül is lesz olyan 10-hatvány, ami 1 maradékot ad. A legkisebb ilyen legyen \(\displaystyle 10^r\), ekkor tehát \(\displaystyle r>1\). Ekkor \(\displaystyle 10^r\)-től kezdve az \(\displaystyle 1,10,10^2,\dots,10^{r-1}\) számok \(\displaystyle 9d\)-es maradékának sorozata ismétlődik ciklikusan. Speciálisan ez azt is jelenti, hogy \(\displaystyle 10^n\) pontosan akkor ad 1 maradékot \(\displaystyle 9d\)-vel osztva, ha \(\displaystyle r\mid n\). Mivel a feltételek szerint \(\displaystyle 10^{S(a)}\) és \(\displaystyle 10^{S(b)}\) is 1 maradékot adnak \(\displaystyle 9d\)-vel osztva, ezért \(\displaystyle r\) mind az \(\displaystyle S(a)\), mind az \(\displaystyle S(b)\) számnak osztója. Tehát \(\displaystyle S(a)\) és \(\displaystyle S(b)\) nem relatív prímek, ezzel igazoltuk a feladat állítását.

Megjegyzés. Nem nehéz megmutatni, hogy \(\displaystyle a=\frac{10^{S(a)}-1}{9}\) és \(\displaystyle b=\frac{10^{S(b)}-1}{9}\) számok legnagyobb közös osztója \(\displaystyle \frac{10^{(S(a),S(b))}-1}{9}\). Ezt \(\displaystyle a+b\)-re vonatkozó teljes indukcióval igazoljuk. Ha \(\displaystyle a+b=2\), vagyis \(\displaystyle a=b=1\), akkor az állítás teljesül. Az indukciós lépéshez tegyük fel, hogy \(\displaystyle a+b< k\) esetén már igazoltuk az állítást valamely \(\displaystyle 2<k\)-ra és vegyünk egy \(\displaystyle a,b\) párt (ha van ilyen), melyre \(\displaystyle a+b=k\). Legyen

\(\displaystyle d:=(a,b)=(\underbrace{11\ldots1}_{S(a)},\underbrace{11\ldots 1}_{S(b)}).\)

Ha \(\displaystyle a=b\), akkor az állítás teljesül, a továbbiakban feltesszük, hogy \(\displaystyle a>b\). (Az \(\displaystyle a<b\) szimmetrikus eset ugyanúgy kezelhető.)

Világos, hogy

\(\displaystyle d=(a,b)=(a-b,b)=(\underbrace{11\ldots1}_{S(a)-S(b)}\underbrace{00\ldots0}_{S(b)},\underbrace{11\ldots1}_{S(b)}).\)

Mivel \(\displaystyle (b,10)=1\), ezért ebből kapjuk, hogy \(\displaystyle d=(\underbrace{11\ldots1}_{S(a)-S(b)},\underbrace{11\ldots1}_{S(b)})\) is teljesül, azonban az indukciós feltevés alapján ez éppen \(\displaystyle \frac{10^{(S(a)-S(b),S(b))}-1}{9}\). Mivel \(\displaystyle (S(a)-S(b),S(b))=(S(a),S(b))\), ezért ezzel az indukciós lépést igazoltuk.

Statistics:

25 students sent a solution.
5 points:	Besze Zsolt, Cynolter Dorottya, Egyházi Hanna, Halász Henrik, Horváth Milán, Keszthelyi Eszter, Kurucz Márton, Nagy Daniella, Sipeki Márton, Szalanics Tamás.
4 points:	Murai Dóra Eszter, Pájer Vilmos, Szabó Zóra.
3 points:	4 students.
1 point:	3 students.
0 point:	1 student.
Unfair, not evaluated:	3 solutionss.

Problems in Mathematics of KöMaL, January 2022