「合同式congruence_equation」の研究

• [定義]
  整数a,b,mに対して、
  a-bがmの整数倍のとき、
  aはmを法modulusとしてbと合同である、といい、
  a≡b  (mod  m)と書く。
• [定理1]a≡b  (mod  m)となるための必要十分条件は、a,bをmで割った余りが等しいことである。
  [証明]
  • a≡b  (mod  m)→a,bをmで割った余りが等しいを示す。
    a,bをmで割った余りをそれぞれr₁,r₂とおくと、
    a=ma'+r₁ただし、0≦r₁＜m
    xb=mb'+r₂ただし、0≦r₂＜m
    a-b=m(a'-b')+(r₁-r₂)・・・(1)
    ここで、
    0≦r₁＜m
    -m＜-r₂≦0
    であるから、
    -m＜r₁-r₂＜m・・・(2)
    一方、a≡bであるから、a-bは、mの整数倍であり、
    (1)式より、r₁-r₂もmの整数倍でなければならない。
    (2)の範囲の中でこれを満たすのは、r₁-r₂=0のみである。
    よって、r₁=r₂
  • a,bをmで割った余りが等しい→a≡b  (mod  m)を示す。
    a,bをmで割った余りがいずれもrとすると、
    a=ma'+r
    b=mb'+r
    ただし、0≦r＜m
    a-b=m(a'-b')
    a-bはmの整数倍である。
