[Kotlin] Algorithm - The remaining operational distribution law
Kotlin2023-10-17 18:30 (KST)
Modular Arithmetic
Operation to find the remainder by dividing one number by another
In general, dividing the two integers (A, B) yields the quotient (Q) and the remainder (R).
A / B = Q The rest R
The remaining operation is an operation that obtains only the remainder from the divided value, and is expressed as follows using a modular operator.
A mod B = R
At this time, A modular B is said to be equal to R. (B is a module)
In programming languages, % is used to represent A % B
.
Understanding as a Clock
Increasing A by 1 and dividing by B repeats the remaining values from 0
to B-1
.
This is similar to the process of turning the hour hand on a clock. (1 mod 12 = 1, 2 mod 12 = 2, 11 mod 12 = 11, 12 mod 12 = 0, 13 mod 12 = 1)
- Analog clocks have time from 1 to 12 written in the circle. Here, if you change 12 to 0, the module B becomes a circle of 12.
- If A is 3, start at 0 and turn the hour hand by 3. (Clockwise direction of positive side, counterclockwise direction of negative side)
- The number at the stopping point does harm. (3 mod 12 = 3)
![modulo.png](https://file.dico.me/2023/10/20231010143824_000.png)
- Example of negative calculation: -3 mod 5 = -(3 mod 5) + 5 = -3 + 5 = 2
Congruent
If the results are the same when the two numbers A and B are modularized by C, A and B are called joint relationships for module C.
If A mod C = B mod C
is established, it can be expressed as the joint relationship A ≡ B mod C
.
Equivalent relationship
Concept of dividing pie (circle) into equal sized pieces through modular operation
Decide how to divide the pie into pieces (equivalents).
When the pie is divided by module C, the numbers in the same piece (equivalence) have an equivalent relationship.
The difference between any two values in a piece is a multiple of C.
The pie pieces have a joint relationship to module C, which forms an equivalent relationship.
![modulo_01.png](https://file.dico.me/2023/10/20231010152351_000.png)
Characteristic
- Reflexivity: A is related to A.
A ≡ A mod C
- Symmetry: If A is related to B, B is also related to A.
A ≡ B mod C
이면B ≡ A mod C
- Transitivity: If A is related to B, and B and D are related, A and D are also related. If
A ≡ B mod C
andB = D mod C
, thenA ≡ D mod C
Law of distribution
a mathematical law that describes the relationship between addition or subtraction and the rest of the operation
When the two numbers A and B are divided by C, the quotient and the remainder are expressed as follows.
A = Q1 * C + R1
B = Q2 * C + R2
Addition/Division/Multiplication Distribution Law Properties
(A ± B) mod C = (A mod C ± B mod C) mod C
(A × B) mod C = (A mod C × B mod C) mod C
- Proof
LHS = the left side of the equation
RHS = the right side of the equation
LHS = (A ± B) mod C
= (C(Q1 ± Q2) ± R1 ± R2) mod C // The remainder of the operation is zero
= (R1 ± R2) mod C
RHS = (A mod C ± B mod C) mod C
= (R1 ± R2) mod C
LHS = RHS = (R1 ± R2) mod C
power characteristic property
A^B mod C = ((A mod C)^B) mod C
- Depending on the value of B, overflow may occur, so split conquest should be used.
Reference
https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic
https://gosamy.tistory.com/75
https://dev-min.tistory.com/1
https://developer-mac.tistory.com/84
https://codingram.tistory.com/26
https://velog.io/@yyeonggg/모듈러-연산Modular-Arithmetic
https://velog.io/@gidskql6671/나머지Modulo-연산-분배법칙
https://gliver.tistory.com/5
https://www.crocus.co.kr/1231
https://sskl660.tistory.com/75
https://velog.io/@sw801733/나머지-연산-분배법칙-모듈러-연산
Previous Article
[Kotlin] Algorithm - Recursive
Kotlin