弗羅貝尼烏斯問題

弗羅貝尼烏斯問題(Frobenius problem)是關於一次不定方程的一個著名問題。設a₁，a₂，…，a_n為整數，它們的最大公約數為1，求不能表示成a₁x₁+a₂x₂+…+a_nx_n的最大整數，其中x₁，x₂，…，x_n為任意非負整數。這個問題稱為一次不定方程的弗羅貝尼烏斯(Frobenius)問題，也稱為換錢問題。

基本介紹

• 中文名：弗羅貝尼烏斯問題
• 外文名：Frobenius problem
• 所屬學科：數學
• 所屬問題：初等數論(不定方程)
• 簡介：關於一次不定方程的一個著名問題
• 別稱：換錢問題

基本介紹

設n≥2，a₁，a₂，…，a_n都是正整數，(a₁，a₂，…，a_n)=1，再設x_i≥0 (i=1，2，…，n)的線性型a₁x₁+a₂x₂+…+a_nx_n不能表出的最大整數為g(a₁，a₂，…，a_n)，即對大於它的任意整數m，存在整數x_i≥0 (i=1，2，…，n)，使a₁x₁+a₂x₂+…+a_nx_n=m，研究g(a₁，a₂，…，a_n)的存在性及其解法，就是關於丟番圖方程a₁x₁+a₂x₂+…+a_nx_n=c的弗羅貝尼烏斯問題。

該問題不僅在不定方程理論上有重要意義，還在規劃論、計算技術、合理下料、合理派工等方面都有實際套用。對此問題，目前研究的結果為：當n=2時，g(a₁，a₂)=a₁a₂-a₁-a₂；在n≥3時，關於g(a₁，a₂，…，a_n)尚無一般表示式，但在多種情形已有些不同的方法。例如，當a₃>a₁a₂/(a₁，a₂)²-(a₁+a₂)/(a₁+a₂)時，可算得g(a₁，a₂，a₃)=a₁a₂/(a₁，a₂)+a₃(a₁，a₂)-a₁-a₂-a₃，由於g(a₁，a₂，a₃)=g(a₂，a₃，a₁)=g(a₃，a₁，a₂)，上麵條件及結果中的a₁，a₂，a₃可以輪換，對於一般的n有

其中d_i=(a₁，a₂，…，a_i) (i=2，3，…，n)，d₁=a₁(d_n=1)。

相關證明

n=2時，易知所求的數為a₁a₂-a₁-a_2，證明如下：

首先，設m>a₁a₂-a₁-a_2，方程

的全部解可寫成

其中是(1)的任一組整數解，t為任意整數。可以假定0≤x₂<a₁ (否則將x₂加上或減去若干個a₁)，這時

因此，x₁≥0，即m=a₁x₁+a₂x₂，x₁，x₂都是非負整數。

另一方面，若

其中x₁，x₂為非負整數，則

從而。

因為，所以從而

矛盾。

所以，a₁a₂-a₁-a₂是不能表示成a₁x₁+a₂x₂(x₁，x₂為非負整數)的最大整數。

n=3的情況，直至1978年才由E.S.Selmer與Ö.Beyer利用連分數給出有顯表達式的解答，同年O.J.Rodseth對他們的解答作了簡化，1988年，H.Greenberg進一步作了簡化，使所用步驟量為O(log a)。

n≥4時，尚無一般公式。