シルヴァーマン 「はじめての数論」第3版 第6章の練習問題

※MathJaxの数式表示に少し時間がかかります。

6.1
(a) $x=11$, $y=-2$
(b) $x=1645$, $y=9048$

6.2
$k\in\mathbb{Z}$とする。
(a) $x=-53+121k$, $y=46-105k$
(b) $x=11+4526k$, $y=-2-823k$
(c) $x=-1645+3292k$, $y=9048-18107k$

6.3
(c)
(i) $g=7$, $x=1303$, $y=-1095$
(ii) $g=1$, $x=-381$, $y=1448$
(iii) $g=237$,$x=-8980$,$y=10063$

(e)
(c)(ii)(iii)を$x>0$になるよう解き直すと
(ii) $g=1$, $x=8006$,$y=-30427-381$
(iii) $g=237$,$x=19839059$,$y=-22231676$

6.4
(a) $x=7$, $y=-14$, $z=-1$
(b)
$a,b,c$が互いに素であること、すなわち$\gcd(\gcd(a,b),c)=1$であること。
$ax'+by'=\gcd(a,b)$の解$x',y'$と$\gcd(a,b)w+cz=1$の解$w,z$を用いて、$(x,y,z)=(wx',wy',z)$とすればよい。

(c)
$x=2124$, $y=-944$, $z=-19$

6.5
定理6.1によって$au+bv=1$は解$(u,v)=(u_1,v_1)$を常に持つから、$(x,y)=(cu_1,cv_1)$は$ax+by=a(cu_1)+b(cv_1)=c(au_1+bv_1)=c$を満たす。したがって、$ax+by=1$は常に解を持つ。なお$ax+by=c$のすべての解が$x=cu_1+bk$, $y=cv_1-ak$ ($k\in\mathbb{Z}$)で表されることは、本文と同様に示される。
$37u+47v=1$の解をなるべく小さくすると$(u,v)=(14,-11)$が得られるので、$(x,y)=(1442,-1133)$。

6.6
(a)
$x=0$または$y=0$に対して解はなく、$x\ge1$, $y\ge1$については$3x+5y\ge8$だからやはり解はない。

(b)
リストに現れないのは1,2,4,7のみの模様。証明は4について行った(a)と同様。

(c)
(i) 11
(ii) 23
(iii) 29

(d)
$ax+by$にならない最大の数は$ab-(a+b)$と思われる。
(a)と、(c)の3つについては$ab-(a+b)$で合っている。

(e)
$ax+by=ab-(a+b)$に$x\ge0$, $y\ge0$となる解が存在したとすると、$a(x-b+1)=-b(y+1)$だから、$x<b-1$、また$\gcd(a,b)=1$より$a|(y+1)$。これより$y+1=av\ge1$となる$v>0$が存在する。このとき$a(x-b+1)=-abv$より$x=b-1-bv\ge0$だから$b(1-v)\ge1$となるので$1-v\ge1$、故に$v\le0$となり$v>0$と矛盾。したがって$ax+by=ab-(a+b)$に$x\ge0$, $y\ge0$となる解は存在しない。

$c=ab-(a+b)$が$ax+by=c$となる$x\ge0$, $y\ge0$を持ち得ない最大の$c$であることを証明するには、$c=ab-(a+b)+\gamma$ ($\gamma\ge1$)に対し$ax+by=c$となる$x\ge0$, $y\ge0$が常に存在することを示せばよい。まず少し準備。

(i) 方程式$ax+by=ab-(a+b)+\gamma$において、$a,b$のいずれかが1、例えば$b=1$なら$x=0$, $y=\gamma-1\ge0$が常に解となり自明。$a=1$の時も同様。以後$a>1$, $b>1$とする。
(ii) $aX+bY=1$ ($\gcd(a,b)=1$)は定理6.1より常に$X,Y\in\mathbb{Z}$となる解を持つが、$X=bk$ ($k\in\mathbb{Z}$)となる解があったとすると、$b(ak+Y)=1$より$b|1$だから$b=1$となり$b>1$と矛盾する。したがって$X=bk+t$ ($1\le t<b$)。
(iii) $aX+bY=\gamma$ ($\gcd(a,b)=1$, $\gamma\in\mathbb{Z}$)は練習問題6.5により常に$X,Y\in\mathbb{Z}$となる解を持ち、(ii)と同様に$X=bk+t$ ($k\in\mathbb{Z}$, $1\le t<b$)であることを示せる。

方程式$ax+by=ab-(a+b)+1$を考えると、$a(x-b+1)+b(y+1)=1$。いま$aX+bY=1$の解のうち、$X<0$となる一つの解$X_1,Y_1$をとる。$Y_1>0$すなわち$Y_1\ge1$である。また(ii)により$X_1=bk+t$ ($k<0$, $1\le t<b$)と書ける。とくに$k=-1$となるように$X_1<0, Y_1\ge1$をとれる。この$X_1,Y_1$を用いれば、$-(b-1)\le X_1<0$。そこで$x-b+1=X_1$, $y+1=Y_1$とすれば、$x=X_1+b-1\ge0$かつ$y\ge0$となるから、$ax+by=ab-(a+b)+1$には$x\ge0$, $y\ge0$となる解が常に存在する。
方程式$ax+by=ab-(a+b)+\gamma$ ($\gamma>1$)についても、(iii)を用いて上の$\gamma=1$の場合と同様にすれば、$x\ge0$, $y\ge0$となる解が常に存在する。
以上により、$c=ab-(a+b)+\gamma$に対し$ax+by=c$となる$x\ge0$, $y\ge0$が常に存在する。

(f)
...