2015-10-07

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


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

8.1
$k,l\in\mathbb{Z}$とすると、定義により\[a_1-b_1=mk\tag{1}\]\[a_2-b_2=ml\tag{2}\]
(a)
(1)(2)を辺々足して$(a_1+a_2)-(b_1+b_2)=m(k+l)$だから$a_1+a_2\equiv b_1+b_2 \pmod{m}$。

(b)
(1)(2)より$a_1=mk+b_1$, $a_2=ml+b_2$。これらの積より$a_1a_2=m(mkl+kb_2+lb_1)+b_1b_2$なので$a_1a_2-b_1b_2=m(mkl+kb_2+lb_1)$だから$a_1a_2\equiv b_1b_2 \pmod{m}$。

8.2
$k\in\mathbb{Z}$として、定義により$ac-bc=c(a-b)=mk$だから$m|c(a-b)$。$\gcd(c,m)=1$だから練習問題7.1により$m|(a-b)$となるので$a\equiv b \pmod{m}$。

8.3
(a) $x\equiv9\pmod{15}$
(b) 解なし。
(c) $x\equiv1,3,5,7\pmod{8}$
(d) $x\equiv3,4\pmod{7}$
(e) 解なし。

8.4
(a)
$a$の末尾2桁を$a_2$とする。すなわち$a=100k+a_2$ ($k\geq0$, $0\leq a_2<100$ )。$a-a_2=100k=4\cdot25k$だから、$a\equiv a_2\pmod{4}$である。
したがって$4|a$すなわち$a\equiv0\pmod{4}$と$4|a_2$すなわち$a_2\equiv0\pmod{4}$は同値。

(b)
$a$の末尾3桁を$a_3$とする。すなわち$a=1000k+a_3$ ($k\geq0$, $0\leq a_3<1000$ )。$a-a_3=1000k=8\cdot125k$だから、$a\equiv a_3\pmod{8}$である。
したがって$8|a$すなわち$a\equiv0\pmod{8}$と$8|a_3$すなわち$a_3\equiv0\pmod{8}$は同値。

(c)(d)
$n+1$桁の数$a$が、$1\leq a_n\leq9$, $0\leq a_i\leq9$ ($0\leq i\leq n-1$)となる$a_0,\cdots,a_n$を用いて$a=10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0$と表されているとする。$10\equiv1\pmod{9}$なので練習問題8.1(b)により$10^j\equiv1\pmod{9}$ ($1\leq j\leq n$)だから、$10^j=9k_j+1$ ($k_j\in\mathbb{N}$)と書けるので、$a$の各桁の和$s=a_n+a_{n-1}+\cdots+a_1+a_0$として\[a=9(a_nk_n+a_{n-1}k_{n-1}+\cdots+a_1k_1)+s\tag{3}\]これより$a\equiv s \pmod{9}$だから、$9|a$すなわち$a\equiv0\pmod{9}$と$9|s$すなわち$s\equiv0\pmod{9}$は同値。
(3)において3を法としても同様なので、$3|a$と$3|s$は同値。

