2020-04-01

ぺル方程式の問題

[問題]　 $D$ を素数の平方を因数にもたない正の整数とする。
このとき $p^2-D q^2= \pm 1$ を満たす正の整数 $p,q$ を求めよ。

この問題はぺル方程式の問題とよばれている。実際にはぺルは無関係で、

研究したのは主にオイラーである。ぺル方程式の一般解は、「最小解」を求めることで全て求めることができる。ぺル方程式の「最小解」とは、 $p+q\sqrt{D}$ の値が最小となる正の整数 $p,q$ のこととする。解が存在すれば、最小解も存在することが分かる。

[命題１]　 $p^2-D q^2= 1$ の最小解を $p_0,q_0$ とする。

他の解を $p,q$ とすると、ある整数 $k$ が存在して、 $p+q\sqrt{D}=(p_0 + q_0 \sqrt{D})^k$ を満たす。

（証明）最小解の性質から、

$(p_0 + q_0 \sqrt{D})^k \leqq p+q\sqrt{D}$ $\lt(p_0 + q_0 \sqrt{D})^{k+1}$ を満たす整数 $k$ が存在する。

したがって、 $1 \leqq \displaystyle\frac{p+q\sqrt{D}}{(p_0 + q_0 \sqrt{D})^k}$ $\lt$ $p_0 + q_0 \sqrt{D}$ となる。

ノルムを $N(p+q\sqrt{D})=p^2-D q^2$ で定めると、ブラーマグプタの恒等式を使って $N(xy)=N(x)N(y)$ が成り立つ。

ブラーマグプタの恒等式から、 $\displaystyle\frac{p+q\sqrt{D}}{(p_0 + q_0 \sqrt{D})^k} = a+b \sqrt{D}$ となる整数 $a,b$ が存在することも分かる。

$N(a+b \sqrt{D}) = 1$ となるが、 $p_0,q_0$ が最小解であると仮定しているので、 $a+b \sqrt{D} = 1$ でなければならない。よって、 $p+q\sqrt{D}=(p_0 + q_0 \sqrt{D})^k$ が成り立つ。（終）

◇連分数展開のアルゴリズム

$\sqrt{D}$ の整数部分を $a_0$ とする。

$A_0=a_0$ , $B_0=D-A_0^2$ , $x_0=\displaystyle\frac{\sqrt{D}+A_0}{B_0}$ とおく。

$x_0$ の整数部分を $a_1$ とする。

$A_1=a_1 B_0 - A_0$ , $B_1=1+a_1 (A_0 - A_1)$ , $x_1=\displaystyle\frac{\sqrt{D}+A_1}{B_1}$ とおく。

$n \geqq 2$ について、

$x_{n-1}$ の整数部分を $a_n$ とする。

$A_n=a_n B_{n-1} - A_{n-1}$ , $B_n=B_{n-2}+a_n (A_{n-1} - A_n)$ , $x_n=\displaystyle\frac{\sqrt{D}+A_n}{B_n}$ とおく。

[Lemma]

$a_n,A_n,B_n$ は正の整数である。
$0 \leqq \displaystyle\frac{1}{x_n} \leqq 1$
$D-A_n^2 =B_n B_{n-1}$
$\sqrt{D} \lt A_n + B_n$
$\sqrt{D}=a_0+\displaystyle\frac{1}{a_1+\displaystyle\frac{1}{a_2+ \cdots }}$

[系] $\sqrt{D}$ に対して $x_n,a_n,A_n,B_n$ の候補は有限個である。

[定理１] $x_0=\displaystyle\frac{1}{\sqrt{D}-A_0}$ を連分数展開すると、 $x_N=x_0$ を満たす $N$ >0 が存在する。すなわち連分数が「循環」する。

$a_0+\displaystyle\frac{1}{\cdots +\displaystyle\frac{1}{a_n}}=\displaystyle\frac{p_n}{q_n}$ と表すことにする。（ $p_n,q_n$ は正の整数）

これを $n$ 階近似分数とよぶことにする。このとき、
$\displaystyle\frac{p_{n+1}}{q_{n+1}}=\displaystyle\frac{a_{n+1}p_{n}+p_{n-1}}{a_{n+1}q_{n}+q_{n-1}}$ が成り立つ。（ $n \geqq 1$ ）

[Lemma] $C_n=p_n^2-Dq_n^2 , E_n=p_n p_{n-1} - D q_n q_{n-1}$ とおく。
このとき、 $C_n=(-1)^{n+1}B_n ,E_n=(-1)^n A_n$ 　が成り立つ。

