Инверсия по модул

Класна стая на Google

Какво означава реципрочно?

Спомни си, че число, умножено по реципрочното си число, е равно на 1. От основната аритметика знаем, че:

Реципрочното число на A е 1/A, тъй като A * 1/A = 1 (т.е. реципрочното на 5 е 1/5)
Всички реални числа без 0 имат реципрочни
Умножаването на число по реципрочното на А е еквивалентно на деление на A (т.е. 10/5 е същото, като 10* 1/5)

Какво е модулно реципрочно?

В модулната аритметика нямаме оператор за деление. Имаме обаче модулни реципрочни.

Модулното реципрочно на A (mod C) е A^-1
(A * A^-1) ≡ 1 (mod C) или (A * A^-1) mod C = 1
Само числата, които са взаимно прости с C (числата, които имат еднакви прости делители с числото C) имат модулно реципрочно (mod C)

Как да намериш модулно реципрочно

Прост метод за намиране на модулно реципрочно на A (mod C) е:

стъпка 1. Изчисли A * B mod C за B стойностите от 0 до C-1

стъпка 2. Модулното реципрочно на A mod C е стойността B, която прави A * B mod C = 1

Забележи, че терминът B mod C може да приема само целочислена стойност от 0 до C-1, затова е излишно да проверяваме за по-голяма стойност за В.

Пример: A=3 C=7

Стъпка 1. Изчисли A * B mod C за стойности на B от 0 до C-1

3 * 0 ≡ 0 (mod 7)

3 * 1 ≡ 3 (mod 7)

3 * 2 ≡ 6 (mod 7)

3 * 3 ≡ 9 ≡ 2 (mod 7)

3 * 4 ≡ 12 ≡ 5 (mod 7)

3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ НАМЕРЕНО РЕЦИПРОЧНО!

3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

**Стъпка 2. Модулното реципрочно на A mod C е стойността на B, за която A * B mod C = 1**

5 е модулното реципрочно на 3 mod 7, тъй като 5*3 mod 7 = 1

Просто е!

Да направим още един пример, в който не намираме реципрочно.

Пример: A=2 C=6

**Стъпка 1. Изчисли A * B mod C за B стойностите от 0 до C-1**

2 * 0 ≡ 0 (mod 6)

2 * 1 ≡ 2 (mod 6)

2 * 2 ≡ 4 (mod 6)

2 * 3 ≡ 6 ≡ 0 (mod 6)

2 * 4 ≡ 8 ≡ 2 (mod 6)

2 * 5 ≡ 10 ≡ 4 (mod 6)

**Стъпка 2. Модулното реципрочно на A mod C е стойността на B, за която A * B mod C = 1**

Няма стойност на В, за която A * B mod C = 1. Следователно, A няма модулно реципрочно (mod 6).
Това е така, защото 2 не е взаимно просто с 6 (имат общ делител 2).

Този метод изглежда бавен...

Има много по-бърз метод за откриването на реципрочното на А (mod C), който ще обсъдим в следващите статии за Разширения алгоритъм на Евклид.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.