프로베니우스 문제

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

 정의 
이 글에서, 은 음이 아닌 정수의 집합, 는 양의 정수의 집합이다.

일련의 양의 정수 가 주어졌고, 그 최대 공약수가 1이라고 하자 (). 그렇다면, 의 프로베니우스 수

는 방정식

의 음이 아닌 정수해 가 존재하지 않게 되는 양의 정수  가운데 가장 큰 하나이다. 슈어 정리에 따라, 만약 라면, 이는 항상 존재한다.

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

 성질 
 존재 
인 임의의 양의 정수  및 양의 정수 에 대하여,

가 이들을 계수로 하는 방정식의 음이 아닌 정수해의 개수라고 하자. 그렇다면 이는 다음과 같이 점근적으로 근사할 수 있다.

이를 슈어 정리()라고 한다. 특히, 가 충분히 크면 방정식의 음이 아닌 정수해가 존재한다. 따라서, 만약 모든 가 2 이상이라면 (1은 해가 아니므로) 가 존재한다.

의 정의에 따라, 는 유리 함수

의 멱급수 전개 속 의 계수이다.

가 다항식 의 서로 다른 근이고,

가 그 중복도라고 하자. 이므로, 이다. 그렇다면, 를 다음과 같이 부분 분수 분해할 수 있다.

이제, 각 부분 분수

의 멱급수 전개에서, 의 계수는 이항 정리에 따라

이므로,

이다. 그런데 이므로, 의 멱급수 전개 속 의 계수 는

을 만족시킨다.

마지막으로, 의 부분 분수 분해 및 에 따라

이다.

 계산 복잡도 
프로베니우스 수를 구하는 문제는 NP-난해 문제이다. 그러나 일부 특수한 경우에는 간단한 알고리즘들이 존재한다.

 예 
두 양의 서로소 정수 의 프로베니우스 수는 다음과 같다 ().

 참고 문헌 

 외부 링크 






분류:디오판토스 방정식