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

Phan Van Chung: Egy klasszikus probléma általánosítása

Megmutatjuk, hogy elég az (a,m) = 1 esettel foglalkozni. 1. TÉTEL. Legyenek a és m rögzített pozitív egészek, m>l. Az C2) x

2 = ax Cmod m) kongruencia minden megoldása visszavezethető C3) y

2 = a y Cmod m > alakú m

o|m. kongurenciák megoldására, ahol m

o> = 1, a

Q|a

i és BIZONYÍTÁS:Legyen Ca,m> = d és tegyük fel, hogy x egy megoldása C2)-nek. Ekkor a = da

t, ni = dm

t és Ca

i,m

j) = 1 és C2) alakja x

2 = da^x Cmod dm^, amiből d|x

2 . Ha d|x , akkor x = dy és C2)-be helyettesítve a d

2y

2 = da

tdy Cmod dm

f> adódik, amiből y

2 = a

ty Cmod m

Q>, mi ahol m = vi-—r- , es ez a ki vant C3) alak. o Cu,m

t) * Ha d f x, akkor d prímosztóit x is tartalmazza: e. f d = f] P. 1 és x = [] P. 1 x' i=l 1 ahol e. ^ 2 f. Cl = i.2,...,S> de van olyan j, hogy e . > f . • ) S Legyen d

o = f] P^ és x = d

Qx' ' tx3 az