Feladat: Gy.2688 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Faragó Gergely ,  Győry Máté ,  Megyesi Zoltán ,  Urbán Péter 
Füzet: 1991/november, 394 - 395. oldal  PDF file
Témakör(ök): Nevezetes azonosságok, Prímtényezős felbontás, Gyakorlat
Hivatkozás(ok):Feladatok: 1991/március: Gy.2688

Legyen m tetszőleges pozitív egész szám. Mekkora az 1991m-1 prímtényezős felbontásában a 2 kitevője?

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.

Jelöljük az 1991m-1 szám törzstényezős felbontásában a 2 kitevőjét f(m)-mel. Ha m=2kp alakú, ahol a p páratlan szám, akkor (1991m-1)-et két p-edik hatvány különbségeként szorzattá alakítva az első tényező (19912k-1), a második tényező pedig páratlan, így f(m)=f(2k), ahol tehát a k a 2 kitevője az m prímfelbontásában.
Mármost 19912k-1 szorzattá alakítható a következőképpen:

(19912k-1+1)(19912k-2+1)...(1991+1)(1991-1).(1)



Ha r>0 és páros, akkor 1991r+1 osztható 2-vel, de 4-gyel nem, hiszen 1991r+1=(1992-1)r+1 a 4-gyel osztva 2 maradékot ad. Mivel 1992=23249,1990=2995, ezért a fentiek alapján
f(2k)={1,ha  k=0,k+3,ha  k>0.

Ez azt jelenti, hogy ha k jelöli az m kitevő prímtényezős felbontásában a 2 kitevőjét, akkor k=0 ‐ tehát páratlan m kitevő esetén ‐ a keresett f(m) kitevő értéke 1, egyébként pedig k+3.