[Kotlin] Algorithm - The remaining operational distribution law

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)

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.
2. If A is 3, start at 0 and turn the hour hand by 3. (Clockwise direction of positive side, counterclockwise direction of negative side)
3. The number at the stopping point does harm. (3 mod 12 = 3)

• 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.

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 and B = D mod C, then A ≡ 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/나머지-연산-분배법칙-모듈러-연산

[Kotlin] Algorithm - Recursive - Dico

알고리즘 재귀(Recursive)를 코틀린으로 설명

dico.me

[Kotlin] Algorithm - Dynamic Programming (DP) - Dico

알고리즘 동적계획법 개념 정리

dico.me