[定理2] $p^2-Dq^2=1$ を満たす正の整数 $p,q$ が存在する。
（証明） $x_0=x_N$ となる $N \geqq 1$ が存在するので、正の整数 $n$ について $x_n=x_{n+N}$ が成り立つ。
$A_0=A_N,B_0=B_N$ であるから、 $D-A_N^2=B_N B_{N-1}$ と $D-A_0^2=B_0$ より、 $B_{N-1}=1$ となる。したがって、
$p_{N-1}^2-Dq_{N-1}^2=(-1)^N B_{N-1}=(-1)^N$
なので、 $N$ が奇数であれば、 $p_{N-1}^2-Dq_{N-1}^2=(-1)^N B_{N-1}=-1$ の解が存在する。
また、 $x_0=x_{2N}$ より、 $B_{2N-1}=1$ であるから、
$p_{2N-1}^2-Dq_{2N-1}^2=(-1)^{2N} B_{2N-1}=1$ となる。（終）

2020-03-29

平方根の連分数

$\sqrt{n}=a+\displaystyle\frac{1}{\sqrt{1+\displaystyle\frac{1}{\sqrt{1+\frac{1}{b}}}}}$ を満たす正の整数 $n,a,b$ を求めよう。

$x=\sqrt{n}-a$ とおく。 $\displaystyle\frac{1}{x^2}=1+\displaystyle\frac{1}{\sqrt{1+\frac{1}{b}}}$ より、 $(\displaystyle\frac{1}{x^2}-1)^2=\displaystyle\frac{b}{b+1}$ となるので、 $c=b+1,y=\displaystyle\frac{1}{x^2}$ とおくと、 $y^2-2y+\displaystyle\frac{1}{c}=0$ となる。

$\alpha=\sqrt{n}-a , \beta=-\sqrt{n}-a$ とおくと、 $y^2-2y+\displaystyle\frac{1}{c}=0$ の解は、 $\displaystyle\frac{1}{\alpha^2},\displaystyle\frac{1}{\beta^2}$ と表せる。解と係数の関係より、 $\displaystyle\frac{1}{\alpha^2}+\displaystyle\frac{1}{\beta^2}=2$ 、 $\displaystyle\frac{1}{\alpha^2} \displaystyle\frac{1}{\beta^2}=\displaystyle\frac{1}{c}$ より、 $\displaystyle\frac{4a^2-2(a^2-n)}{c}=2$ となるので、 $a^2+n=c=(a^2-n)^2$ を得る。この式を $n$ についての2次方程式とみると、判別式 $D=8a^2 +1$ は平方数 $k^2$ となる。

$k^2=8a^2 +1$ はぺル方程式なので、別の節で解説する。

2020-03-28

整数解の問題

$a\sqrt{b}=\sqrt{a*10^N+b}$ を満たす正の整数 $a,b,N$ を求めよう。

$a^2 b=a*10^N+b$ を $a$ についての2次方程式とみる。判別式 $D=10^{2N}+4b^2$ は平方数 $c^2$ となる必要がある。

ピタゴラスの三つ組は一般に、 $k(m^2-n^2),2kmn,k(m^2+n^2)$ で表すことができる。したがって、

$10^N=k(m^2-n^2)$

$2kmn=2b$

$k(m^2+n^2)=c$

として、解の公式より、 $a=\displaystyle\frac{10^N \pm c}{2b}=\frac{k(m^2-n^2) \pm k(m^2+n^2)}{2kmn}=\displaystyle\frac{m}{n},\displaystyle\frac{-n}{m}$ となる。

$a$ は正の整数なので、 $a=\displaystyle\frac{m}{n}$ である。 $m=an$ より、 $10^N=k((an)^2-n^2)=kn^2(a^2-1)$ となるので、 $a^2-1=2^x 5^y$ と表せる。

$a^n-1=p^m$ を満たす２以上の正の整数 $a,n,p,m$ ( $p$ は素数)は、 $3^2-1=2^3$ のみである。はてなブログでTeX - k56737kagawa’s blog

したがって $x$ は正である。

$a+1,a-1$ の最大公約数は $1,2$ のいずれかである。 $a+1,a-1$ が互いに素のとき、 $a^2-1=2^x 5^y$ より、 $a+1+a-1=2^x+5^y$ となって矛盾する。

$a+1,a-1$ の最大公約数は $2$ である。以下の場合を考えればよい。

　 $a+1=2^{x-1} 5^y$ かつ $a-1=2$ 　この場合 $a=3$
　 $a+1=2*5^y$ かつ $a-1=2^{x-1}$ 　この場合 $a=9$
　 $a-1=2*5^y$ かつ $a+1=2^{x-1}$ 　この場合は解なし