• [定理2]mを法とするとき、次の3式(同値律）がなりたつ。
  1. 反射律    a≡a  (mod  m)
  2. 対称律    a≡b  (mod  m)ならばb≡a  (mod  m)
  3. 推移律    a≡b  (mod  m),b≡c  (mod  m)ならばa≡c  (mod  m)
  [証明]
  1. a=ma'+rただし、0≦r＜m、とすると、
     a-a=0すなわち、a≡a
  2. a≡b  (mod  m)から、
     a=ma'+r,b=mb'+rただし、0≦r＜m
     b-a=m(b'-a')よって、b≡a
  3. a≡b  (mod  m)から、
     a=ma'+r,b=mb'+rただし、0≦r＜m
     b≡c  (mod  m)から、
     b=mb'+r,c=mc'+rただし、0≦r＜m
     a-c=m(a'-c')よって、a≡c
• [定理3]a≡b  (mod  m),c≡d  (mod  m)のとき、次の各式が成立する。
  1. a+c≡b+d  (mod  m)
  2. a-c≡b-d  (mod  m)
  3. ac≡bd  (mod  m)
  4. aⁿ≡bⁿ  (mod  m)ただしnは自然数
  [証明]
  a≡b  (mod  m)より、a-b=mq₁
  c≡d  (mod  m)より、c-d=mq₂
  1. (a+c)-(b+d)=(a-b)+(c-d)=m(q₁+q₂)
  2. (a-c)-(b-d)=(a-b)-(c-d)=m(q₁-q₂)
  3. ac-bd=(b+mq₁)(d+mq₂)-bd
         =bmq₂+dmq₁+m²q₁q₂
         =m(bq₂+dq₁+mq₁q₂)
  4. 数学的帰納法による。
     • n=1のときa≡b  (mod  m)・・・(ア)
     • n=kに対して、aⁿ≡b^k  (mod  m)と仮定。
       iiiより、aa^k≡bb^k  (mod  m)
       すなわち、a^k+1≡b^k+1  (mod  m)・・・(イ)
     (ア)(イ)より、任意の自然数nに対して、aⁿ≡bⁿ  (mod  m)
• [定理3・系1]
  a≡b  (mod  m)のとき、任意の整数nに対して、
  a≡b+mn  (mod  m)
  [証明]
  a≡b  (mod  m)より、a-b=mq
  a-(b+mn)=mq-mn=m(q-n)
• [定理3・系2]
  整数係数の整式に対して、
  a≡b  (mod  m)のとき、f(a)≡f(b)  (mod  m)
  [証明]
  a≡b  (mod  m)だから、k=0,1,2,・・・,n-1に対して、[定理3iv]より、
  a^n-k≡b^n-k  (mod  m)
  また、a⁰≡b⁰  (mod  m)
  よって、k=0,1,2,・・・,nに対して、a^n-k≡b^n-k  (mod  m)
  a^n-k≡b^n-k=mq_kと書くことができる。
  
• [定理4]ac≡bc  (mod  m)のとき、(c,m)=gならば、
  a≡b  (mod  m/g)
  ここに、(c,m)=gとは、c,mの最大公約数がgであることをあらわす。
  [証明](c,m)=gより、c=gc',m=gm'とおくことができる。
  ここに、(c',m')=1すなわち、c',m'は互いに素である。
  ac≡bc  (mod  m)より、ac-bc=mq=gm'q
  一方、ac-bc=c(a-b)=gc'(a-b)
  すなわち、gm'q=gc'(a-b)
  すなわち、m'q=c'(a-b)
  (c',m')=1だから、a-bはm'で割り切れる。すなわち、a-bはm/gで割り切れる。
• [定理4・系]ac≡bc  (mod  m)のとき、(c,m)=1ならば、
  a≡b  (mod  m)
• [定理3i〜iii]では、｢加・減・乗｣の3つの演算に関しては、｢合同式｣が通常の数式の等式と同様に扱えることが明らかになった。
  しかし、｢除｣に関しては、[定理4・系]が示すように、序数と法が互いに素であるときに限り、行うことができる。

1. 
   • (1)24≡4  (mod  5)、[定理3iv]より、24⁵⁰≡4⁵⁰  (mod  5)
     4⁵⁰=16²⁵、16≡1  (mod  5)、同様に、16²⁵≡1²⁵  (mod  5)
     よって、24⁵⁰≡1  (mod  5)
   • (2)3¹⁰⁰5²⁰=9⁵⁰25¹⁰
     9≡1  (mod  8)、25≡1  (mod  8)だから、
     [定理3iv]より、9⁵⁰≡1  (mod  8)、25¹⁰≡1  (mod  8)
     [定理3iii]より、9⁵⁰25¹⁰≡1  (mod  8)
     すなわち、3¹⁰⁰5²⁰≡1  (mod  8)
   • (3)513⁸¹を10で割った余りを求めればよい。
     513≡3  (mod  10)、[定理3iv]より、513⁸¹≡3⁸¹  (mod  10)
     3⁸¹=3^4×20+1=81²⁰×3
     81≡1  (mod  10)、[定理3iv]より、81²⁰≡1  (mod  10)
     [定理3iii]より、81²⁰×3≡1×3  (mod  10)
     よって、513⁸¹≡3  (mod  10)
   • (4)9³⁰⁰を100で割った余りを求めればよい。
     二項定理より、
     右辺のk=0からk=298に対応する項はすべて100で割り切れるから、
     9³⁰⁰≡₃₀₀C₂₉₉10¹(-1)²⁹⁹+₃₀₀C₃₀₀10⁰(-1)³⁰⁰≡300・10・(-1)+1≡1  (mod  100)
     よって、9³⁰⁰≡1  (mod  100)
2. 
   • (1)n≡2  (mod  7)だから、
     [定理3iv]より、n²≡2²≡4  (mod  7)
     [定理3iii]より、3n≡3・2≡6  (mod  7)
     [定理3i,ii]より、n²+3n-1≡4+6-1≡9≡2  (mod  7)
   • (2)n≡11  (mod  13)だから、
     [定理3iv、系1]より、n²≡11²≡121≡13×9+4≡4  (mod  13)
     [定理3iii、系1]より、12n²≡12×4≡48≡13×3+9≡9  (mod  13)
     [定理3iii、系1]より、2n≡2×11≡22≡13×1+9≡9  (mod  13)
     [定理3i,ii、系1]より、12n²-2n+25≡9-9+25≡25≡13×1+12≡12  (mod  13)
3. 
   • (1)2・3ⁿ+5^2n-1≡0  (mod  11)を示したい。
     5^2n-1=5^2(n-1)+1=5・25^n-1
     25≡3  (mod  11)、[定理3iii,iv]より、5・25^n-1≡5・3^n-1  (mod  11)
     [定理3i]より、
     2・3ⁿ+5・25^n-1≡2・3ⁿ+5・3^n-1≡6・3^n-1+5・3^n-1≡11・3^n-1≡0  (mod  11)
     よって、2・3ⁿ+5^2n-1≡0  (mod  11)
   • (2)7²ⁿ⁺¹+5^2n-1≡0  (mod  12)を示したい。
     7²ⁿ⁺¹+5^2n-1=7²ⁿ⁺¹+5^2(n-1)+1=7・(7²)ⁿ+5・(5²)^n-1=7・49ⁿ+5・25^n-1
     [定理3・系1]より、49≡12×4+1≡1  (mod  12)、25≡12×2+1≡1  (mod  12)
     [定理3iv,iii,i]より、7・49ⁿ+5・25^n-1≡7・1ⁿ+5・1^n-1≡7+5≡12≡0  (mod  12)
4. 
   • (1)3を何倍かして、5で割ると1余る数にしたい。
     3x≡2  (mod  5)
     [定理3iii]より、6x≡4  (mod  5)
     [定理3・系1]より、5x+x≡x≡4  (mod  5)
   • (2)3を何倍しても、8で割ると1余る数にはできない。
     これは、[定理4]の適用場面で、
     2x≡4  (mod  8)
     (2,8)=2だから、つまり、2と8の最大公約数は2だから、
     x≡2  (mod  4)
     ｢合同式を解く｣とは、未知数xの与えられた法に対する剰余を求めることだから、
     x≡□  (mod  8)でなければならない。
     x≡2  (mod  4)から、x-2=4qすなわち、x=4q+2
     4で割ると2余る数を、8で割った余りは?、これは、qが2の倍数であるか否かで異なる。
     1. q=2q'のとき・・・x=8q'+2すなわち、x≡2  (mod  8)
     2. q=2q'+1のとき・・・x=8q'+6すなわち、x≡6  (mod  8)
     よって、x≡2,6  (mod  8)
5. 
   • (1)5を何倍かして、7で割ると1余る数にしたい。
     5x≡3  (mod  7)
     [定理3iii]より、15x≡9≡2  (mod  7)
     [定理3・系1]より、2×7x+x≡x≡2  (mod  7)
   • (2)13を何倍かして、11で割ると1余る数にしたい。78=13×6=11×7+1
     13x≡8  (mod  11)
     [定理3iii]より、78x≡48≡4  (mod  11)
     [定理3・系1]より、7×11x+x≡x≡4  (mod  11)
   • (3)3x≡6  (mod  9)
     (3,9)=3であるから、[定理4]より、x≡2  (mod  3)
     すなわち、x=3q+2
     qを3の剰余類に分類する。
     1. q=3q'のとき、・・・x=9q'+2
     2. q=3q'+1のとき、・・・x=9q'+5
     3. q=3q'+2のとき、・・・x=9q'+8
     よって、x≡2,5,8  (mod  9)
   ところで、｢解のない｣合同式(合同方程式)が存在する。
   [定理5]合同式ax≡b  (mod  m)は、(a,m)がbを割り切るとき、そのときだけ解をもつ。
   [例]2x≡5  (mod  4)は、解をもたない。
   2x-5=4q
   左辺は奇数であり、右辺は偶数であるから、このような整数x,qは存在しない。
6. 
   • (1)x,yの係数を比較すると、2より3の方が大きいから、3=2×1+1として、
     2x+3y≡2x+(2×1+1)y≡y  (mod  2)
     一方、31≡1  (mod  2)
     よって、y≡1  (mod  2)
   • (2)y=2k+1 (kは整数)とすると、
     2x+3y=31
     2x+3(2k+1)=31
     2x+6k=28
     x+3k=14
     x=-3k+14
     よって、整数kに対して、(x,y)=(-3k+14,2k+1)
7. 
   • (1)11x+13y=23
     11x+13y≡11x+(11+2)y≡2y  (mod  11)
     23≡2×11+1≡1  (mod  11)
     よって、2y≡1  (mod  11)
     12y≡11y+y≡y≡6  (mod  11)
     y=11k+6 (kは整数)とすると、
     11x+13(11k+6)=23
     11x+13×11k=23-78=-55
     x+13k=-5
     よって、整数kに対して、(x,y)=(-13k-5,11k+6)
   • (2)39x-29y=326
     39x-29y≡(29+10)x-29y≡10x  (mod  29)
     326≡29×11+7≡7  (mod  29)
     よって、10x≡7  (mod  29)
     30x≡29x+x≡x≡21  (mod  29)
     x=29k+21 (kは整数)とすると、
     39(29k+21)-29y=326
     39×29k-29y=326-39×21=326-819=493=-29×17
     39k-y=-17
     よって、整数kに対して、(x,y)=(29k+21,39k+17)

自然数a,bがあり、
(a,b)=1、すなわち、a,bは互いに素であるとする。
このとき、方程式、
ax+by=1
を満たす、0でない整数解(x,y)が無数に存在する。
その中で、0＜|x|＜b,0＜y＜aとなるものと、
0＜x＜b,0＜|y|＜aとなるものとが、各一組ずつ存在する。

---

[証明]

• (a,b)=1であるから、a,bの最小公倍数l=abである。
  すなわち、lはaで割り切れ、かつ、
  n=1,2,3,・・・,a-1のすべてのnに対して、
  nbはaで割り切れない。
  そこで、
  nb=qa+rただし、qは自然数、0＜r0＜a
  となるq,rが存在する。
• 異なるnに対しては、rも異なることを示す。背理法による。
  n≠n'に対して、
  nb=qa+r
  n'b=q'a+r
  なる、自然数q,q'が存在すると仮定する。
  (n-n')b=(q-q')aとなる。
  • n＞n'とすると、q＞q'で、n'＜n＜aだから、0＜n-n'＜a
    これは、a,bの最小公倍数がl=abであるのに、
    aよりはるかに小さいn-n'に対して、(n-n')bがすでにaの倍数であると主張しており、明らかに不合理である。
  • n＜n'の場合も同様である。
  よって、異なるnに対しては、rも異なることが示された。そこで、
  nb=q(n)a+r(n)  ただし、n=1,2,3,・・・,a-1
  と書くことができる。