(e)
(c)(d)と同様に$a=10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0$とする。$10\equiv-1\pmod{11}$なので練習問題8.1(b)により\[10^j\equiv\left\{\begin{array}{cc} 1\pmod{11}& \mbox{($j$が偶数のとき)}\\-1\pmod{11}& \mbox{($j$が奇数のとき)}\end{array}\right.\]
これより$a$の各桁の交代和を$A$として$a\equiv A\pmod{11}$だから、$11|a$すなわち$a\equiv0\pmod{11}$と$11|A$すなわち$A\equiv0\pmod{11}$は同値。

8.5
(a) $x\equiv6,13\pmod{14}$
(b) 解なし。
(c) $x\equiv5,18,31,44,57,70,83\pmod{91}$

8.6
(a) $\gcd(72,200)=8$より$\gcd(72,200)\nmid47$だから、定理8.1により解はない。
(b) $\gcd(4183,15087)=47$で、$\gcd(4183,15087)\mid5781$だから、定理8.1により解は47個。
(c) $\gcd(1537,6731)=53$より$\gcd(1537,6731)\nmid2863$だから、定理8.1により解はない。

2015-10-06

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

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

7.1
定理7.3により$a=p_1p_2\cdots p_n$と素因数分解される。$\gcd(a,b)=1$だから、$p_1$は$b$の因数でないので、定理7.2により$p_1|c$。そこで$a_1=a/p_1=p_2p_3\cdots p_n$, $c_1=c/p_1$とすると、$a_1|bc_1$だから、上と同様に$p_2|c_1$となるので$p_1p_2|c$。同様に繰り返して$p_1p_2\cdots p_n|c$だから$a|c$。

7.2
$a=p_1p_2\cdots p_m$, $b=q_1q_2\cdots q_n$と素因数分解されたとすると、$\gcd(a,b)=1$より$\{p_1,p_2,\cdots, p_m\}\cap\{q_1q_2\cdots q_n\}=\emptyset$。$a|(c\cdot1)$なので練習問題7.1により$p_1p_2\cdots p_m|c$だから、$c=c'p_1p_2\cdots p_m$とかける。$q_1\nmid p_1p_2\cdots p_m$だから定理7.2により$q_1|c'$。以降$q_2,\cdots, q_n$について練習問題7.1と同様に繰り返して$q_1q_2\cdots q_n|c'$。故に$c'=c''q_1q_2\cdots q_n$となるから、$c=c''p_1p_2\cdots p_mq_1q_2\cdots q_n=c''ab$なので$ab|c$。

7.3
(a)
$n=1$のとき$n(n+1)/2=1$だから成立。$n>1$に対して$1+2+\cdots+(n-1)+n=(n-1)n/2+n=n(n+1)/2$。

(b)
$n=1$のとき$n(n+1)(2n+1)/6=1=1^2$だから成立。$n>1$に対して$1^2+2^2+\cdots+(n-1)^2+n^2=(n-1)n[2(n-1)+1]/6+n^2=n(n+1)(2n+1)/6$。

(c)
$n=0$のとき$(1-a^{n+1})/(1-a)=1$だから成立。$n>0$に対して$1+a+a^2+\cdots+a^n=(1-a^n)/(1-a)+a^n=(1-a^{n+1})/(1-a)$。

(d)
$n=2$のとき$(n-1)/n=1/2$だから成立。$n>2$に対して$1/(1\cdot2)+\cdots+1/[(n-2)(n-1)]+1/[(n-1)n]=(n-2)/(n-1)+1/[(n-1)n]=(n-1)/n$。

7.4
まー大体の話でいいと思うので、$\mathbb{E}$を公理的に構成するとか、$\mathbb{N}$によらずに証明するとかってのは、ここでは要求されてないよね多分。

(a)(b)
$\mathbb{E}$は$n\in\mathbb{N}$として$4n$か$4n+2$の形の数から構成される。$4n$の形の数は$2\cdot2n$というように$2,2n\in\mathbb{E}$の積に分解できるので$\mathbb{E}$素数でない。$4n+2$の形の数は$\mathbb{N}$において$p_1,\cdots,p_m$を奇素数として$2p_1\cdots p_m$と一意に分解され、偶数$\times$偶数の形になりえないからすべて$\mathbb{E}$素数。

(c)
2通りの分解を与える最小の数:$36=2\cdot18=6\cdot6$
3通りの分解を与える最小の数:$180=2\cdot90=6\cdot30=10\cdot18$
4通りの分解を与える最小の数:$360=2\cdot2\cdot90=2\cdot6\cdot30=2\cdot10\cdot18=6\cdot6\cdot10$

(d)
$e$を1つの$\mathbb{E}$素数として$2^ne$ ($n\geq0$)の形の数。

7.5
(a)
5,9,13,17,21,29

(b)
$441=9\cdot49=21\cdot21$

7.6
(b)
$1000000=2^{6}\cdot 5^{6}$
$1000001=101\cdot 9901$
$1000002=2\cdot 3\cdot 166667$
$1000003=1000003$
$1000004=2^{2}\cdot 53^{2}\cdot 89$
$1000005=3\cdot 5\cdot 163\cdot 409$
$1000006=2\cdot 7\cdot 71429$
$1000007=29\cdot 34483$
$1000008=2^{3}\cdot 3^{2}\cdot 17\cdot 19\cdot 43$
$1000009=293\cdot 3413$
$1000010=2\cdot 5\cdot 11\cdot 9091$
$1000011=3\cdot 333337$
$1000012=2^{2}\cdot 13\cdot 19231$
$1000013=7\cdot 373\cdot 383$
$1000014=2\cdot 3\cdot 166669$
$1000015=5\cdot 200003$
$1000016=2^{4}\cdot 62501$
$1000017=3^{2}\cdot 23\cdot 4831$
$1000018=2\cdot 500009$
$1000019=47\cdot 21277$
$1000020=2^{2}\cdot 3\cdot 5\cdot 7\cdot 2381$
$1000021=11\cdot 90911$
$1000022=2\cdot 107\cdot 4673$
$1000023=3\cdot 333341$
$1000024=2^{3}\cdot 125003$
$1000025=5^{2}\cdot 13\cdot 17\cdot 181$
$1000026=2\cdot 3^{4}\cdot 6173$
$1000027=7\cdot 19\cdot 73\cdot 103$
$1000028=2^{2}\cdot 250007$
$1000029=3\cdot 31\cdot 10753$
$1000030=2\cdot 5\cdot 100003$

シルヴァーマン 「はじめての数論」第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)
...

