問題021｜整数・合同式と素数

$1000=8\cdot 125$ である．$x^2\equiv 1(\mathrm{mod}8)$ の条件と，$125\mid (x-1)(x+1)$ の条件を別々に調べよ．

$x-1$ と $x+1$ の最大公約数は2の約数なので，5の因子は一方にしか現れない．したがって $x\equiv 1,-1(\mathrm{mod}125)$ であり，さらに $x$ が奇数である必要がある．

まず3で割った余りから $n$ の偶奇を決める．そのうえで $n=3^{r}m$（$m\not\equiv 0(\mathrm{mod}3)$）と置き，$A^3+1=(A+1)(A^2-A+1)$ を利用せよ．

$A\equiv -1(\mathrm{mod}3)$ ならば $A^2-A+1$ は3で割れるが9では割れない．また $m$ が奇数で $m\not\equiv 0(\mathrm{mod}3)$ ならば，$(A^m+1)/(A+1)$ は3で割れない．

(1) $(x,y)$ から $(-y,x-y)$ への変換を調べよ．(2) $2891=7^2\cdot 59$ である．まず7を法として式を調べる．

(1) 上の変換を3回行うと元に戻る．(2) $y\not\equiv 0(\mathrm{mod}7)$ ならば $t=x/y$ を7を法として考え，$t^3-3t+1$ が0にならないことを確認せよ．

そのような素数が $p_1,\dots ,p_r$ だけだと仮定し，$M=3p_1\cdots p_r$ に対して $M^2+M+1$ の素因数を調べよ．

素数 $q\mid M^2+M+1$ に対して，$M^3\equiv 1(\mathrm{mod}q)$ だが $M\not\equiv 1(\mathrm{mod}q)$ であることを示せ．$M$ のべきが初めて1になる指数が3であることから，$3\mid q-1$ を導け．

8と125は互いに素なので，条件は $x^2\equiv 1(\mathrm{mod}8)$ と $x^2\equiv 1(\mathrm{mod}125)$ の両方が成り立つことである．奇数 $x=2u+1$ の平方は $4u(u+1)+1\equiv 1(\mathrm{mod}8)$ であり，偶数の平方は1にならない．よって前者は $x$ が奇数であることと同値である．

後者について，$gcd(x-1,x+1)\mid 2$ なので，5は両因子を同時には割らない．したがって $5^3\mid (x-1)(x+1)$ ならば $125\mid x-1$ または $125\mid x+1$ である．逆も明らかである．

範囲内の $x=1+125t$ は $t=0,\dots ,7$ で，$x$ が奇数となるのは $t=0,2,4,6$ である．また $x=-1+125t$ は $t=1,\dots ,8$ で，奇数となるのは $t=2,4,6,8$ である．よって

がすべてである．

正整数 $M$ に対し，$M$ を割り切る3の最高べきの指数を $v_3(M)$ と書く．$n$ が偶数ならば $2^n+1\equiv 2(\mathrm{mod}3)$ なので不適である．以下，$n=3^{r}m$ と置き，$m$ は3で割れない奇数とする．

$A\equiv -1(\mathrm{mod}3)$ のとき，$A=-1+3t$ と書けば

となる．したがって $v_3(A^3+1)=v_3(A+1)+1$ である．$2+1=3$ を出発点として繰り返すと，$v_3(2^{3^r}+1)=r+1$ を得る．

次に $A=2^{3^r}$ と置く．$m$ は奇数なので

であり，右辺の各項は3を法として1に等しい．その和は $m\not\equiv 0(\mathrm{mod}3)$ だから，この商は3で割れない．以上から $v_3(2^n+1)=r+1$ である．

求める条件は $v_3(2^n+1)=4$，すなわち $r=3$ である．したがって $n=27m$ で，$m$ は奇数かつ3の倍数でない．答えは

を満たす正整数すべてである．

$F(x,y)=x^3-3x{y}^2+y^3$ と置く．

(1) 展開により $F(-y,x-y)=F(x,y)$ である．変換 $T(x,y)=(-y,x-y)$ は

を満たす．もし $T(x,y)=(x,y)$ ならば $x=-y,y=x-y$ から $x=y=0$ となるが，これは $F(x,y)=n>0$ に反する．また3つの組のうち2つが一致すれば，$T^3$ が恒等変換であることから $T(x,y)=(x,y)$ となる．したがって $(x,y),(-y,x-y),(y-x,-x)$ は相異なる3組の整数解である．

(2) $F(x,y)\equiv 0(\mathrm{mod}7)$ とする．もし $y\not\equiv 0(\mathrm{mod}7)$ ならば，7を法として $y$ の逆数が存在するので $t\equiv x{y}^{-1}(\mathrm{mod}7)$ と置ける．すると $t^3-3t+1\equiv 0(\mathrm{mod}7)$ である．しかし $t=0,1,2,3,4,5,6$ に対する余りはそれぞれ $1,6,3,5,4,6,3$ であり，0は現れない．よって $7\mid y$ であり，元の合同式から $7\mid x$ も従う．

したがって，$F(x,y)=2891$ を満たすならば $x=7u,y=7v$ と書け，$343F(u,v)=2891$ となる．ところが $2891=49\cdot 59$ は343で割り切れない．よって整数解は存在しない．

3で割ると1余る素数が有限個で，そのすべてが $p_1,\dots ,p_r$ であると仮定する．実際に7がこの条件を満たすので $r\ge 1$ である．$M=3p_1\cdots p_r$，$N=M^2+M+1$ と置き，$N>1$ の素因数を1つ選んで $q$ とする．$N\equiv 1(\mathrm{mod}3)$ および $N\equiv 1(\mathrm{mod}{p}_i)$ より，$q$ は3でも $p_i$ のいずれでもない．また $M\not\equiv 0(\mathrm{mod}q)$ である．

$(M-1)N=M^3-1$ より $M^3\equiv 1(\mathrm{mod}q)$ である．もし $M\equiv 1(\mathrm{mod}q)$ ならば $N\equiv 3(\mathrm{mod}q)$ となり $q=3$ を得るので，$M\not\equiv 1(\mathrm{mod}q)$ である．

フェルマーの小定理から $M^{q-1}\equiv 1(\mathrm{mod}q)$ である．$q-1=3h+s$，$s=0,1,2$ と書くと $M^s\equiv 1(\mathrm{mod}q)$ となる．$s=1$ は不可能であり，$s=2$ でも $M^3\equiv M^2\equiv 1(\mathrm{mod}q)$ から $M\equiv 1(\mathrm{mod}q)$ となって不可能である．したがって $s=0$，すなわち $q\equiv 1(\mathrm{mod}3)$ である．これは $p_1,\dots ,p_r$ 以外にも条件を満たす素数 $q$ があることを意味し，矛盾する．よってそのような素数は無数に存在する．