平方数に関する問題１ - k56737kagawa’s blog

[問題１] $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$ の場合のみである。