Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1993. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 21)

Pham Van Chung: Egy klasszikus probléma általánosítása. II

Mivel (d,m

1) = 1 folytán <p(m) = (pid)-^^), így a bal oldal tovább alakítható, felhasználva az Euler-Fermat tételt (.x

xd)

n l = (x

ld)'**^\x

ldy1 = (jc

1ú?)

r_

1(mod m,). Tehát a fenti kongruencia a következőre redukálódik: (x

xd)

r~

l = ö (mod Wj). Itt d-vel szorozva mindkét oldalt és a modulust is, majd x

xgyel szorozva a két oldalt és , ill. rn^d helyébe visszaírva *

0-t, ill. m-et, az kongruenciát kapjuk, mivel igazoltuk a tételt az egyik irányban. Ha x

0 megoldása a (3) kongruenciának, akkor az előzőekhez hasonlóan látható be, hogy megoldása a (2)-nek is. Ezután bebizonyítjuk a következő tételt, amely bizonyos esetekben egyszerűsítheti a számításokat 2. Tétel: Ha (n - 1, <p{m)) = 1, akkor az (4) x

n = Jt (mod m) kongruencia ekvivalens. Bizonyítás: Tegyük fel, hogy x

0 megoldása a (4) kongruenciának. Mivel (n - \,(p(m)) = 1, léteznek olyan v és u természetes számok, amelyekre Mint az előző tétel bizonyításában, ha (x

0,m) = d és a felhasznált jelöléseket tartva (4) átalakítható Xq = ax

Q (mod m) x

2 = x (mod m) (6) v-(n - 1) = u-(p(m) +1. (7) (V) =! (

mod m\) 56