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. 1703. feladat (2022. január)

C. 1703. Az \(\displaystyle a\) és \(\displaystyle b \,\,10\)-es számrendszerbeli természetes számok, mindegyik számjegyük \(\displaystyle 1\)-es. Mutassuk meg, hogy ha \(\displaystyle a\) és \(\displaystyle b\) nem relatív prímek, akkor számjegyeik \(\displaystyle S(a)\) és \(\displaystyle S(b)\) összege sem az.

(5 pont)

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


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.


Statisztika:

25 dolgozat érkezett.
5 pontot kapott: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 pontot kapott:Murai Dóra Eszter, Pájer Vilmos, Szabó Zóra.
3 pontot kapott:4 versenyző.
1 pontot kapott:3 versenyző.
0 pontot kapott:1 versenyző.
Nem versenyszerű:3 dolgozat.

A KöMaL 2022. januári matematika feladatai