• ところで、r(n)は、nbをaで割った余りなのだから、1,2,3,・・・,a-1のいずれかに等しい。
  nごとに異なるa-1個のr(n)が、同じくa-1個の1,2,3,・・・,a-1という値のいずれかをとるのであるから、これは一対一の対応である。
  したがって、a-1個のr(n)のうちに、かならず一つだけ、1に等しいものがある。
  それをr(a')、ただし、0＜a'＜a、としよう。
  すなわち、a'b=qa+1と書ける。
  すなわち、-qa+a'b=1
  であるから、(x,y)=(-q,a')は、与えられた方程式の一つの解である。
  ここに、qa＜a'b＜abであるから、0＜q＜b
  また、0＜a'＜aであるから、この解は、
  0＜|x|＜b,0＜y＜aの条件を満たしている。
  0＜q＜bしたがって、0＜b-q＜b
  q'=b-qとおくと、0＜q'＜b
  (q'-b)a+a'b=1
  q'a-(a-a')b=1
  a''=a-a'とおくと、0＜a''＜a
  q'a-a''b=1
  したがって、(x,y)=(q',-a'')も、与えられた方程式の一つの解である。
  0＜q'＜b,0＜a''＜aであるから、この解は、
  0＜x＜b,0＜|y|＜aの条件を満たしている。

---

6. 2x+3y=31・・・(ア)
   (2,3)=1であるから、2x'+3y'=1は整数解をもつ。
   得られた(x',y')に対して、(x,y)=(31x',31y')である。
   2x'+3y'=1を解く。・・・(イ)
   x',y'の係数2,3を「ユークリッド互助法」により、次第に小さくし、最終的にはどちらかを1に帰着させる。
   (2,3)=1、すなわち、2と3は互いに素であるから、かならずこれは可能である。
   2x'+(2×1+1)y'=1
   2(x'+y')+y'=1
   こうして、第2項の係数が1となった。
   明らかに、x'+y'=0,y=1は、解である。
   この連立方程式を解くと、
   (x',y')=(-1,1)
   これは(イ)の無数に存在する整数解のうちのひとつの解（特殊解）である。
   ちなみにこれは、x'が絶対値において3より小さい正数であり、かつ、y'が2より小さい正数である特殊解である。
   (イ)に代入して、辺々引くと、
   2x'+3y'=1・・・(イ)
   2(-1)+3・1=1・・・(ウ)
   2(x'+1)+3(y'-1)=0・・・(イ)-(ウ)
   すなわち、
   2(x'+1)=-3(y'-1)
   ここに、(2,3)=1であるから、
   x'+1=-3k
   y'-1=2k
   すなわち、
   (x',y')=(-3k-1,2k+1)
   無論、k=0のときが、上の、
   x'が絶対値において3より小さい正数であり、かつ、y'が2より小さい正数である特殊解、
   (x',y')=(-1,1)
   である。
   では、
   x'が3より小さい正数であり、かつ、y'が絶対値において2より小さい正数である特殊解、
   の方はどうか?
   k=-1とすればよい。すなわち、
   (x',y')=(2,-1)
   (ア)に戻ると、解は次のように書ける。
   (x,y)=(31(-3k-1),31(2k+1))
   もう少しシンプルな表現にしたい。k'=31kとおくと、
   (x,y)=(-3k'-31,2k'+31)
   さらに、たとえば、k''=k'+15とおくと、
   (x,y)=(-3(k''-15)-31,2(k''-15)+31)=(-3k''+14,2k''+1)
   または、たとえば、k'''=k'+10とおくと、
   (x,y)=(-3(k'''-10)-31,2(k'''-10)+31)=(-3k'''-1,2k'''+11)
   ここでも、端数の絶対値を31より小さくする方法が、ただ2通り、存在するのである。
7. • (1)11x+13y=23・・・(ア)
     (11,13)=1であるから、11x'+13y'=1は整数解をもつ。
     得られた(x',y')に対して、(x,y)=(23x',23y')である。
     11x'+13y'=1を解く。・・・(イ)
     x',y'の係数11,13を「ユークリッド互助法」により、次第に小さくし、最終的にはどちらかを1に帰着させる。
     (11,13)=1、すなわち、11と13は互いに素であるから、かならずこれは可能である。
     11x'+(11×1+2)y'=1
     11(x'+y')+2y'=1
     (2×5+1)(x'+y')+2y'=1
     2{5(x'+y')+y'}+(x'+y')=1
     2(5x'+6y')+(x'+y')=1
     こうして、第2項の係数が1となった。
     明らかに、5x'+6y'=0,x'+y=1は、解である。
     この連立方程式を解くと、
     
     
     (x',y')=(6,-5)
     これは(イ)の無数に存在する整数解のうちのひとつの解（特殊解）である。
     ちなみにこれは、x'が13より小さい正数であり、かつ、y'が絶対値において11より小さい正数である特殊解である。
     (イ)に代入して、辺々引くと、
     11x'+13y'=1・・・(イ)
     11・6+13(-5)=1・・・(ウ)
     11(x'-6)+13(y'+5)=0・・・(イ)-(ウ)
     すなわち、
     11(x'-6)=-13(y'+5)
     ここに、(11,13)=1であるから、
     x'-6=-13k
     y'+5=11k
     すなわち、
     (x',y')=(-13k+6,11k-5)
     無論、k=0のときが、上の、
     x'が13より小さい正数であり、かつ、y'が絶対値において11より小さい正数である特殊解、
     (x',y')=(6,-5)
     である。
     では、
     x'が絶対値において13より小さい正数であり、かつ、y'が11より小さい正数である特殊解、
     の方はどうか?
     k=1とすればよい。すなわち、
     (x',y')=(-7,6)
     (ア)に戻ると、解は次のように書ける。
     (x,y)=(23(-13k+6),23(11k-5))
     もう少しシンプルな表現にしたい。k'=23kとおくと、
     (x,y)=(-13k'+23×6,11k'-23×5)
     23×6=13×10+8,23×5=11×10+5であるから、
     さらに、たとえば、k''=k'-10とおくと、
     (x,y)=(-13(k''+10)+13×10+8,11(k''+10)-11×10-5)=(-13k''+8,11k''-5)
     23×6=13×11-5,23×5=11×11-6であるから、
     または、たとえば、k'''=k'-11とおくと、
     (x,y)=(-3(k'''+11)+13×11-5,11(k'''+11)-11×11+6)=(-13k'''-5,11k'''+6)
     ここでも、端数の絶対値を23より小さくする方法が、ただ2通り、存在するのである。
   • (2)39x-29y=326・・・(ア)
     (39,29)=1であるから、39x'-29y'=1は整数解をもつ。
     得られた(x',y')に対して、(x,y)=(326x',326y')である。
     39x'-29y'=1を解く。・・・(イ)
     x',y'の係数の絶対値39,29を「ユークリッド互助法」により、次第に小さくし、最終的にはどちらかを1に帰着させる。
     (39,29)=1、すなわち、39と29は互いに素であるから、かならずこれは可能である。
     (29×1+10)x'-29y'=1
     29(x'-y')+10x'=1
     (10×2+9)(x'-y')+10x'=1
     10{2(x'-y')+x'}+9(x'-y')=1
     10(3x'-2y')+9(x'-y')=1
     (9×1+1)(3x'-2y')+9(x'-y')=1
     9{(3x'-2y')+(x'-y')}+(3x'-2y')=1
     9(4x'-3y')+(3x'-2y')=1
     こうして、第2項の係数が1となった。
     明らかに、4x'-3y'=0,3x'-2y=1は、解である。
     この連立方程式を解くと、
     
     
     (x',y')=(3,4)
     これは(イ)の無数に存在する整数解のうちのひとつの解（特殊解）である。
     ちなみにこれは、x'が29より小さい正数であり、かつ、-y'が絶対値において39より小さい正数である特殊解である。
     (イ)に代入して、辺々引くと、
     39x'-29y'=1・・・(イ)
     39・3-29・4=1・・・(ウ)
     39(x'-3)-29(y'-4)=0・・・(イ)-(ウ)
     すなわち、
     39(x'-3)=29(y'-4)
     ここに、(39,29)=1であるから、
     x'-3=29k
     y'-4=39k
     すなわち、
     (x',y')=(29k+3,39k+4)
     無論、k=0のときが、上の、
     x'が29より小さい正数であり、かつ、-y'が絶対値において39より小さい正数である特殊解、
     (x',y')=(3,4)
     である。
     では、
     x'が絶対値において29より小さい正数であり、かつ、-y'が39より小さい正数である特殊解、
     の方はどうか?
     k=-1とすればよい。すなわち、
     (x',y')=(-26,-35)
     (ア)に戻ると、解は次のように書ける。
     (x,y)=(326(29k+3),326(39k+4))
     もう少しシンプルな表現にしたい。k'=326kとおくと、
     (x,y)=(29k'+326×3,39k'+326×4)
     326×3=29×33+21,326×4=39×33+17であるから、
     さらに、たとえば、k''=k'+33とおくと、
     (x,y)=(29(k''-33)+29×33+21,39(k''-33)+39×33+17)=(29k''+21,39k''+17)
     326×3=29×34-8,326×4=39×34-22であるから、
     または、たとえば、k'''=k'+34とおくと、
     (x,y)=(29(k''-34)+29×34-8,39(k''-34)+39×34-22)=(29k''-8,39k''-22)
     ここでも、端数の絶対値を326より小さくする方法が、ただ2通り、存在するのである。

---

｢新課程｣初年度のこの学年の教科書を、私は見ていないから、たとえば新たに盛り込まれた｢2元1次不定方程式の整数解｣問題、いわゆる｢ディオファントス方程式｣でございますな、・・・、の解法を、高校生にどう説明すべきか?、を知らなかった。単なる｢趣味｣として、高木貞治｢新式算術入門｣(ちくま学芸文庫)を読んで、まだ｢路頭に迷う｣とは予想していなかった(笑)昨年の秋ごろ、没頭していたから、｢得意｣分野ではあるのだが、高木貞治が紹介している｢オイラーの方法｣、しかも高木貞治が、｢あとは、わかるでしょ?｣みたいに(笑)放り出している部分は、自己流で補って、編み出した方法は、以前ご紹介したように、こんな感じ(↓)で、
「冷笑に満ちた『修辞疑問文』のさなかで?」
こんなに延々と数式を羅列したのでは、ほとんどが文科系志望の生徒さんたちは、辟易してしまうだろう、とも思えた。案の定、「先生、教科書に書いてあるの、もっと簡単そうだよ｣、と、声がかかった。斜に構えて、にやにや｢冷笑｣しているだけではなく(笑)、ちゃんと指摘してくれる、｢進学校｣ではない生徒さんの朴訥さが、ありがたい(笑)。
やっていることの｢本質｣は(笑)、同じ、｢ユークリッド互除法｣なのだが、確かに、わかりやすい説明にはなっている。こうして初めて知った(笑)教科書風の、ディオファントス解法を、紹介する。以前のと同じ例題を用いよう。

39x-29y=326
ここで、39と29はたがいに素であるから、
39x'-29y'=1
は整数解をもつ。高木貞治のきわめてエレガントなその証明も、以前ご紹介(↓)したが、
「人が饒舌だとしたら、それは、何かそれ以外のことを、決して喋りたく『ない』からだ。」
高校教科書では、ここは証明なしで断言しているのだと思う。
得られた一組の(x',y')に対して、(x,y)=(326x',326y')とあらわされることは明らかである。
「ユークリッド互除法」を39,29に適用する。たがいに素であることは明白だから、｢1｣に至るまで続く筈である。
39=29×1+10・・・(1)
29=10×2+9・・・(2)
10=9×1+1・・・(3)
これで｢収束｣した。この3式を組み立てなおして、目標である、
1=39x'-29y'
を｢再構成｣しよう、と言うのである。各式の第1項を移項して、左辺右辺を入れ替え、かつ、番号を逆順にして並べて見ると、
1=10-9×1・・・(3')
9=29-10×2・・・(2')
10=39-29×1・・・(1')
(3')式の「9」に(2')式を「代入｣する。
1=10-(29-10×2)×1
｢10｣を同類項としてまとめると、29と10、もちろんたがいに素、の｢1次結合｣になる。もちろん教科書はそんな小難しいことは言わない(笑)。
1=10×(1+2)-29×1
1=10×3-29×1
｢10｣に(1')を「代入」し、おなじく｢29｣を同類項としてまとめると、今度こそ、39と29の｢1次結合｣になり、これが求めるものなのであった!
1=(39-29×1)×3-29×1
1=39×3-29×(3+1)
1=39×3-29×4
ほら!(笑)こうして、(x',y')=(3,4)が得られた、したがって、(x,y)=(326×3,326×4)が解である。