≡ 1 теңдікті

Тура іріктеу әдісі

Тура іріктеу әдісі — модульдік арифметикада кері элементті табудың ең қарапайым тәсілдерінің бірі. Әдістің мәні: a · a⁻¹ ≡ 1 (mod n) теңдігі орындалғанға дейін, x = 1, 2, …, n − 1 мәндерін кезекпен қойып тексеру.

Негізгі теңдеу

Кері элементті x = a⁻¹ (mod n) ретінде белгілесек, іздеу келесі шартқа келіп тіреледі:

a · x ≡ 1 (mod n)

Яғни x мәндерін біртіндеп тексеріп, a · x көбейтіндісінің n-ге бөлгендегі қалдығы 1-ге тең болатын жағдайды табамыз.

Мысал (n = 7, a = 5)

n = 7, a = 5 болсын. Онда x = a⁻¹ (mod 7) мәнін табу керек.

Теңдеу: a · x ≡ 1 (mod n), яғни 5 · x ≡ 1 (mod 7).

Тексерілетін мүмкін мәндер: x = 1, 2, 3, 4, 5, 6 (себебі n − 1 = 6).

Тура іріктеу нәтижесінде x = 3 табамыз, өйткені 5 · 3 = 15 және 15 ≡ 1 (mod 7). Демек, 5⁻¹ (mod 7) = 3.

Кесте 1

Тура іріктеу әдісінің мысалы

n = 7, a = 5

x	5·x	5·x (mod 7)
1	5	5
2	10	3
3	15	1
4	20	6
5	25	4
6	30	2

Кестеден 5·x (mod 7) = 1 болатын жалғыз мән x = 3 екені көрінеді.