다음 편 보기
나눗셈 정리
a는 정수, b는 자연수라고 하자. 이 때, a = bq + r (0 ≤ r < b) 를 만족하는 정수 q와 r은 유일하게 존재한다.
이 때, q를 '몫', r을 '나머지' 라고 하며 r = 0인 경우를 특히 'a가 b에 나누어떨어진다' 라고 표현한다.
나눗셈 정리는 정수론의 기본식 중 하나인데, 이 식에서 특히 많은 관심을 가지는 부분은 나머지인 r이다. 정수론에서는 나머지에 관심이 많다. 나머지는 무수히 많은 정수를 유한개로 분류해주기 때문이다. 간단한 예를 들어보자.
제곱수를 3으로 나눈 나머지가 2이다. 그 수는 무엇일까?
한번 10까지 제곱해서 값을 구해보자. 1의 제곱인 1은? 3으로 나눈 나머지가 1이다. 마찬가지로 4, 9, 16, 25, 36, ... 이 값들은 어떨까? 이상하게도 3으로 나눈 나머지가 0 또는 1이다. 2인 경우는 없다.
실제로 어떤 제곱수도 3으로 나눈 나머지는 2일 수 없다. 모든 자연수는 3으로 나눈 나머지가 0, 1, 2중 하나인데, 각각의 제곱수는 3으로 나눈 나머지가 0, 1, 1이 되기 때문이다.
숫자는 무한하다. 하지만 그 무수히 많은 숫자들도 3으로 나눈 나머지는 '0', '1', '2' 총 3개 중 하나이다. 이 덕분에 3종류의 숫자만 본다면 무수히 많은 제곱수중 3으로 나눈 나머지가 2인 수는 없다는 것을 쉽게 증명할 수 있다.
수많은 정수를 유한개로 분류했을 때 나오는 여러 특징들을 바탕으로 다양한 문제를 풀어낼 수 있으며 이 기반은 나눗셈 정리가 바탕이 된다.
1) 홀짝성
나머지의 분류를 활용하는 가장 대표적인 방식은 홀수와 짝수이다. 모든 정수는 홀수와 짝수 2가지로 분류된다. 홀수와 짝수라는 개념은 초등학생 때부터 배우며 이미 많이 풀어봤겠지만, 홀수와 짝수의 특징을 이용한 문제들은 수없이 많고 난이도도 상당하다. 앞으로 그러한 문제들을 많이 볼 것이기 때문에 충분히 익히고 넘어가자.
홀수와 짝수의 특징
- 짝수 ± 짝수, 홀수 ± 홀수는 반드시 짝수이다.
- 짝수 ± 홀수, 홀수 ± 짝수는 반드시 홀수이다.
- 짝수 × 홀수, 짝수 × 짝수는 반드시 짝수이다.
- 홀수 × 홀수는 반드시 홀수이다.
예제 1.1 (난이도 ☆) : 축구팀 5팀이 아무렇게나 시합을 했을 때, 모든 팀이 홀수번 시합을 할 수 있는지 판단하세요.
경기 횟수를 n회라고 하자. 그러면 경기마다 두 팀이 붙으므로 5팀이 각각 시합을 한 횟수의 총합은 2n이 된다.
축구팀 5팀이 모두 홀수번 시합을 했다면, 시합을 한 횟수의 총합은 (홀수 + 홀수 + 홀수 + 홀수 + 홀수) = 홀수여야 한다. 이는 짝수인 2n이 되지 못하므로 모순이 생긴다.
따라서 5명 모든 팀이 홀수번 시합은 불가능하다.
예제 1.2 (난이도 ☆) : 0과 1만으로 이루어진 수열이 있습니다. 모든 숫자 사이에 +혹은 -를 넣어서 식을 만들려고 하는데, 이 식의 절댓값이 최소가 되도록 하고 싶습니다. 주어진 수열에서 최솟값을 구하세요.
a) 0 1 1 0 1
b) 1 1 0 1 1
c) 일반적인 모든 수열
- Codeforces Polynomial Round 2022 A 각색
a) 직접 숫자들 사이에 +와 -를 넣어보자. 이상하게도 -1과 1은 만들 수 있지만, 0은 만들지 못한다. (답 : 1)
b) 이 수열에서는 1 - 1 + 0 + 1 - 1 등의 방법으로 0을 만들 수 있다. (답 : 0)
c) 앞선 예제들을 바탕으로 생각해 보면, 1이 홀수개 있는 수열은 어떻게 더하고 빼도 홀수가 되므로 최솟값이 1이 된다. 1이 짝수개 있는 수열은 항상 짝수가 되므로 최솟값이 0이 된다.
특히 코드포스에서는 홀짝성을 이용하는 문제가 굉장히 많다. 이번에는 A번의 문제로 가지고 왔지만 이 문제는 홀짝성만 관찰해도 문제를 풀 수 있어서 그렇고, 난이도가 높은 문제에서도 기본 중의 기본으로 활용되는 경우가 널렸다. 예제 1.2는 홀짝성의 일반화된 버전이기도 하므로 충분히 이해가 되지 않았다면 몇번이고 곱씹고 넘어가는 것이 좋다.
연습문제 (가능하면 난이도 순으로 배열했습니다.)
Codeforces Deltix Round, Autumn 2021 A
2) 나머지의 성질 일반화
홀짝성은 나머지의 성질 중 특별한 경우이다. 2로 나눈 나머지에 대해서 설명할때 홀짝성이라는 단어를 붙이곤 한다. 하지만 언뜻 보면 홀짝성에서만 쓰일 것 같더라도 어느 숫자로 나눈 나머지에서든 동일한 성질이 보일 수 있다.
특히 비둘기집을 활용하는 경우가 흔하다
예제 1.3 (난이도 ☆) : 서로 다른 자연수가 5개가 있을 때, 항상 두 수의 차이가 4의 배수가 되도록 두 개의 숫자를 고를 수 있음을 보이시오.
4로 나눈 나머지는 0, 1, 2, 3중 하나이다. 서로 다른 자연수가 5개 있다면 반드시 4로 나눈 나머지가 같은 숫자가 있게 되며, 그 두 숫자의 차이를 구하면 반드시 두 수의 차이는 4의 배수가 된다.
따라서 5개의 자연수가 있다면 항상 차이가 4의 배수가 되도록 두 개의 숫자를 고를 수 있다.
예제 1.4 (난이도 ★☆) : 자연수로 이루어진 수열 a가 있습니다. 수열 a의 모든 원소에 대해서 다음을 만족하는 자연수 x가 있는지 알아보고 싶습니다: 주어진 수열에서 그러한 x가 있는지 없는지 판단하세요.
- 수열 a의 아무 자연수 a[i], a[j] 두개를 골랐을 때, 항상 gcd(a[i] + x, a[j] + x) = 1을 만족한다.
a) 2 4 8
b) 2 3 4 5
c) 3 5 7 9 11 13
d) 일반적인 모든 수열
- Codeforces Good Bye 2022 C 각색
a) 직접 x를 넣어보면, x = 3일 때 5, 7, 11이 되어 아무 자연수를 골라도 항상 최대공약수는 1이 됩니다. (답 : 있다)
b) 직접 x를 넣어보면, x가 짝수일 때에는 2 + x, 4 + x가 반드시 짝수여서 2의 배수이고, x가 홀수일 때에는 3 + x, 5 + x가 반드시 짝수여서 2의 배수임을 알 수 있다. (답 : 없다)
c) 이 수열에서는 홀짝성만 따지면 x가 짝수일 때에는 모든 수가 홀수이므로 충분히 가능해 보인다. 하지만 실제로는 그렇지 않다. 3으로 나눈 나머지가 0, 1, 2인 숫자가 각각 2개씩 있기 때문이다. x가 무슨 값이 되더라도 더한 값들의 3으로 나눈 나머지가 0인 개수는 2개이며 이 두개의 숫자를 고르면 반드시 최대공약수가 3이 된다. (답 : 없다)
d) 앞선 예제들을 바탕으로 생각해 보면, 아무 정수 a에 대해 a로 나눈 나머지 0, 1, 2, 3, ..., a-1인 그룹마다 전부 수가 2개 이상 있다면 x가 존재하지 않는다.
이에 대한 엄밀한 증명은 중국인의 나머지 정리를 바탕으로 하지만 여기서는 넘어가겠다.
위에 문제들을 풀어보면, 홀짝성에서만 적용될 것 처럼 보이던 특징들이 고민해보면 일반화되는 경우가 상당히 많다. 홀짝성이 문제의 접근에서 중요한 것으로 보일 때에는 한번 쯤 이런 생각도 해보자. '정말 2로 나눴을때만 생기는 특징이야?'
연습문제
백준 2839 : 설탕 배달
3) 합동
합동은 정수론에서 굉장히 중요한 요소이다. 우선 간단한 문제를 하나 풀어보자.
2의 99999999999제곱을 3으로 나눈 나머지는 몇일까?
이 문제의 답은 무엇일까? 직접 하나씩 제곱을 해보면 특징이 보인다. 2의 1제곱은 3으로 나눈 나머지가 2, 2제곱은 1, 3제곱은 2, 4제곱은 1, ...
2의 홀수제곱은 3으로 나눈 나머지가 2이고, 2의 짝수제곱은 3으로 나눈 나머지가 1이다. 따라서 위 문제의 답은 2일 것이라고 추론해볼 수 있다. (수학적 귀납법 등을 이용하면 증명도 가능하다.)
이 문제는 쉽게 풀었다. 왜냐하면 특징이 너무 뚜렷했다. 그렇다면 3의 99999999999제곱을 100으로 나눈 나머지는 어떻게 구할까? 그 때도 비슷한 방식으로 풀 수 있을까?.. 쉽지 않을 것이다.
이런 다양한 식에서 숫자의 나머지를 어떻게 빠르게 구할 수 있을지의 고민 중에 도입된 개념이 바로 합동이라는 개념이다.
정수론에서는 중요도가 매우 높고 나머지를 구하기 위해 특히 중요하지만, ps에서는 컴퓨터를 활용하기 때문에 페르마의 소정리, 오일러 정리, 중국인의 나머지 정리 등등 나머지를 빠르게 구하는 기술들은 ps에서는 엄청나게 중요한 분야는 아니다. ps에서는 정수론의 지식 대신 알고리즘을 활용해 어렵지 않게 나머지를 구할 수 있다. ps에서 나머지를 구하라는 대부분의 문제들은 순전히 구하려는 숫자가 long long int (2^63)를 넘어가서 그런 경우가 많다. 따라서 합동식의 개념만 충분히 이해하고 넘어가자.
예제 1.5 : 추가예정
추가예정
예제 1.6 (난이도 ★) : i = 1 ~ n에 대해 ∑i^2 의 값에 2022를 곱한 값을 (1e9 + 7)로 나눈 나머지를 구하고자 합니다. 이 값을 구하는데 long long (8e18) 범위를 초과할 수 없으며 총 1억회 이상의 덧셈, 뺄셈, 곱셈, 나머지 연산을 할 수 없습니다. 다음 n에서 어떻게 연산하는 것이 좋을지 판단하세요.
a) n ≤ 1e5
b) n ≤ 1e9
- Codeforces Round #841 B 각색
a) n이 1e5 이하인 경우, 1부터 n까지 i^2을 전부 더하고 2022을 곱한 뒤 (1e9 + 7)로 나눈 나머지를 구하더라도 long long 범위를 초과하지 않으며 연산 횟수도 초과하지 않습니다. 전부 더하는 방식으로 답을 구할 수 있습니다.
b) 추가 예정
합동식의 나눗셈은 특정 상황에서만 만족한다는 점을 주의하자. 물론 나중에 나올 잉여역수를 이용하면 나눗셈도 할 수 있다. 이에 대한 내용은 페르마 소정리 파트때 설명하겠다.
연습문제
추가 예정
댓글로 질문, 피드백 언제나 환영합니다 :)