Az A. 415. feladat (2006. december)

A. 415. Bizonyítsuk be, hogy tetszőleges a>b és n pozitív egészek esetén (aⁿ-bⁿ) osztható n-nel. ((m) jelöli az m-nél nem nagyobb, m-mel relatív prím pozitív egészek számát.)

Javasolta: Strenner Balázs (Budapest)

(5 pont)

A beküldési határidő 2007. január 15-én LEJÁRT.

Megoldás. Legyen a és b legnagyobb közös osztója d, a=pd és b=qd. Mivel pⁿ-qⁿ osztója (aⁿ-bⁿ)-nek, (pⁿ-qⁿ) is osztója (aⁿ-bⁿ)-nek, és elég azt igazolni, hogy (pⁿ-qⁿ) osztható n-nel. Más szóval, elég az állítást abban az esetben igazolni, ha a és b relatív prímek.

Megjegyezzük, hogy a és b is relatív prím (aⁿ-bⁿ)-hez.

Legyen m=aⁿ-bⁿ és legyen c az az elem, amire acb mod  m. Először megmutatjuk, hogy az 1,c,c²,...,c^n-1 maradékosztályok mind különbözők, és cⁿ1 mod  m. Tekintsük a

bⁿ<bⁿc=ab^n-1<bⁿc²=a²b^n-2<...<bⁿc^n-1=a^n-1b<bⁿcⁿ=aⁿ

maradékosztályokat. Az első és utolsó szám küönbsége éppen aⁿ-bⁿ=m; a többi maradék tehát ezektől és egymástól különbözik. Mivel az m és a bⁿ relatív prímek, ebből következik, hogy az 1,c,c²,...,c^n-1 maradékosztályok különbözők és cⁿ1 mod  m.

Most tetszőleges olyan x számra, ami relatív prím m-mel, tekintsük az x,cx,c²,... maradékosztályokat modulo m. Minden ilyen sorozat pontosan n különböző maradékosztályt tartalmaz. A sorozatok a modulo m redukált maradékosztályokat (az m-mel relatív prím maradékosztályokat) n-es csoportokra osztják, a redukált maradékok száma, (m) tehát osztható n-nel.

Megjegyzés. Az utolsó lépésben valójában a csoportelméletből ismert Lagrange-tételt alkalmaztuk: Véges csoportban minden elem rendje osztója a csoport rendjének. A modulo m redukált maradékok multiplikatív csoportjában a csoport rendje (m), a c elem rendje n, tehát (m) osztható n-nel.

Statisztika:

9 dolgozat érkezett.
5 pontot kapott:	Gyenizse Gergő, Hujter Bálint, Kisfaludi-Bak Sándor, Kónya 495 Gábor, Korándi Dániel, Lovász László Miklós, Nagy 224 Csaba, Nagy 235 János, Tomon István.

A KöMaL 2006. decemberi matematika feladatai