腊眶a,b,cについて、肌の数镍及の腊眶豺を滇める啼玛を艰り惧げる。
ax+by=c (*)
稍年数镍及(*)を豺くことは、傣部池弄に雇えれば、木俐ax+by=c惧の腊眶爬∈郝筛が尉数とも腊眶の爬∷を滇めることと票じである。
1肌の稍年数镍及(*)について、肌のように窗链な批えを涂えることができる。
[年妄]d=GCD(a,b)と弥くと肌が喇り惟つ。
[1]cがdの擒眶でなければ、(*)は腊眶豺を积たない。
[2]cがdの擒眶ならば、(*)は腊眶豺を∈警なくとも1つ∷积つ。
また、x=x0,y=y0が(*)の1つの豺であれば、(*)のすべての豺が肌の妨で涂えられる。
(**)
ただし、tは扦罢の腊眶である。
[沮汤]数镍及(*)が腊眶豺を积ったとすれば、dは(*)の焊收を充り磊るので、dは((*)の宝收である)cを充り磊らなくてはならない。これで[1]の略而が绩されたので、[1]が喇り惟つ。
海刨は、嫡にdがcを充り磊ると簿年する。このときは、ユ〖クリッドの高近恕によって、数镍及ax+by=dの腊眶豺x=x*,y=y*を滇めることができる。
x=x*,y=y*が(*)の豺であることより、扦罢の腊眶tに滦して(**)が(*)の豺であることはすぐに澄かめられる∈洛掐して纷换するだけである∷。
嫡に、x,yが(*)の豺であるとすれば、霹及(*)からax0+by0=cを苞き换すれば、
a(x-x0)+b(y-y0)=c-c=0
となるので、a(x-x0)=-b(y-y0)が喇り惟つ。
さらに、d=GCD(a,b)で充れば、肌が评られる。
(***)
ここで、a/dとb/dは高いに燎なので、(***)からb/dがx-x0を充り磊ることがわかる。つまり、ある腊眶tによって、と山される。
これを(***)に洛掐すると、が评られる。 ⅱ
极脸眶dに滦して、㈠dは铜妄眶かという啼玛を雇える。
この啼玛は2じの稍年数镍及x2-dy2=0が极脸眶豺を积つかどうかという啼玛と簇息している。
肌の炭玛は词帽だが、梦っていると舔に惟つことが驴い。
[炭玛]腊眶xに滦して、笆布が喇り惟つ。
x2⑨0 or 1 (mod 4)
[沮汤]腊眶xは4を恕とした眷圭、0,1,2,3のどれかに圭票である。x=0,1,2,3の眷圭のx2を4で充った途りを纷换する。
| x | 0 | 1 | 2 | 3 |
| x2 | 0 | 1 | 0 | 1 |
この山から、x2 (mod 4)の猛は0 or 1しかない。 ⅱ
この炭玛は、咐い垂えれば、士数眶は4を恕として2や3に圭票になることはない。
[庙罢]毋えば、17⑨1 (mod 4)なので、惧淡の炭玛より17は士数眶というのは粗般いである。汤らかに17は士数眶ではない。
惧淡の炭玛は士数眶であるためには0または1と圭票でなければならないということであり、0または1と圭票であれば涩ず士数眶になるというのはではない。 〓
さらに、拒しい肌の炭玛も绩すこともできる。
[炭玛]腊眶xに滦して、笆布が喇り惟つ。
x2⑨0 or 1 or 4 (mod 8)
[沮汤]腊眶xは8を恕とした眷圭、0,1,2,3,4,5,6,7のどれかに圭票である。x=0,1,2,3,4,5,6,7の眷圭のx2を8で充った途りを纷换する。
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| x2 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 |
この山から、x2 (mod 4)の猛は0 or 1しかない。 ⅱ
[侍沮][1]xが饿眶ならx=2y(yは腊眶)と山すことができ、x2=4y2である。
このとき、yが饿眶なら、y2も饿眶であるから、≈x2=4y2=4∵饿眶=8の擒眶∽である。
また、yが瘩眶なら、y2も瘩眶であるから、≈x2-4=4(y2-1)=4∵(瘩眶-1)=4∵饿眶=8の擒眶∽である。
[2]xが瘩眶ならx=2z+1(zは腊眶)と山すことができ、x2-1=(2z+1)2-1=4z2+4z=4z(z+1)となる。zかz+1はどちらかが饿眶でるため、x2-1は8の擒眶である。 ⅱ
[毋]肌を塔たす腊眶豺を积たないことを绩す。
x2-21y2=38 (*)
[沮汤]秦妄恕で沮汤するために、(*)が腊眶豺x,yを积つと簿年する。
このとき、38の燎傍眶である19に庙誊して、士数娟途の雇弧を乖っていく。
さて、もし19|yであれば、(*)によって、19|x2が喇り惟つ。
すると、19は燎眶であるから、19|xとなる。
これで、x,yが鼎に19で充り磊れることになったので、(*)の焊收は192で充り磊れる。
しかし、(*)の宝收は192では充り磊れないから、これは谭解する。
したがって、yは19と高いに燎でなくてはならない。
(*)の尉收を19を恕として雇えると、肌が喇り惟つことがわかる。
x2-21y2⑨0 (mod 19)
x2-2y2⑨0 (mod 19) (**) ∈㈣21⑨2 (mod 19)∷
yが19で充り磊れないので、19を恕とするyの嫡眶y-1が赂哼する。
(**)の尉收に(y-1)2を齿けると、肌が评られる。
(xy-1)2⑨2 (mod 19)
これは2が19を恕とする士数娟途であることを绩しているが、これは(2/19)=-1∈2は恕19の士数润娟途の1つだから∷という祸悸に谭解している。 〓
[毋]稍年数镍及x2-xy-2y2=-1は豺を积たないこと∈数镍及を塔たす腊眶x,yは赂哼しないこと∷を绩す。
数镍及を塔たす腊眶x,yが赂哼すると簿年する。
ここで、3を恕として、xとyは0,1,2のどれかに圭票である。これらの猛の寥み圭わせについて、x2-xy-2y2の猛を纷换して、山を侯る。
| x | y | x2-xy-2y2 |
| 0 | 0 | 0 |
| 0 | 1 | -2⑨1 |
| 0 | 2 | -8⑨1 |
| 1 | 0 | 1 |
| 1 | 1 | -2⑨1 |
| 1 | 2 | -9⑨0 |
| 2 | 0 | 4⑨1 |
| 2 | 1 | 0 |
| 2 | 2 | -8⑨1 |
よって、x2-xy-2y2⑨0 or 1である。
[输怪]列妒俐x2-xy-2y2=-1∈列妒俐の敛夺俐はx+y=0とx+2y=0∷が呈灰爬を奶らないことを罢蹋している。 〓
