Основно съдържание
Курс: Компютърни науки > Раздел 2
Урок 5: Модулна аритметика- Какво е модулна аритметика?
- Оператор за деление с остатък
- Предизвикателство с деление с остатък
- Сравнение по модул
- Съгласувана връзка
- Отношения на еквивалентност
- Теорема за остатъка от делене
- Събиране и изважане по модул
- Събиране по модул
- Модулно предизвикателство (събиране и изваждане)
- Умножение по модул
- Умножение по модул
- Степенуване по модул
- Бързо степенуване по модул
- Бързо степенуване по модул
- Инверсия по модул
- Алгоритъм на Евклид
© 2024 Khan AcademyУсловия за ползванеДекларация за поверителностПолитика за Бисквитки
Събиране и изважане по модул
Да разгледаме свойството събиране в модулната аритметика:
(A + B) mod C = (A mod C + B mod C) mod C
Пример:
Нека A=14, B=17, C=5
Нека проверим: (A + B) mod C = (A mod C + B mod C) mod C
ЛСУ = Лява Страна на Уравнението
ДСУ = Дясна Страна на Уравнението
ЛСУ = Лява Страна на Уравнението
ДСУ = Дясна Страна на Уравнението
ЛСУ = (A + B) mod C
ЛСУ = (14 + 17) mod 5
ЛСУ = 31 mod 5
ЛСУ = 1
ЛСУ = (14 + 17) mod 5
ЛСУ = 31 mod 5
ЛСУ = 1
ДСУ = (A mod C + B mod C) mod C
ДСУ = (14 mod 5 + 17 mod 5) mod 5
ДСУ = (4 + 2) mod 5
ДСУ = 1
ДСУ = (14 mod 5 + 17 mod 5) mod 5
ДСУ = (4 + 2) mod 5
ДСУ = 1
ЛСУ = ДСУ = 1
Интуицията зад модулното събиране
Наблюдавай фигурата по-долу. Ако искаме да изчислим 12+9 mod 7, можем лесно да минем през модулния цикъл за последователност от 12+9 стъпки по часовниковата стрелка (както е показано в долния ляв кръг).
Можем да минем напряко, като забележим, че на всеки 7 стъпки завършваме на същата позиция на модулния кръг. Тези пълни цикли около модулния кръг не допринасят за крайната ни позиция. Игнорираме тези пълни цикли, като изчисляваме всяко число mod 7 (както е показано на горните два модулни кръга). Това ще ни даде броя на стъпките по часовниковата стрелка по отношение на 0-та, които допринасят за крайните позиции около модулния кръг.
Сега само трябва да минем през кръга по часовниковата стрелка с общия брой стъпки, които допринасят за крайната позиция на всяко число (както е показано на десния долен модулен кръг). Като цяло този метод се прилага към две цели числа и всеки модулен кръг.
Доказателство за модулно събиране
Ще докажем, че (A + B) mod C = (A mod C + B mod C) mod C
Трябва да покажем, че LHS=RHS
Трябва да покажем, че LHS=RHS
От Теоремата за частно и остатък можем да запишем А и В като:
A = C * Q1 + R1, където 0 ≤ R1 < C and Q1 е някакво цяло число. A mod C = R1
B = C * Q2 + R2, където 0 ≤ R2 < C и Q2 е цяло число. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
B = C * Q2 + R2, където 0 ≤ R2 < C и Q2 е цяло число. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
LHS = (A + B) mod C
LHS = (C * (Q1 + Q2) + R1+ R2) mod C
Можем да елиминираме множителите на С, като вземем mod C
LHS = (R1 + R2) mod C
LHS = (C * (Q1 + Q2) + R1+ R2) mod C
Можем да елиминираме множителите на С, като вземем mod C
LHS = (R1 + R2) mod C
ДСУ = (A mod C + B mod C) mod C
ДСУ = (R1 + R2) mod C
ДСУ = (R1 + R2) mod C
ЛСУ=ДСУ= (R1 + R2) mod C
Модулно изваждане
Доказателството за модулното изваждане е много подобно
(A - B) mod C = (A mod C - B mod C) mod C
Искаш ли да се присъединиш към разговора?
Все още няма публикации.