§A4.17競技数学入門

例 1.1 ($n^5-n$の整除). 任意の整数$n$について$30\mid n^5-n$である。$30=2\cdot3\cdot5$と分解し、$n^5-n=n(n^4-1)$を法2、法3、法5で調べる。

• 法2。$n$が偶数なら$2\mid n$である。$n$が奇数なら$n^4$も奇数なので、$2\mid n^4-1$である。
• 法3。$n\equiv0\pmod3$なら$3\mid n$である。$n\equiv\pm1\pmod3$なら$n^2\equiv1\pmod3$であるから、$3\mid n^4-1$である。
• 法5。$5\mid n$なら$5\mid n^5-n$である。$5\nmid n$なら、$5$が素数であるからフェルマーの小定理を適用でき、$n^4\equiv1\pmod5$である。

したがって、$n^5-n$は2、3、5のそれぞれで割り切れる。$2,3,5$はどの二つも互いに素であるから、$30\mid n^5-n$である。

例 1.2 (平方数の法4における余り). 任意の整数$x$に対して$x^2\equiv0$または$1\pmod4$であり、$x^2\equiv2\pmod4$とはならない。$x$が偶数なら$x=2k$と書けるので$x^2=4k^2\equiv0\pmod4$である。$x$が奇数なら$x=2k+1$と書けるので

である。二つの場合で整数を尽くすので、結論を得る。

例 1.3 (素数の平方の法24における余り).$p>3$を素数とする。$p$は奇数なので$p=2k+1$と書け、$p^2-1=4k(k+1)$である。$k(k+1)$は連続する二整数の積なので偶数であり、$8\mid p^2-1$、すなわち$p^2\equiv1\pmod8$である。

また、$p>3$は素数なので$3\nmid p$である。したがって$p\equiv\pm1\pmod3$であり、$p^2\equiv1\pmod3$である。$8$と$3$は互いに素であり、$8\mid p^2-1$と$3\mid p^2-1$がともに成り立つので、$24\mid p^2-1$である。よって$p^2\equiv1\pmod{24}$である。

例 3.1 ($x^2=2y^2$に対する降下).$x^2=2y^2$を満たす正整数解が存在すると仮定し、その中から$x$が最小となる解$(x,y)$を取る。$x^2$は偶数なので$x$は偶数であり、正整数$u=x/2$を用いて$x=2u$と書ける。すると

$4u^2=2y^2,\qquad y^2=2u^2$

となる。したがって、$(y,u)$は$Y^2=2U^2$を満たす正整数の組であり、元と同じ方程式の解である。また$x^2=2y^2>y^2$で$x,y>0$だから$y<x$である。新しい解$(y,u)$の第一成分は元の解の第一成分より小さく、$x$の最小性に反する。よって正整数解は存在しない。

もし$\sqrt2=x/y$と正整数$x,y$を用いて書けたなら$x^2=2y^2$となるので、$\sqrt2$は無理数である。この証明では分数を既約にする操作を用いず、正整数解の最小性だけを用いている。

例 4.1 ($x^4+y^4=z^2$に対する三つの判断).$x^4+y^4=z^2$を満たす正整数解が存在すると仮定し、その中から$z$が最小となる解$(x,y,z)$を取る。

第1段（互いに素にする）。 素数$p$が$x$と$y$の両方を割ると仮定する。このとき$p^4\mid z^2$であるから、素因数の指数を比較すると$p^2\mid z$である。したがって$(x/p,y/p,z/p^2)$は正整数の組であり、

を満たす。さらに$z/p^2<z$であり、$z$の最小性に反する。よって$\gcd(x,y)=1$である。

第2段（法4で偶奇を決める）。$(x^2)^2+(y^2)^2=z^2$と読むと、$\gcd(x^2,y^2)=1$を満たすピタゴラス数である。$x,y$は両方偶数ではない。両方奇数なら$z^2\equiv1+1\equiv2\pmod4$となり、例 1.2に反する。よって$x,y$の一方だけが偶数である。必要なら$x,y$を入れ替え、$x$を偶数、$y$を奇数とする。

原始ピタゴラス数の一般形（フェルマーの最終定理$n=4$ で証明したもの）より、互いに素で偶奇の異なる正整数$m>n>0$があって

$x^2=2mn,\qquad y^2=m^2-n^2,\qquad z=m^2+n^2$

と書ける。$m,n$の偶奇は異なる。$m$が偶数で$n$が奇数なら$m^2-n^2\equiv3\pmod4$となるが、$y$は奇数なので$y^2\equiv1\pmod4$である。したがって$m$は奇数で、$n$は偶数である。

第3段（指数に着目する）。$n$は偶数なので、正整数$w$を用いて$n=2w$と書く。$x^2=2mn=4mw$より

$\left(\frac{x}{2}\right)^2=mw$

である。$w\mid n$と$\gcd(m,n)=1$から$\gcd(m,w)=1$である。補題 2.1を適用すると$m$と$w$はそれぞれ平方数である。したがって、正整数$u,v$を用いて

$m=u^2,\qquad n=2v^2$

と書ける。$m$は奇数なので$u$も奇数である。これを$y^2=m^2-n^2$へ代入すると

$y^2=u^4-4v^4=(u^2-2v^2)(u^2+2v^2)$

となる。二つの因子はともに奇数である。二つの因子を割る素数$d$があると仮定すると、$d$は和$2u^2$と差$4v^2$を割る。$d$は奇数なので$d\mid u^2$かつ$d\mid v^2$である。一方、$\gcd(m,n)=1$と$m=u^2,n=2v^2$から$\gcd(u,v)=1$である。これは両立しない。よって二つの因子は互いに素である。積は平方数$y^2$なので、補題 2.1により、正整数$r,s$を用いて

$u^2-2v^2=r^2,\qquad u^2+2v^2=s^2$

と書ける。第二の因子は正であり、二因子の積$y^2$も正なので、第一の因子も正である。$u$が奇数なので$r,s$はともに奇数である。また$s>r>0$である。差を取ると

$s^2-r^2=4v^2$

である。$s+r$と$s-r$はともに正の偶数なので

$\frac{s+r}{2}\cdot\frac{s-r}{2}=v^2$

が成り立つ。ここで$r$と$s$は互いに素である。実際、両方を割る素数は、$r^2+s^2=2u^2$と$s^2-r^2=4v^2$を割る。$r,s$は奇数なので、その素数は奇数であり、$u$と$v$の両方を割ることになって$\gcd(u,v)=1$に反する。

さらに$(s+r)/2$と$(s-r)/2$をともに割る整数は$s$と$r$をともに割るので、この二つの正整数も互いに素である。積は平方数$v^2$なので、補題 2.1により、正整数$p,q$を用いて

$\frac{s+r}{2}=p^2,\qquad \frac{s-r}{2}=q^2$

と書ける。すると$s=p^2+q^2$、$r=p^2-q^2$であり、$s^2+r^2=(u^2+2v^2)+(u^2-2v^2)=2u^2$から

$u^2=\frac{s^2+r^2}{2}=p^4+q^4$

となる。したがって$(p,q,u)$は正整数の組であり、元と同じ方程式$X^4+Y^4=Z^2$を満たす。

第4段（降下）。$m=u^2$と$n>0$より

$u\le u^2=m\le m^2<m^2+n^2=z$

なので$u<z$である。新しい正整数解$(p,q,u)$の第三成分が$z$より小さいことは、$z$の最小性に反する。したがって、$x^4+y^4=z^2$を満たす正整数解は存在しない。