프로베니우스 문제

수론에서, 프로베니우스 문제(영어: Frobenius problem)는 주어진 양의 정수들을 더하여 만들 수 없는 가장 큰 양의 정수를 구하는 문제이다. 특정 액면가의 동전들로 나타낼 수 없는 가장 큰 액수를 찾는 것에 비유할 수 있으므로, 동전 문제(영어: coin problem)라고도 부른다. 예를 들어, 3원짜리 동전과 5원 동전을 모아 만들 수 없는 최대 액수는 7원이다. 만약 모든 액면가가 어떤 1보다 큰 정수의 배수라면, 만들 수 있는 액수들 역시 이 정수의 배수이므로, 만들 수 없는 액수가 임의로 크게 존재하게 된다. 따라서, 만들 수 없는 최대 액수가 존재하려면, 액면가들의 최대 공약수가 1이어야 한다.

정의

이 글에서, $\mathbb {N}$ 은 음이 아닌 정수의 집합, $\mathbb {Z} ^{+}$ 는 양의 정수의 집합이다.

일련의 양의 정수 $a_{1},\dots ,a_{n}\in \mathbb {Z} ^{+}$ 가 주어졌고, 그 최대 공약수가 1이라고 하자 ( $\gcd\{a_{1},\dots ,a_{n}\}=1$ ). 그렇다면, $a_{1},\dots ,a_{n}$ 의 프로베니우스 수

g(a_{1},\dots ,a_{n})=\max(\mathbb {Z} ^{+}\setminus (a_{1}\mathbb {N} +\cdots a_{n}\mathbb {N} ))\in \mathbb {Z} ^{+}

는 방정식

a_{1}x_{1}+\cdots +a_{n}x_{n}=c

의 음이 아닌 정수해 $x_{1},\dots ,x_{n}\in \mathbb {N}$ 가 존재하지 않게 되는 양의 정수 $c\in \mathbb {Z} ^{+}$ 가운데 가장 큰 하나이다. 슈어 정리에 따라, 만약 $a_{1},\dots ,a_{n}\geq 2$ 라면, 이는 항상 존재한다.

프로베니우스 수를 구하는 문제를 프로베니우스 문제라고 한다.

성질

존재

$\gcd\{a_{1},\dots ,a_{n}\}=1$ 인 임의의 양의 정수 $a_{1},\dots ,a_{n}\in \mathbb {Z} ^{+}$ 및 양의 정수 $c\in \mathbb {Z} ^{+}$ 에 대하여,

A(a_{1},\dots ,a_{n};c)=|\{(x_{1},\dots ,x_{n})\in \mathbb {N} ^{n}\colon a_{1}x_{1}+\cdots +a_{n}x_{n}=c\}|

가 이들을 계수로 하는 방정식의 음이 아닌 정수해의 개수라고 하자. 그렇다면 이는 다음과 같이 점근적으로 근사할 수 있다.^[1]^{:301, 정리 11.2.1}

A(a_{1},\dots ,a_{n};c)\approx {\frac {c^{n-1}}{(n-1)!a_{1}\cdots a_{n}}}\qquad (c\to \infty )

이를 슈어 정리(영어: Schur’s theorem)라고 한다. 특히, $c$ 가 충분히 크면 방정식의 음이 아닌 정수해가 존재한다. 따라서, 만약 모든 $a_{i}$ 가 2 이상이라면 (1은 해가 아니므로) $g(a_{1},\dots ,a_{n})$ 가 존재한다.