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

- 9 m felborítható két relativ prim tényező szorzatára; a tényezők sorrendjét is figyelembe véve. A felbontás a következőképpen történhet: u az m-nek r primtényező

je közül tartalmazhat 0,l,2,...,r -et, amig v rendre: r, r-1, • 2, 1, 0 -át. Ezért a megoldások száma (5) + (D * •• + IfJ = Ezzel bizonyítottuk a következő tételt: a a a 4. TÉTEL. Ha m = P/ P„

z ... P r az m szám kanonikus 12 r előállítása, akkor az x

2 ~ nx Cmod mi kongruenciának 2

r inkongruens megoldása van, feltéve, hogy Ca,mi = 1. Most vizsgáljuk azt az esetet, amikor a modulus m-nek k-adik hatványa, vagyis 2 V Cói x s ax Cmod mi, ahol Ca,mi = 1. Mivel m

v -ra ugyanazok a fej tételek teljesülnek mind m-re és prímtényezők száma is megegyezik, ezért a 2. és 3. Tétel segítségével Cói is megoldható és az inkongruens megoldások száma a Tétel miatt itt is 2

r. Megkönnyíti azonban Cói numerikus megoldását a következő tétel, ami lényegében a 3. Tétel átfogalmazása. 5. TÉTEL. Ha Ca, ini = 1, m = u'v; Cu,vi = 1 és y

k = u'^

v:>,vk_

1Cmod m

ki, k « , akkor x

k = ay^ Cmod m i megoldása az C6i kongruenciának. Lássunk egy példát az 5. Tételre. I.egyen például ••• = 10 2 V es a = 1, vagyis keressük az x s x Cmod 10 i kongruencia megoldásait, azaz azokat a k jegyű pozitív egész számokat, melyek négyzetének utolsó k helyen álló számjegyei megegyeznek az eredeti számmal. Például u=5, v=2 esetén