2015-10-01

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

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

5.1
(a) 15
(b) 3

5.3
$r_n$ ($n\ge0$)は自然数を$r_{n-1}$で割った剰余なので$r_{n-1}>r_n$である。$a<b$であることがありうるので互除法の最初の1ステップのみ$q_1\ge0$だが、以降のステップでは$r_{m-1}<r_{m-2}$ ($m\ge2$)より$q_m\ge1$。これらの不等式を用いて$i\ge0$について\[r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}\]だから、\[r_{i+2}<\frac{1}{2}r_i\]

5.4
(a)(b)
(i) $m=8$, $n=12$に対し$\mathrm{LCM}(m,n)=24$, $\gcd(m,n)=4$
(ii) $m=20$, $n=30$に対し$\mathrm{LCM}(m,n)=60$, $\gcd(m,n)=10$
(iii) $m=51$, $n=68$に対し$\mathrm{LCM}(m,n)=204$, $\gcd(m,n)=17$
(iv) $m=23$, $n=18$に対し$\mathrm{LCM}(m,n)=414$, $\gcd(m,n)=1$

$mn=\mathrm{LCM}(m,n)\gcd(m,n)$と予想される。

(c)
$\gcd(m,n)=d$とすると、$m=dm', n=dn'$ ($\gcd(m',n')=1$)と書ける。このとき$\mathrm{LCM}(m,n)=dm'n'$である:$m|dm'n'$, $n|dm'n'$は明らかだから、$dm'n'$は$m,n$の公倍数。$m,n$の公倍数$L$について、$m|L$より$L=dm'p$とかける。$n|L$でもあるから、$n'|m'p$だが、$m'$と$n'$は互いに素だから$n'|p$でなければならないので$p=n'p'$。これより$L=dm'n'p'$だから$dm'n'|L$。よって$dm'n'$は$m,n$のすべての公倍数の約数なので、すべての公倍数の中で最小のものだから、$\mathrm{LCM}(m,n)=dm'n'$。
以上により$mn=dm'dn'=dm'n'\cdot d=\mathrm{LCM}(m,n)\gcd(m,n)$。

(d)
$\gcd(301337,307829)=541$より、$\mathrm{LCM}(301337,307829)=301337\cdot307829/541=171460753$。

(e)
$m=18m'$,$n=18n'$とすれば(c)より$18m'n'=720$だから$m'n'=40$かつ$\gcd(m',n')=1$。これを満たす40の約数の組は(1,40)と(5,8)の2つなので、$(m,n)$として(18,720)または(90,144)。

5.5
数論の未解決問題''Collatz問題''。常に停止するかどうかは未解決だが、停止しない例は見つかっていない。
(a)
(i) 値1, 長さ8
(ii) 値1, 長さ10
(iii) 値1, 長さ107

(b)
$n=10000$まで調べた範囲では、常に停止し、繰り返しは1,4,2,1,4,2,1,4,2,1...である。

(c)
$n=8k+4$から始めても$n+1=8k+5$から始めても、アルゴリズムの3回めの動作で$6k+4$となるので、$L(n)=3+L(6k+4)=L(n+1)$。

