Hogy oldjam meg? Relatív prímes feladat

Az állítás azzal ekvivalens, hogy egy p prímre p nem oszthatja mindkettőt, vagyis, minden p páratlan prímre a Z_p gyűrűben

vagy -1 nem kettőhatvány (ekkor p ∤ 2^n + 1)

vagy -1 kettőhatvány, de 2 rendje páros

Ez pedig egyszerű.

Biztos, hogy nem írom le teljesen. Talán valaki más. Mit nem értesz? A kongruenciákat ismered már? Mert akkor átfogalmazva:

Az állítás azzal ekvivalens, hogy egy p prímre p nem oszthatja mindkettőt, vagyis, minden p páratlan prímre

*) vagy nincs olyan n, amelyre 2^n ≢ -1 (mod p)

*) vagy van olyan n, amelyre 2^n ≡ -1, de, ekkor a 2 rendje páros, így 2^m ≢ 1, semmilyen páratlan m-re.

Ez tényleg egyszerű. Segítségül egy lemma:

Tekintsük a 2^n, n=0,1,2,.. számokat modulo p.

Lemma: ez egy 1,2,...,1,2,...,1,2,... alakú sorozat lesz, vagyis:

i) létezik olyan n>0, hogy 2^n ≡ 1 (mod p)

ii) az első két egyes közötti rész periodikusan ismétlődik.

A legkisebb ilyen o pozitív egészt, amelyre 2^o ≡ 1 (mod p), a 2 rendjének nevezzük. (Ez nyilván függ p-től.)

Lásd be, hogy ha a -1 az felbukkan valahol a sorozatban, mint p-szerinti maradék, akkor, ha a -1 első előfordulása u, akkor o=2*u, tehát 2^m ≢ 1, semmilyen páratlan m-re.