Ако виждаш това съобщение, значи уебсайтът ни има проблем със зареждането на външни ресурси.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Основно съдържание

Събиране и изважане по модул

Да разгледаме свойството събиране в модулната аритметика:

(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
ДСУ = (A mod C + B mod C) mod C
  ДСУ = (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
От Теоремата за частно и остатък можем да запишем А и В като:
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
LHS = (A + B) 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

Модулно изваждане

Доказателството за модулното изваждане е много подобно

(A - B) mod C = (A mod C - B mod C) mod C

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

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