Lower and upper bounds for solutions of the congruence x^m ≡ a(mod n)

Maciej Zakarczemny

Abstrakt

Niech n, m będą liczbami naturalnymi, takimi że n ≥ 2. Powiemy, że liczba całkowita a, (a, n) = 1, jest m-tą resztą kwadratową modulo n, jeśli istnieje liczba całkowita x, taka że xm ≡ a(mod n). Niech C(n) będzie grupą multiplikatywną zawierającą reszty modulo n, względnie pierwsze z n. Oznaczmy przez s(n, m, a) najmniejsze rozwiązanie równania xm ≡ a(mod n) w zbiorze C(n). Oznaczmy przez t(n, m, a) największe rozwiązanie równania xm ≡ a(mod n) w zbiorze C(n). Podamy górne oszacowanie na s(n, m, a) oraz dolne na t(n, m, a).

Słowa kluczowe: najmniejsze rozwiązanie, największe rozwiązanie, górne oszacowanie, dolne oszacowanie, kongruencja, klasa reszt, równanie wielomianowe
References

[1] Nathanson M.B., Elementary Methods in Number Theory, Vol. 195, GTM, Springer, New York 2000.


[2] Norton K.K., k-th coset representatives modulo n, Acta Arithmetica, XV, 1969, 161-179.