第1章 江戸時代初期

１次のディオファントス方程式とはa,b,cを与えられた整数として ax+by=c という形の方程式で、整数解x,yが存在するかどうかを調べるものです。例えば 2x+3y=1にはx=2,y=-1など、解が無限に存在しますが、2x+6y=1 には解が存在しません。そして、2x+3y=1 の解はtを任意の整数としてx=2+3t, y=-1-2t という形をしています。K.F.ガウスはx-2は3の倍数であることをx≡2(mod 3)と書いて、xと2は3を法にして合同などと呼ぶことにしました。 ax+by=cが解を持つための必要十分条件はcがaとbの最大公約数 d=(a,b)の倍数であることで、このときax≡c (mod b)、by≡c (mod a) が成り立っています。ax≡c (mod b)はd=1の時x≡p(mod b)という形の解があり、d>1の時x≡q(mod c/d)という形の解があります。

ax≡b (mod c)という形の合同方程式は、解が存在する場合は x≡s (mod t)という形に書き換えられますので、次はx≡a (mod m)かつ x≡b (mod n)という形の連立合同方程式の解がどうなるかが問題となります。解が存在する必要十分条件はmとnの最大公約数を dとしたとき、a≡b (mod d)となることです。特にd=1の時(言い換えると、mとnが互いに素)、解はx≡p (mod mn)という形になります。s個の連立合同式x≡a₁ (mod m₁)かつ x≡a₂ (mod m₂)かつ ... x≡a_s (mod m_s)の解は、これを繰り返すことで、解はx≡q (mod m₁m₂...m_s)という形になります。これを中国式剰余定理と呼びます。

以下では、合同式と合同方程式について実例を使って説明してみましょう。a≡b (mod c)とはa-bがcの倍数になることで、あるnがあってa-b=cn となることです。mod 3 の例をみてみましょう。

...-9≡-6≡-3≡0≡3≡6≡9...(mod 3)
...-8≡-5≡-2≡1≡4≡7≡10...(mod 3)
...-7≡-4≡-1≡2≡5≡8≡11...(mod 3)

のように、整数は互いに合同な数字からなる3つのグループに分かれます。[一般にmod mは整数全体をm個のグループに分けます]そして、整数の足し算、掛け算をグループとして見てみます(赤字がグループの代表)と、
0+0=0, 0+1=1, 0+2=2, 1+1=2, 1+2=0, 2+2=1, 0×0=0, 0×1=0, 0×2=0, 1×1=1, 1×2=2, 2×2=1 が同じグループ内のどの数字に対しても成り立っていることがわかります。これによりax≡b (mod c)という形の方程式には規則的な解が存在するのです。

2x≡1 (mod 3)という方程式を考えてみましょう。2×2=1 ですので、グループ２の数字すべてが解になり、x≡１（mod 3）が答えになります。ところが3x≡1 (mod 3)という方程式には解が存在しません。（3は0のグループなので、どんな数字をかけても１にはならない）方程式ax≡b (mod c)は、bがaとcの最大公約数の倍数である時に解け、aとcが互いに素(最大公約数が1)であれば、bがどんな数であっても解けます。

次に15x≡21 (mod 33)という方程式を考えてみましょう。15と33の最大公約数は3で、21は3の倍数ですので、解が存在します。この方程式は15x-21=33nということですが、全体が3で割れて5x-7=11nとなり、5x≡7 (mod 11)と同じ方程式です。これを解くには、7に11ずつ足していって5の倍数となるものを探します。7+11×3=40が5の倍数ですので、5x≡40 (mod 11)よりx≡8 (mod 11)が解になります。この解をもとのmod 33で書き直しますと、x≡8 (mod 33)、x≡19 (mod 33)、x≡30 (mod 33)という３つの解があることになります。

それでは連立合同方程式の例を見てみましょう。『塵劫記』の問題を一般化してx≡a (mod 3) & x≡b (mod 5) & x≡c (mod 7)を解いてみます。3,5,7は互いに素ですので、中国式剰余定理からx≡p (mod 3×5×7)という形の解が存在します。s≡a (mod 3) & s≡0 (mod 5) & s≡0 (mod 7)となるsと、t≡b (mod 5) & t≡0 (mod 3) & t≡0 (mod 7)となるtと、 u≡c (mod 7) & u≡0 (mod 3) & u≡0 (mod 5)となるuの和x=s+t+uが条件を満たしていることを確かめてください。ではs,t,uを実際に求めてみましょう。

sは35の倍数で、3で割るとa余る数ですが、35の倍数で3で割ると1余る最小の数は70ですので、s=70aとなります。tは21の倍数で5で割るとb余る数、21の倍数で5で割ると1余る最小の数は21ですのでt=21b、uは15の倍数で7で割るとc余る数、15の倍数で7で割ると1余る最小の数は15ですので、u=15cとなります。従って、解はx≡70a+21b+15c (mod 105)です。　『括要算法』の問題はa=2,b=1,c=5の場合ですので、解はx≡70×2+21×1+15×5 (mod 105)、すなわちx≡236 (mod 105)、きれいにするとx≡26 (mod 105)です。

最後に問題をひとつ出しておきます。解答は腕試し問題Q2にあります。

問　x≡a (mod 5) & x≡b (mod 11) & x≡c (mod 13)の一般解を求めなさい。