Lower and upper bounds for solutions of the congruence xm ≡ a(mod n)

• Autorzy: Zakarczemny M.

Identyfikatory

DOI

10.4467/2353737XCT.17.194.7423

Warianty tytułu

PL

Dolne oszacowanie na największe i górne oszacowanie na najmniejsze rozwiązanie kongruencji xm ≡ a(mod n)

• Języki publikacji: EN

Abstrakty

EN

Let n, m be natural numbers with n ≥ 2. We say that an integer a, (a, n) = 1, is the m-th power residue modulo n if there exists an integer x such that x^m ≡ a(mod n). Let C(n) denote the multiplicative group consisting of the residues modulo n which are relatively prime to n. Let s(n, m, a) be the smallest solution of the congruence x^m ≡ a(mod n) in the set C(n). Let t(n, m, a) be the largest solution of the congruence x^m ≡ a(mod n) in the set C(n). We will give an upper bound for s(n, m, a) and a lower bound for t(n, m, a).

PL

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 x^m ≡ 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 x^m ≡ a(mod n) w zbiorze C(n). Oznaczmy przez t(n, m, a) największe rozwiązanie równania x^m ≡ 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

EN

smallest solution; largest solution; upper bound; lower bound; congruence relation; residue class; n-th degree equation

PL

najmniejsze rozwiązanie; największe rozwiązanie; górne oszacowanie; dolne oszacowanie; kongruencja; klasa reszt; równanie wielomianowe

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Technical Transactions
• Rocznik: 2017
• Tom: Vol. 11(114)
• Strony: 161--168
• Opis fizyczny: Bibliogr. 2 poz., wz.

Twórcy

autor

Zakarczemny M.

• Institut of Matchematics, Faculty of Physis, Mathematics and Computer Science, Cracow University of Technology

Bibliografia

• [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.

Uwagi

EN

Section "Mathematics"

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)