Feladat: 2010. évi Kürschák matematikaverseny 3. feladata Korcsoport: - Nehézségi fok: -
Megoldó(k):  Fleiner Tamás 
Füzet: 2011/február, 70. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Maradékos osztás, Maradékosztályok
Hivatkozás(ok):Feladatok: 2011/február: 2010. évi Kürschák matematikaverseny 3. feladata

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.

Megoldás. Azt állítjuk, hogy pontosan akkor léteznek a kívánt ai és bj számok, ha n és k relatív prímek. Ehhez elsőként igazoljuk, hogy az állítás elégséges. Tegyük fel tehát, hogy (n,k)=1. Legyen 1≤i≤n és 1≤j≤k esetén ai=ik+1, illetve bj=jn+1. Az aibj=ijnk+ik+jn+1 szám n-nel osztva ik+1, k-val osztva pedig jn+1 maradékot ad. Az n és k relatív prím volta miatt 1≤i≤n esetén az ik+1 számok páronként különböző maradékot adnak n-nel osztva, 1≤j≤k esetén pedig a jn+1 számok páronként különböző maradékot adnak k-val osztva. Ha ugyanis mondjuk ik+1 és i'k+1 ugyanazt a maradékot adják n-nel osztva, akkor n∣ik+1-(i'k+1)=(i-i')k, ahonnan n∣(i-i') következik, hiszen n-nek és k-nak nincs közös prímosztója. Ez utóbbi oszthatóság és 1≤i,i'≤n miatt i=i'.
Azt kaptuk tehát, hogy bárhogyan is veszünk két különböző aibj szorzatot, azok n-nel vagy k-val osztva különböző maradékot adnak. Nem lehetséges tehát, hogy két különböző szorzat nk-val osztva azonos maradékot adjon, nekünk pedig éppen erre van szükségünk.
A szükségesség bizonyításához azt tesszük fel, hogy az ai és bj számok rendelkeznek a feladatban leírt tulajdonsággal. Ez azt is jelenti, hogy valamelyik, mondjuk a1b1 szorzat nk-val osztva 0 maradékot ad, azaz nk∣a1b1. Legyen a=(a1,nk) és b=(b1,nk). Világos, hogy nk∣ab, ezért nk≤ab.
Figyeljük meg, hogy a k db a1bj szorzat mindegyike osztható a-val. Márpedig az nk szerinti osztási maradékok között pontosan nka olyan van, amely a-val osztható. Ez azt jelenti, hogy k≤nka, azaz a≤n. Hasonló gondolatmenet igazolja a b≤k becslést. Ezek szerint ab≤nk, amit a korábbi nk≤ab megfigyeléssel összevetve azt kapjuk, hogy ab=nk. Ez utóbbi pedig csak úgy lehetséges, ha a=n és b=k.
Jelölje d az n és k legnagyobb közös osztóját. Ekkor n és k legkisebb közös többszöröse M=nkd. Számoljuk meg, hány olyan osztási maradék van nk szerint, amely n-nel vagy k-val osztható. Világos, hogy k maradék osztható n-nel és n maradék k-val, ám azokat a maradékokat, amelyek n-nel és k-val is oszthatók, kétszer számoltuk meg. Ezek éppen az M-mel osztható maradékok, számuk tehát nkM=d. Ezért pontosan n+k-d olyan nk szerinti maradék van, amely n-nel vagy k-val osztható. Azonban n∣a1 és k∣b1 miatt az a1bj, illetve aib1 szorzatok oszthatók n-nel, illetve k-val. Az ilyen szorzatok száma pedig n+k-1, ezért n+k-1≤n+k-d, azaz 1≥d=(n,k). Ezek szerint n és k valóban relatív prímek, ezzel pedig a feltétel szükségességét is igazoltuk.  □

 
Megjegyzés. A szükségességet igazoló gondolatmenet Dankovics Attila megoldásából származik.