5882353
$A^2+B^2=10^n A+B$を満たす正の整数$A,B,n$を求めよ。
簡単に見つかる解は$A=10^n$と$B=1$である。従ってこれ以外の解を見つけることが目標である。解が見つかったと仮定する。
$A^2+B^2=10^n A +B$を変形すると$(2A-10^n)^2+(2B-1)^2=10^{2n}+1$となるが$10^{2n}+1$が素数であれば$(10^n)^2+1^2$以外の二平方和による表し方はない。合成数であればその素因数は$4n+1$の型をしており、平方和で表すことができる。ディオファントスの等式を利用すると二平方和による表現が複数可能となる。$$(a^2+b^2)(x^2+y^2)=(ax+by)^2+(ay-bx)^2=(ax-by)^2+(ay+bx)^2$$
$10^{2n}+1$は奇数なので二平方和$X^2+Y^2$で表すと、一方は偶数で他方は奇数となる。$2B-1$は正の奇数なので$2B-1=Y$としてよい。$2A-10^n$は負になることもありうるので、$2A-10^n=\pm X$である。$\displaystyle{A=\frac{10^n+X}{2}}$とするとき$C=10^n-A=\displaystyle{\frac{10^n-X}{2}}$と表すことができる。
$\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$の約数を調べることで見つけることができる。
★解の探索方法
$p=4n+1$を素数とする。$p=a^2+b^2$の形で表すことができる。
フェルマーの小定理により$\displaystyle{\frac{1}{p}}$の循環節の長さは$4n$の約数となる。
すなわち$10^{p-1}\equiv 1(\mod p)$である。ただし$p \ne 5$とする。
$$\frac{1}{p}=\frac{M}{10^{4n}-1}$$
ここで$M$は循環節である。
循環節の長さが最大の$4n$である場合について考える。このとき$p$は$10^{2n}-1$の約数ではない。したがって$p$は$10^{2n}+1$の素因数である。
$ax+by=10^n,bx-ay=1$を解くと$$x=\frac{10^n a+b}{a^2+b^2},y=\frac{10^n b-a}{a^2+b^2}$$を得る。$x,y$がともに整数なるとき$ax=A,bx=B$が求める解となる。また$by=10^n-A=C,bx=B$も$C^2+B^2=10^n C+B$を満たすので解とみなせる。
$p=17=4^2+1^2$について$\displaystyle{\frac{1}{p}}$を計算すると$0.0588235294117647･･･$という循環小数が得られる。
$588235294117647÷(10^8-1)=5882353$となり、$5882353*17$$=10^8+1$である。
$$5882353=\frac{10^8+1}{17}=\frac{588235294117647}{10^8-1}$$
$x=\displaystyle{\frac{4*10^4+1}{4^2+1^2}}=2353$により$A=9412,B=2353$が解として得られる。また、$y=\displaystyle{\frac{1*10^4-4}{4^2+1^2}}=588$により$C=588,B=2353$も条件を満たす。
ちなみに$5882353$は素数である。
問題1の解となるような$A,B$について$10^n A+B$が素数となるのは、$B$が$n$桁と仮定するとき$101$と$5882353$のみである。
$10^nA+B$が素数となるのであれば$A,B$は互いに素である。
$\displaystyle{\frac{A}{B}=\frac{a}{b}}$より$x=1$とすればよいので、
$(A^2+B^2)(1+y^2)=(A+By)^2+(B-Ay)^2=10^{2n}+1$となる。
このとき$A+By=10^n,B-Ay=1$である。
$A^2+B^2=10^n A+B$が$10^{2n}+1$の約数となるためには、$B$は$10$の倍数ではなく、かつ$B$が$n$桁であるためには$10^{n-1} \lt B \lt 10^n$が必要条件である。
ただし$n=1$の場合に限り$1 \leqq B \lt 10$となる。
$n=1$の場合、$10^2+1=101$は素数となるので約数は自明なものに限る。したがって$y=0$となるので$B-Ay=B$より$B=1$となり、このとき$A=10$となるので$A^2+B^2=101$となる。
$n \geqq 2$のとき$10^{n-1} \lt B \lt 10^n$である。
よって$10^{2n-2} \lt B(B-1) \lt 10^{2n}$
$y \geqq 1$なので$B \leqq By=10^n-A$より$10^{n-1} \lt 10^n-A \lt 10^n$が成り立つ。
したがって$10^{n-2} \lt \displaystyle\frac{B(B-1)}{10^n-A} \lt 10^{n+1}$が成り立つので$10^{n-2} \lt A $となる。$10^{2n-2} \lt 10^n A \lt 10^n A+B=A^2+B^2=\displaystyle\frac{10^{2n}+1}{1+y^2}$となるので、$1+y^2 \lt \displaystyle\frac{10^{2n}+1}{10^{2n-2}} \lt 101$を得る。従って$y \leqq 9$である。
$1+y^2$が$10^{2n}+1$の約数となるような条件を満たす$y$は$4,6$のみである。
$y=6$とすると$1+y^2=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)$となるので矛盾する。
$y=4$とすると$1+y^2=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$の場合のみである。
すなわち$5882353$のみである。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
