[JAVA]모듈러 연산

개념

모듈러 연산이란 한 숫자를 다른 숫자로 나누었을 때 생기는 나머지를 구하는 연산이다.

코딩에서는 "%" 기호를 사용한다. ex) 5 % 3 = 2

 

쉬운 개념이지만, 모듈러 연산에는 생소할 수도 있는 몇 가지 성질이 있다.

위 식이 성립한다는 것인데, 간단하게 증명을 해 보겠다.

증명은 다 같은 원리로 진행되기 때문에, 첫 번째 성질만 증명하겠다.

 

증명

A를 C로 나누었을 때의 몫을 Qa, 나머지를 Ra라 하고,

B를 C로 나누었을 때의 몫을 Qb, 나머지를 Rb라 하면 아래와 같이 식을 세울 수 있다.

위 식을 정리하면 아래와 같고, 

Ra는 A를 C로 나눈 나머지, Rb는 B를 C로 나눈 나머지 이므로, 아래와 같이 표현 가능하다.

따라서 첫 번째 성질이 성립한다는 것을 알 수 있다.

 

예시 코드

백준 알고리즘 10430번 : 나머지 문제를 풀면, 실제로 위 성질이 같다는 것을 코드로도 알 수 있다.

BufferedReader 클래스와 StringBuilder 클래스를 이용하여 풀어 보았다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int result1 = (A + B) % C;
        int result2 = ((A % C) + (B % C)) % C;
        int result3 = (A * B) % C;
        int result4 = ((A % C) * (B % C)) % C;

        sb.append(result1).append("\n");
        sb.append(result2).append("\n");
        sb.append(result3).append("\n");
        sb.append(result4);
        System.out.println(sb);
    }
}

 

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
제가 이해한 내용을 간단히 요약하여 기록해 두고, 기억이 나지 않을 때마다 찾아보려는 목적으로 작성하는 글입니다.
따라서 설명이 부족할 수 있으니 양해 부탁드리고, 궁금한 부분이 있으시면 자유롭게 댓글 남겨주세요!