(d)
$n=128k+28=8(16k+3)+4$だから、(c)により$L(n)=L(n+1)$。$n$から始めると、アルゴリズムの7回目の動作で$216k+52=8(27k+6)+4$となり、$n+2$から始めると7回目の動作で$216k+53=8(27k+6)+5$となるから、(c)により$L(n)=7+L(216k+52)=7+L(216k+53)=L(n+1)$。以上により$L(n)=L(n+1)=L(n+2)$。

(e)
(i)
$n=16k+2$から始めるとアルゴリズムの2回めの動作で$24k+4=8\cdot3k+4$となり、$n+1$から始めると2回めの動作で$24k+5=8\cdot3k+5$となるので、(c)により$L(n)=2+L(24k+4)=2+L(24k+5)=L(n+1)$

(ii)
$n=32k+22$から始めるとアルゴリズムの2回めの動作で$48k+34=16(3k+2)+2$となり、$n+1$から始めると2回めの動作で$48k+35=16(3k+2)+3$となるので、(e)(i)により$L(n)=2+L(48k+34)=2+L(48k+35)=L(n+1)$

(iii)
$n=64k+14$から始めるとアルゴリズムの2回めの動作で$96k+22=32\cdot3k+22$となり、$n+1$から始めると2回めの動作で$96k+23=32\cdot3k+23$となるので、(e)(ii)により$L(n)=2+L(96k+22)=2+L(96k+23)=L(n+1)$

(iv)
$n=128k+94$から始めるとアルゴリズムの2回めの動作で$192k+142=64(3k+2)+14$となり、$n+1$から始めると2回めの動作で$192k+143=64(3k+2)+15$となるので、(e)(iii)により$L(n)=2+L(192k+142)=2+L(192k+143)=L(n+1)$

