백준 10430 증명

10430번: 나머지 (acmicpc.net)

A=Q1*C+R1
B=Q2*C+R2

라고 정의하면 다음과 같다.

A%C=R1
B%C=R2

(A+B)%C
=(Q1*C+R1+Q2*C+R2)%C
=(C(Q1+Q2)+R1+R2)%C
=(R1+R2)%C
=((A%C)+(B%C))%C

(A*B)%C
=((Q1*C+R1)*(Q2*C+R2))%C
=(Q1*Q2*C^2+(R1*Q2+R2*Q1)C+R1*R2)%C
=(R1*R2)%C
=((A%C)*(B%C))%C

두 번째는 그림으로도 곱셈 공식 증명하듯 증명 가능함.

C가 포함되어 있으면 다 사라지니까... 결국엔 R1*R2만 남는 거죠.