Modulo distributive property (분배 법칙)

내가 알던 Modulo = remainder 구하는 operator

• ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
• ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
• ( a – b) % c = ( ( a % c ) – ( b % c ) + c ) % c

 

 

🤔 문제점) 종만북에서는 modular subtraction을

( a – b) % c = ( ( a % c ) – ( b % c ) + c ) % c 로 정의함.

c를 더해서 음수가 되는 것을 방지 (참고)

 

근데 아래 source에서는 ( a – b) % c = ( ( a % c ) – ( b % c ) ) % c 로 정의하네? 댓글에 달린 proof를 봐도 문제 없는 것 같고..

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction

 

A) 결론 : 수학적으로 negative modular arithmetic 정의 가능하나, CS에선 되도록이면 modulus (위 식에서 c) 더해줘서 양수로 유지하자 (언어별로 구현이 다르므로 혼란 야기함)

 

❓ 수학에서 정의하는 modulo와 CS에서 쓰는 modulo가 다른가?

 

negative remainder → mod 더해서 positive remainder로 바꿔야

5 % (-3) 생각

Case 1) 5 = (-3)*2 + 1 → 5 % (-3) = 1

Case 2) 5 = (-3)*1 + (-2) → 5 % (-3) = -2

결과가 2개가 나온다? => Case 2는 negative remainder

https://math.stackexchange.com/questions/2179579/how-can-i-find-a-mod-with-negative-number

 

 

👉🏻 CS에서 modulo는 remainder처럼 정의되고, negative modulo는 programming-language specific 하므로 양수로 유지해주는게 마음 편한 듯.

https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers

Modulo operation with negative numbers

 

정의를 보자.

https://en.wikipedia.org/wiki/Modulo_operation

Modulo operation - Wikipedia

In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation).

...

When exactly one of a or n is negative, the naive definition breaks down, and programming languages differ in how these values are defined.