答えは２つしかない。

$3 \sqrt{375}=\sqrt{3375}$ と $9 \sqrt{1125}=\sqrt{91125}$ である。

2020-03-19

平方数に関する問題１

[問題１] $A^2+B^2=10^n A+B$ を満たす正の整数 $A,B,n$ を求めよ。

簡単に見つかる解は、 $A=10^n$ と $B=1$ である。従ってこれ以外の解を見つけることが目標である。

問題1の解が見つかったとする。

$\displaystyle\frac{A}{B}$ を既約分数で $\displaystyle\frac{a}{b}$ と表すと、 $\displaystyle{\frac{A}{B}=\frac{B-1}{10^n-A}}$ より、正の整数 $x,y$ で、 $A=ax,B=bx,B-1=ay,10^n-A=by$ を満たす数が存在する。

このとき、 $ax+by=10^n,bx-ay=1$ より、 $(ax+by)^2+(bx-ay)^2=10^{2n}+1$ となるが、ディオファントスの恒等式 $(a^2+b^2)(x^2+y^2)=(ax+by)^2+(bx-ay)^2$ により、 $10^{2n}+1$ は合成数であり、分解されたそれぞれの数もまた平方数の和で表すことができる。従って問題1の解は $10^{2n}+1$ の約数を調べることで見つけることができる。

[解の探索方法]

$\displaystyle\frac{1}{p}$ を循環小数で表す。( $p=a^2+b^2$ と仮定する。)
循環節の長さが $4n$ の場合について考える。
$\displaystyle\frac{1}{p}=\displaystyle\frac{M}{10^{4n}-1}$ より、 $p$ は $10^{2n}+1$ の素因数である。
$x=\displaystyle\frac{a*10^n + b}{a^2+b^2}$ と $y=\displaystyle\frac{b*10^n - a}{a^2+b^2}$ が整数であれば、 $A=ax,B=bx$ と $A=by,B=bx$ が解である。

(例) $p=17=4^2+1^2$ について、

$\frac{1}{p}$ を計算すると、0.0588235294117647･･･という循環小数が得られる。

$588235294117647÷(10^8-1)=5882353$ となり、 $5882353*17=10^8+1$ である。

$x=\frac{4*10^4+1}{4^2+1^2}=2353$ により、 $A=9412,B=2353$ が解として得られる。また、 $y=\frac{1*10^4-4}{4^2+1^2}=588$ により、 $A=by=588,B=bx=2353$ も解の条件を満たす。ちなみに、 $5882353$ は素数である。

[定理]　[問題1]の解となる $A*10^n+B$ が素数となるのは、 $B$ が $n$ 桁と仮定すると、 $101$ と $5882353$ のみである。

(証明)

$A*10^n+B$ が素数となるのであれば、 $A,B$ は互いに素である。 $A(10^n-A)=B(B-1)$ より、 $B-1=Az$ となる整数 $z$ が存在する。このとき、 $10^n-A=Bz$ となる。 $(A^2+B^2)(1+z^2)=(A+Bz)^2+(Az-B)^2=10^{2n}+1$ より、 $A^2+B^2$ は $10^{2n}+1$ の約数となる。 $A*10^n+B$ が $10^{2n}+1$ の約数となるので、 $B$ は $10$ の倍数にならず、 $B$ が $n$ 桁であることから、 $10^{n-1} \lt B \lt 10^n$ である。よって、 $10^{n-1} \leqq B-1 \lt 10^n$ となるので、 $10^{2n-2} \lt B(B-1) \lt 10^{2n}$ ･･･(1)が成り立つ。

$z=0$ のとき、 $B=1,n=1,A=10$ より、この場合は素数 $101$ が得られる。

また、 $z \geqq 1$ のとき、 $B \leqq Bz=10^n-A$ より、 $10^{n-1} \lt 10^n-A \lt 10^n$ ･･･(2)が成り立つ。

(1)(2)より、 $10^{n-2} \lt \displaystyle\frac{B(B-1)}{10^n-A} \lt 10^{n+1}$ が成り立つので、 $10^{n-2} \lt A \lt 10^{n+1}$ となる。 $10^{2n-2} \lt A*10^n \lt A*10^n+B=A^2+B^2=\displaystyle\frac{10^{2n}+1}{1+z^2}$ となるので、 $1+z^2 \lt \displaystyle\frac{10^{2n}+1}{10^{2n-2}} \leqq 101$ を得る。従って $z \leqq 9$ である。