(c)と(i)〜(iv)のパターンは以下にまとめられる:
ある$i\ge3$, $0<a_i<2^{i-1}$ (ただし$j\ge0$として$a_i=3j+l_i$, $l_i=$ 1 ($i$が偶数のとき) or 2 ($i$が奇数のとき))と、任意の$k\ge1$について\[n^{(i)}_k=2^ik+2a_i\]が$L(n^{(i)}_k)=L(n^{(i)}_k+1)$を満たすなら、\[n^{(i+1)}_k=2^{i+1}k+2a_{i+1}\]も任意の$k\ge1$について$L(n^{(i+1)}_k)=L(n^{(i+1)}_k+1)$を満たす。ただし、\[a_{i+1}=\frac{1}{3}(2^im_{i+1}+2a_i-1)\]\[  m_i=\left\{\begin{array}{cc} 0& \mbox{($i$が偶数のとき)}\\2& \mbox{($i$が奇数のとき)}\end{array}\right.\]

(証明)
まず、$\lambda\ge0$として\[2^i=\left\{\begin{array}{cc} 3\lambda+1& \mbox{($i$が偶数のとき)}\\3\lambda+2& \mbox{($i$が奇数のとき)}\end{array}\right.\]であることを示す。実際、$i=0$について$2^i=1=3\cdot0+1$で、$2^i=3\lambda+1$なら$2^{i+1}=2\cdot2^i=3\cdot(2\lambda)+2$、また$2^i=3\lambda+2$なら$2^{i+1}=3(2\lambda+1)+1$となる。
これを用いて、$a_{i+1}=(2^im_{i+1}+2a_i-1)/3$が奇数であることを示す。$i$が偶数なら$2^im_{i+1}+2a_i-1=2(3\lambda+1)+2(3j+1)-1=3[2(\lambda+j)+1]$なので$a_{i+1}=2(\lambda+j)+1$は奇数。$i$が奇数なら$2^im_{i+1}+2a_i-1=2(3j+2)-1=3(2j+1)$なので$a_{i+1}=2j+1$は奇数。
さて、\[n^{(i+1)}_k=2^{i+1}k+2a_{i+1}\]は偶数なので、$(3n+1)$アルゴリズムを1回行って
\[2^ik+a_{i+1}\]$a_{i+1}$は奇数なのでこれも奇数だから、さらにもう1回行って整理すれば、\[3(2^ik+a_{i+1})+1=2^i(3k+m_{i+1})+2a_i=n^{(i)}_{3k+m_{i+1}}\]となるので、$L(n^{(i+1)}_k)=2+L(n^{(i)}_{3k+m_{i+1}})$。
また\[n^{(i+1)}_k+1=2^{i+1}k+2a_{i+1}+1\]は奇数なので、$(3n+1)$アルゴリズムを1回行って\[2^{i+1}\cdot3k+6a_{i+1}+4\]これは偶数だからさらにもう1回行って整理すれば、\[2^i\cdot3k+3a_{i+1}+2=2^i(3k+m_{i+1})+2a_i+1=n^{(i)}_{3k+m_{i+1}}+1\]となるので、$L(n^{(i+1)}_k+1)=2+L(n^{(i)}_{3k+m_{i+1}}+1)$。
仮定により$L(n^{(i)}_{3k+m_{i+1}})=L(n^{(i)}_{3k+m_{i+1}}+1)$だから、$L(n^{(i+1)}_k)=L(n^{(i+1)}_k+1)$となる。(証明終)

(c)の$8k+4$が$i=3, a_3=2=3\cdot0+2$で上の条件を満たすので、$L(n)=L(n+1)$となる一つの系列として、$n=8k+4$, $16k+2$, $32k+22$, $64k+14$, $128k+94$, $256k+62$, $512k+382$, ...が得られる。
(d)の$128k+28$についてもいろいろ言えると思うが、面倒なのでパス。

2015-09-30

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

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

4.2
(a)
(9,18,81)
(28,84,784)
(70,105,1225)
(65,260,4225)
:
:
なおこのタイプの解では(1,2,3)は直接見つけられない。

(b)
$(n^2A)^3+(n^2B)^3=n^6(A^3+B^3)=n^6C^2=(n^3C)^2$。

(c)
(1,2,3)
(2,2,4)
(7,21,98)
(70,105,1225)
(65,260,4225)
(273,364,8281)
(14,70,588)
:
:

(d)
$2a^3=c^2$だから、$c$は偶数なので$c^2$は4の倍数。$2a^3$が4の倍数だから$a$は偶数となるので、$a=2j$ ($j\ge1$)とおけば$4^2j^3=c^2$。これより$c$も4の倍数だから、$c=4i$ ($i\ge1$)とおけば$j^3=i^2$である。平方数かつ立方数である自然数は、ある$n\ge1$について$n^6$と書け、$j=n^2$, $i=n^3$。したがって$a=2n^2$, $c=4n^3$。逆に$a=2n^2$, $c=4n^3$ ($n\ge1$)は明らかに(*)を満たすので、$a=b=2n^2$, $c=4n^3$が$a=b$となるすべての解である。$n=1$に対する(2,2,4)を除き、$a=b$となる解は既約ではない。

(e)
例えば
(15561,17290,2989441)
(14744,20273,3396649)
(14497,24852,4289041)

2015-05-23

コブリッツ「楕円曲線と保型形式」 第1章§1.2の演習問題

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

1. 巻末ヒントの通り$y\to y/n^2$, $x\to x/n$

2.
(a) $v=t(u+1)$ ($u\ne-1$)を$u^2+v^2=1$に代入して整理すれば、$[(1+t^2)u-(1-t^2)](u+1) =0$だから$u=(1-t^2)/(1+t^2), v=2t/(1+t^2)$

(b) $n=XY/2=Z^2uv/2$より$n/Z^2=uv/2=t(1-t^2)/(1+t^2)^2$

(c) 点$(-t, (1+t^2)/Z$について、(b)により$(-t)^3-(-t) =t(1-t^2) =n[(1+t^2)/Z]^2$だから、この点は$ny^2=x^3-x$上にある。したがって演習問題1により$(-nt, n^2(1+t^2)/Z)$は$y^2=x^3-n^2x$上にある。

$X/Z=(1-t^2)/(1+t^2)$を$t^2$について解いて\[t^2=\frac{\displaystyle Z-X}{\displaystyle Z+X}\]なので\[1+t^2=\frac{\displaystyle 2Z}{\displaystyle Z+X}\]これより\[y=\frac{\displaystyle 2n^2}{\displaystyle Z+X}\]また\[\frac{\displaystyle x}{\displaystyle y}=-\frac{\displaystyle Zt}{\displaystyle n(1+t^2)} =-\frac{\displaystyle Y}{\displaystyle 2n}\]だから、\[x=-\frac{\displaystyle nY}{\displaystyle Z+X}\]

(d) 命題1.2との辻褄がわからない・・・。

(e) (c)の結果を用いて、巻末ヒントの通りの表を得る。

3.
(a)
$X$と$Y$の間の角を$\theta$、$A=\cos\theta, B=\sin\theta$とする。$n=BXY/2$、また余弦定理により$Z^2=X^2+Y^2-2AXY$である。命題1.1の証明と同様にして、\[\left(\frac{\displaystyle X\pm Y}{\displaystyle 2}\right)^2=\left(\frac{\displaystyle Z}{\displaystyle 2}\right)^2+\frac{\displaystyle n(A\pm1)}{\displaystyle B}\tag{1}\]なので、(1)の複号$+$の式と$-$の式を辺々かけて、$u=Z/2, v=(X^2-Y^2)/2$とし、$A^2+B^2=1$より$-B^2=(A+1)(A-1)$も用いれば\[v^2=u^4+\frac{\displaystyle 2nA}{\displaystyle B}u^2-n^2\tag{2}\]§1.2冒頭と同様に$x=u^2, y=uv$として、求める3次方程式\[y^2=x^3+\frac{\displaystyle 2nA}{\displaystyle B}x^2-n^2x\tag{3}\]を得る。

(b)
(a)の(3)式において、演習問題1の逆変換$y\to n^2y$, $x\to nx$を行えば、\[ny^2=x^3+\frac{\displaystyle 2A}{\displaystyle B}x^2-x\tag{4}\]である。$\lambda=B/(A+1)$なので、\[-\lambda+\frac{\displaystyle 1}{\displaystyle \lambda}=\frac{\displaystyle 2A}{\displaystyle B}\tag{5}\]だから、(4)は\[ny^2=x(x-\lambda)\left(x+\frac{\displaystyle 1}{\displaystyle \lambda}\right)\tag{6}\]となる。

2015-05-14

コブリッツ「楕円曲線と保型形式」 第1章§1.1の演習問題

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

1. Silverman (2006)の第2章に証明がある。

2.

3.
(a) 1が合同数と仮定すると、\[X^2+Y^2=Z^2\tag{1}\]\[XY=2\tag{2}\]を同時に満たす$X,Y,Z\in\mathbb{Q}$が存在する。(1)$\pm$2$\times$(2)から\[(X\pm Y)^2=Z^2\pm4\tag{3}\]これらの両辺の積をとって\[(X^2-Y^2)^2=Z^4-2^4\tag{4}\]$X,Y,Z$の分母の最小公倍数を$l$とし、(4)の両辺に$l^4$をかければ\[[(lX)^2-(lY)^2]^2=(lZ)^4-(2l)^4\tag{5}\]で、$lX,lY,lZ\in\mathbb{N}$だから、方程式$x^4-y^4=u^2$は整数解$x=lZ, y=2l, u=(lX)^2-(lY)^2$を持つ。

(1)の両辺に$l^2$をかければ\[(lX)^2+(lY)^2=(lZ)^2\tag{6}\]なので$lX,lY,lZ$はPythagoras数。

$X=n_{x}/d_{x}$, $Y=n_{y}/d_{y}$ , $Z=n_{z}/d_{z}$($\text{gcd}(n_{x},d_{x})= \text{gcd}(n_{y},d_{y})= \text{gcd}(n_{z},d_{z})=1$)とする。1.1節冒頭の平方因子の議論と同様に、$n_{x},n_{y},n_{z}$に共通因子があれば、$XY\in\mathbb{N}$は平方因子を持つ。が、これは$XY=2$と矛盾する。故に$n_{x},n_{y},n_{z}$に共通因子はない。

$Y=2/X=2d_{x}/n_{x}$において、$n_{x}$が素因子2を含むなら、$d_{x}$は素因子2を含まない。$n_{x}=2n'_{x}$として$n_{y}=d_{x}, d_{y}=n'_{x}$なので、$\text{gcd}(d_{x},d_{y})=\text{gcd}(d_{x},n'_{x})=1$。$n_{x}$が素因子2を含まないなら、$n_{y}=2d_{x}, d_{y}=n_{x}$なので、$\text{gcd}(d_{x},d_{y})= \text{gcd}(d_{x},n_{x})= 1$となり、いずれにせよ$\text{gcd}(d_{x},d_{y})= 1$である。\[Z^2=X^2+Y^2=\frac{\displaystyle{n_{x}^{2}d_{y}^{2}+n_{y}^{2}d_{x}^{2}}}{\displaystyle{d_{x}^2d_{y}^2}}\]で、$d_{z}^{2}$は分母$d_{x}^{2}d_{y}^{2}$を分子$n_{x}^{2}d_{y}^{2}+n_{y}^{2}d_{x}^{2}$と約分して現れるから、$d_{z}|(d_{x}d_{y})$となる。以上のことから$l=d_{x}d_{y}$。

$d_{x}d_{y}/d_{z}=m\in\mathbb{N}$とすると、(6)は\[n_{x}^2+n_{y}^2=(mn_{z})^2\tag{7}\]である。$n_{x},mn_{z}$が共通の素因子$g\ge2$をもてば、
\[n_{y}^{2}=(mn_{z})^{2}-n_{x}^2\tag{8}\]が素因子$g$をもつ。したがって$g|n_{y}$となるから$\text{gcd}(n_{x},n_{y})\ge g$となり、$n_{x},n_{y}$に共通因子がないことと矛盾する。故に$\text{gcd}(n_{x},mn_{z})=1$、同様に$\text{gcd}(n_{y},mn_{z})=1$だから、$n_{x},n_{y},mn_{z}$は原始Pythagoras数。よって$n_{x},n_{y}$の偶奇は互いに逆だから$u= (lX)^2-(lY)^2= n_{x}^2-n_{y}^2$は奇数。

(b) (問題文の「フェルマーの最終定理はその系である」は「フェルマーの最終定理の系である」の誤訳(google booksで一部見られる原書で確認))。
$x^4=u^2+y^2$とみても、巻末ヒントにあるHardy & Wright (1960) 13.3節のような降下法の議論にもっていけない・・・。

4.
固定された$n\in\mathbb{N}$に対し、同一の$x$を与える2つの正の有理数の3つ組$(X,Y,Z), (X',Y',Z')$があったとすると、命題1.1の証明で既に示されたことから$4x= Z^2= Z'^2$より$Z= Z'$。また\[(X\pm Y)^2=4x\pm4n\]\[(X'\pm Y')^2=4x\pm4n\]なので複号$+$の式を辺々引いて整理すれば\[(X+Y)^2=(X'+Y')^2\]これより\[(X-X')+(Y-Y')=0\tag{1}\]同様に複号$-$の式から\[(X-X')-(Y-Y')=0\tag{2}\](1)(2)から$X=X', Y=Y'$を得る。

5.
(a) $n=5$に対し、$X=3/2, Y=20/3, Z=41/6$なので、命題1.1から$x=41^2/12^2=1681/144$。

(b) $n=6$に対し、$X=3, Y=4, Z=5$なので、命題1.1から$x =5^2/2^2 =25/4$。

(c) 計算機で探索して、分母・分子が100以下の有理数の中では$x =29^2/2^2 =841/4, x =37^2/2^2 =1369/4$が見つかる。

6.
(a) $p(x,y,z) =2x^2+y^2+32z^2$, $q(x,y,z) =2x^2+y^2+8z^2$とする。$n =2x^2+y^2+32z^2 =2x^2+y^2+8(2z)^2$なので、整数の3つ組$(x,y,z) =(a,b,c)$について、$n =p(a,b,c)$と$n =q(a,b,2c)$は同値。

Tunnelの定理(B)が成り立つとすると、$n =p(x,y,z)$となる$(x,y,z)$が$N$個あるとすれば、
$n =q(x,y,z)$となる$(x,y,z)$は$2N$個ある。$n =q(x,y,z)$となる$(x,y,z)$のうち、$z$が偶数であるものは、$N$個なので、$z$が奇数のものも$2N-N =N$個。よって$n =q(x,y,z)$となる$(x,y,z)$のうち$z$が奇数であるものと、$z$が偶数であるものの数は等しい。

(b)

7.
(a) 巻末ヒントにより、$n \equiv5 \text{ or } 7 \pmod{8}$なら、$n=2x^2+y^2+8z^2$を満たす整数の3つ組$(x,y,z)$は存在しないので、$z$が偶数の3つ組と奇数の3つ組は共に0個だから、演習問題6(a)によりTunnelの定理(B)の条件が満たされる。

(b) 41

(c) 演習問題2を使って計算機で原始Pythagoras数を探索すると、1500番目くらいに合同数41を与える組$(123/20, 40/3, 881/60)$が見つかる。