$1+z^2$ は、 $10^{2n}+1$ の約数となるので、 $z$ は偶数であり、 $1+z^2$ は $5$ の倍数ではない。このような条件を満たす $z$ は、 $z=4,6$ である。

$z=6$ とする。 $p=37$ である。 $10^{2n}+1 \equiv 0$ (mod $37$ )　と仮定すると、 $10^3 \equiv 1$ (mod $37$ )より、 $4n$ は $3$ の倍数となる。従って $n$ は $3$ の倍数となり、 $10^{n}-1 \equiv 0$ (mod $37$ )となるので、矛盾する。

$z=4$ とする。 $p=17$ である。 $10^{2n}+1 \equiv 0$ (mod $17$ )と仮定すると、 $10^8+1 \equiv 0$ (mod $17$ )より、 $4n$ は $16$ の倍数となる。従って、 $n$ は $4$ の倍数なので、 $n=4m$ とおく。 $10^{8m}+1 \equiv 0$ (mod $17$ )が成り立つのは、 $m$ が奇数の場合である。 $\displaystyle\frac{10^{8m}+1}{17}$ が素数となるのは $m=1$ の場合のみである。

2020-03-14

はてなブログでTeX

整数論が高校の教育課程に導入されて数年経ちます。以前から、ユークリッド互除法などを高校で教えるのも面白いかなと感じておりました。また、難関大学の入試問題には昔からよく出題されており、数学オリンピックでも必ず数問取り上げられています。
整数の問題は数を変えてしまうと全く別の問題に変化してしまいます。難易度も格段に上がります。そういう意味でも面白いジャンルではないかと感じています。
はじめに、本校の生徒から出題された問題を紹介します。

[問題１] 　 $\displaystyle\frac{2^n+1}{n^2}$ が整数になるような正の整数 $n$ を求めよ。

インターネットで調べると、「整数のマスターデーモン」と呼ばれています。

$\displaystyle\frac{2^n+1}{n^2}$ が整数なら、 $\displaystyle\frac{2^n+1}{n}$ も整数となります。
[補題]　 $\displaystyle\frac{2^n+1}{n}$ が整数ならば、 $\displaystyle\frac{2^{3n}+1}{3n}$ も整数である。
[補題]　 $\displaystyle\frac{2^n+1}{n}$ が整数ならば、 $n=1$ または $n$ は $3$ の倍数である。

[定理][問題1]の解答は $n=1,3$ の場合のみである。

証明は楽ではありませんが、挑戦してみると面白いと思います。出題してくれた生徒は「LTEの補題」を使って解いたそうです。私は知りませんでしたが、数学オリンピックでは定石の手法らしいです。
次に、私から生徒に向けて出題した問題を紹介します。難関大学の入試問題として過去に出題された問題をもとに考えました。ぜひ挑戦してみて下さい。

[問題２]　 $a^n-1=p^m$ を満たす2以上の正の整数 $a,n,m,p$ (ただし $p$ は素数)を求めよ。

私はこの問題を解くのに相当な労力と時間を費やしましたが、本校の生徒は数日で解答を作ってきました。この問題のもとになっているのは「カタラン予想」です。

[カタラン予想]　 $x^a-y^b=1$ を満たす２以上の整数 $x,y,a,b$ は、 $3^2-2^3=1$ のみである。

いまや予想ではなく、証明された定理となっています。

以下の補題は、通称「LTEの補題」と呼ばれています。
［補題］（Lifting The Exponent Lemma）

整数 $a$ が $p$ でちょうど $n$ 回割れるとき、 $n=(a{)}_p$ と表す。

$p$ が奇素数、 $x-y$ は $p$ の倍数、 $x,y$ は $p$ の倍数ではないとき、
$(x^n-y^n{)}_p=(x-y{)}_p+(n{)}_p$ が成り立つ。

この補題を使って[問題２]を解いてみましょう。

（解法）まず、 $p$ が奇素数の場合を考える。

$a$ が $3$ 以上のとき、 $(a^n-1{)}_p=(a-1{)}_p+(n{)}_p$ より、 $(n{)}_p$ は正の値をとる。

$A=a^{\frac{n}{p}}$ とおくと、 $A^p-1=p^m$ となるので、 $(A^p-1{)}_p=(A-1{)}_p+(p{)}_p$ より、 $A-1=p^{m-1}$ となる。よって、 $A^{p-1}+\cdots+A+1=p$ となるが、これは矛盾である。なぜなら、 $A$ は $3$ 以上なので、左辺は $p$ を超える。