2019-09-16

2012年第二回東大オープン3を解いてみた

2019/09/19追記:みをつくしさんが間違いを指摘してくれたので、修正しました。ありがとうございました。

2012年第二回東大オープン3

今日は本を読む気がなかなかおきなくて数学できていないので、twitterの数学をしました。

[53]p,qを素数、nを正の整数とする。xの方程式
x²-pⁿx+qⁿ＝0
が整数解を持つとき、(p,q,n)の組を全て求めよ(2012年第二回東大オープン3、易)
— 整数問題bot (@seisu_bot) September 16, 2019

解答

まずは、式変形する。

$x^2-p^n x +q^n=0$
$x(p^n -x)=q^n$ ……(1.1)

このとき、

① $x=1,p^n-x=q^n$
② $x=q^n,p^n-x=1$
③ $x\equiv 0,p^n-x\equiv 0 (\bmod q)$

の3通りのパターンがあり得る。

①の場合

$p^n-1=q^n$ ……(2.1)

ここで、 $p,q$ の偶奇は異ならなければいけないことがわかる。 $q\lt p$ より、

$q=2$ ……(2.2)

である。また、 $n$ が偶数のとき、 $n=2k(k \ge 1)$ とおくと、

$(p^k-2^k)(p^k+2^k)=1$ ……(2.2)

となり、これを満たす $p$ は明らかに存在しないので矛盾。 $n$ が奇数のとき、

$p^n=2^n+1=(2+1)(1-2+2^2-\cdots+2^{n-1})$ ……(2.3)

と因数分解できる。ここで、 $n\ge 3$ とすると

$1-2+2^2-\cdots+2^{n-1}=p^{n-1}$
$1-2+2^2-\cdots-2^{n-2}=p^{n-1}-2^{n-1}$
$-1-2^2-2^4 \cdots - 2^{n-3}$ ……(2.4)

となるが右辺は正で、左辺は負となるので矛盾。よって、 $n=1$ で

$(p,q,n)=(3,2,1)$ ……(2.5)

である。

②の場合

$p^n-q^n=1$ ……(3.1)
$p,q$ の偶奇はことなり、 $p \gt q$ なので、 $q=2$ 。従って、

$p^n=2^n+1$ ……(3.2)

この式は(2.3)式と同じなので、求める $p,q,n$ も①の場合と同じである。

③の場合

$p^n\equiv 0 (\bmod q)$ ……(4.1)

より、 $p,q$ は素数なので、

$p=q$ ……(4.2)

である。(1.1)式より、 $k+l=n(n-1 \ge k,l \ge 1)$ となる自然数によって、

$x=p^k,p^n-x=p^l$ ……(4.3)

と表せる。 $x=p^k$ を右の式に代入して、

$p^n-p^k=p^l$
$p^k(p^{n-k}-1)=p^l$ ……(4.4)

ここで、 $n-k\ge 1$ なので、

$p^{n-k}-1\equiv -1 \not\equiv p$ ……(4.5)

なので、 $p^{n-k}-1$ は $p$ で割り切れない。従って、

$p^{n-k}-1=1$
$p^{n-k}=2$ ……(4.6)

でなければいならない。よって、これを満たす $(p,q,n)$ は、

$(p,q,n)=(2,2,2)$ ……(4.7)

求める解

以上より、求める解は、

$(p,q,n)=(3,2,1),(2,2,2)$ ……(5.1)

のみである。

2019-09-13

整数問題bot②の自作問題を解いてみた1

twitter 数学整数問題bot②

整数問題bot②の自作問題

今回もtwitterで見かけた以下の問題を解いてみた。なかなか手ごわい問題だった。

p^n-1=m^5+m^4を満たす素数p,および正の整数m,nを全て求めよ.(自作)
— 整数問題bot② (@handmade_math) September 12, 2019

解答

問題は、

$p^n-1=m^5+m^4$ ……(1.1)

を満たす正の整数[tex;m,n]を全て求めよである。

$m=1$ のとき、

$p^n=3$
$\Rightarrow p=3,n=1$ ……(1.2)

がわかる。次に、 $m=2$ のとき、

$p^n=32+16+1=49$ より

$p=7,n=2$ ……(1.3)

がわかる。これで、解

$(m,n)=(1,1),(2,2)$ ……(1.4)

が求まった。これ以外に解のないことを示す。以後、 $m\ge 3$ として矛盾を導く。

因数分解と合同式

$p^n=m^5+m^4+1=(m^2+m+1)(m^3-m+1)$ ……(2.1)

と因数分解できる。 $m\ge 3$ より、

$m^2+m+1\ge 13 \not= 1$ ……(2.2)
$m^3-m+1 \ge m^3+1 \ge 28 \not= 1$ ……(2.3)

より、 $m^2+m+1,m^3-m+1$ は $p$ の冪乗であって、 $1$ でない。従って、 $p$ を法として、

$m^2+m+1\equiv 0$ かつ $m^3-m+1\equiv 0$ ……(2.4)

である。上の2式の差をとると、

$0\equiv(m^3-m+1)-(m^2+m+1)=m(m^2-m-2)=m(m+1)(m-2)$ ……(2.5)

と因数分解できる。

場合分けと合同式

(2.5)式より、 $p$ を法として

① $m\equiv 0$
② $m\equiv -1$
③ $m\equiv 2$

となる。

①の場合、(2.4)式より、

$1 \equiv 0 (\bmod p)$ ……(3.1)

より、これを満たす素数 $p$ は存在しないので矛盾。

②の場合、(2.4)式より、

$(-1)^2-1+1\equiv 1\equiv 0 (\bmod p)$ ……(3.2)

より、これを満たす素数 $p$ は存在しないので矛盾。

③の場合(2.4)式より、

$2^2+2+1=7 (\bmod p)$ ……(3.3)

より、これを満たす素数 $p$ は $7$ である。(2.4)式より、

$2^3-2+1\equiv 7 \equiv 0 (\bmod 7)$ ……(3.4)

となるので、無矛盾である。よって、 $m\ge 3$ ならば、 $p=7$ である。

再び場合分けと合同式

(2.1),(2.2),(2.3)式より、

$m^2+m+1 = 7^k (k\ge 2)$ ……(4.1)
$m^3-m+1 = 7^l (l \ge 2)$ ……(4.2)

と表せる。そこで、法を49として、(法を7とした時と同様にして、)

$m^2+m+1\equiv 0 (\bmod 49)$ かつ $m^3-m+1\equiv 0 (\bmod 49)$ ……(4.3)

である。再び、差をとって、

$0\equiv m(m+1)(m-2) (\bmod 49)$ ……(4.4)

を得る。ところで、 $m-2$ のみが $7$ で割れたので、 $m-2$ のみが $49$ で割れる。つまり、

$m-2\equiv 0 (\bmod 49)$
$\Rightarrow m \equiv 2 (\bmod 49)$ ……(4.5)

となる。ところが、(4.3)式より、法を49として、

$2^2+2+1 \equiv 7 \equiv 0 (\bmod 49)$ ……(4.6)

となり矛盾。よって、 $m\ge 3$ の解はない。

求める解

以上より、求める解は、(1.4)式より

$(m,n)=(1,1),(2,2)$ ……(5.1)

のみである。

2019-09-10

【別解】2009ウクライナ数学オリンピックを解いてみた

数学 twitter 数学オリンピック整数問題bot②

数学関連の絶版本・品切れ本をコチラから購入できます！

2009ウクライナ 数学オリンピック

今日もtwitterで見かけた問題を解いてみた。最近、平方数にこっているので目についたのが次の問題だ。

素数pと正の整数mであって,2p^2+p+9=m^2を満たすようなものを全て求めよ.(2009 ウクライナ数学オリンピック)
— 整数問題bot② (@handmade_math) September 10, 2019

解いてみてから気づいたが、過去にも同じ問題を解いていた。

sky-time-math.hatenablog.jp

今回は別解を見つけたので、それを紹介する。

解答

問題は、

$2p^2+p+9=m^2$ ……(0)

を満たす素数 $p$ と正の整数 $m$ を求めよである。まずは、式変形して9を右辺に移項することで、

$p(2p+1)=(m-3)(m+3)$ ……(1)

となる。 $p$ は素数なので、 $m-3,m+3$ のいずれかを割る。

① $p$ が $m-3$ を割る場合

整数 $t$ によって、

$m-3=pt$
$\Rightarrow m=3+pt$ ……(2)

と表せる。このとき(1)式より、

$p(2p+1)=pt(pt+6)$
$\Rightarrow 2p+1=t(pt+6)$
$\Rightarrow (t^2-2)p=1-6t$
$\therefore p=\frac{1-6t}{t^2-2}$ ……(3)

と変形する。*1ここで、 $t=-s$ と取り直すと、

$p=\frac{1+6s}{s^2-2}$ ……(4)

を得る。これが整数になるのは、

$1+6s \gt s^2 -2$ または $s^2-2=\pm 1$ ……(5)

の場合である。ここで、 $s^2-2=1$ は $s^2=3$ となり、 $s$ が整数とならないので不適。 $s^2-2=-1$ のとき、

$s^2=1$
$\Rightarrow s=\pm 1$ ……(6)

話を戻して、(5)式のもう一方の条件は、

$f(s) \equiv s^2-2 -(6s+1)=s^2-6s-3 \lt 0$ ……(7)

と表せる。

$f(6)=-3$
$f(7)=4$
$f(0)=-3$
$f(-1)=4$

従って、(7)式または(6)式が成立するのは、

$-1 \le s \le 6$

である。これを満たす整数 $s$ を(3)式に代入していくと、

$s=-1 \Rightarrow p=5$
$s=0 \Rightarrow p=-\frac{1}{2}$
$s=1 \Rightarrow p=-7$
$s=2 \Rightarrow p=\frac{13}{2}$
$s=3 \Rightarrow p=\frac{19}{7}$
$s=4 \Rightarrow p=\frac{25}{14}$
$s=5 \Rightarrow p=\frac{31}{23}$
$s=6 \Rightarrow p=\frac{37}{34}$

となり求める素数 $p$ は

$p=5$

である。このとき、(2)式より、 $t=1$ なので、

$m=3+5=8$

である。

② $p$ が $m+3$ を割る場合

$m+3=pt$
$\Rightarrow m=pt-3$ ……(8)

このとき(1)式より、①と同様にして、

$p(2p+1)=pt(pt-6)$
$\Rightarrow 2p+1=t(pt-6)$
$\Rightarrow (t^2-2)p=6t+1$
$\therefore p=\frac{6t+1}{t^2-2}$ ……(3)

この式は、(4)式と等価なので、

$t=-1$ のときのみ、 $p$ が正の整数になり、

$p=5$

である。このとき、(8)式より、

$m=-5-3=-8$

となるが $m$ は正の整数であったので不適。

求める解

よって、求める解は、

$p=5,m=8$

である。

*1:ちなみに、 $t$ の2次式と見て、判別式から攻めようとするとスタート地点にもどってしまう。

2019-09-07

FoxQの予想の部分的証明([tex:s=2p^2,t=q^2]で[tex:p,q]が互いに素な奇素数の場合 )

twitter プチ研究数学オリジナル

数学関連の絶版本・品切れ本をコチラから購入できます！

原始ピタゴラス数

原始ピタゴラス数は、互いに素な自然数 $s,t$ で、偶奇が異なるものを用いて、

$C=s^2+t^2,B=2st,A=s^2-t^2$ ……(1.1)

で全て表される。今回は、 $s=2p^2$ , $t=q^2$ , $p,q$ は互いに素な奇素数と表されるとき、何が言えるか検証してみたので、成果を報告する。

法を4としたとき

FoxQの予想は次のものである。

$A^a+B^b$ が平方数 $n^2$ *1になる自然数 $(a,b)$ の組は、 $(A,B)=(9,40)$ の場合を除いて高々2通りである。今回は、この予想の証明を部分的な場合について行う。

まず、

$A=s^2-t-2=4p^4-q^2$ ……(2.1)
$B=2st=(2pq)^2$ ……(2.2)

である。

$n^2 \equiv (-1)^a \; (\bmod 4)$
$\Rightarrow a$ は偶数……(2.3)

が言えるので、

$a=2m(m \ge 1)$ ……(2.4)

とおく。また、

$B=2\times2p^2q^2=(2pq)^2$ は平方数……(2.5)

である。

原子ピタゴラス数から原子ピタゴラス数へ

$A^a+B^b=(A^m)^2+[(2pq)^b]^2=n^2$ ……(3.1)

なので、 $A^m,(2pq)^b,n$ は再びピタゴラス数になっている。ここで、Wolfram Alphaによると、

$\gcd(A,2pq)=1$

である。*2つまり、 $A^m,(2pq)^b$ は互いに素なので、 $A^m,(2pq)^b,n$ は再び原始ピタゴラス数になっている。よって、ある偶奇の異なって互いに素な自然数の組 $(\alpha,\beta)$ が存在して、

$A^m=\alpha^2-\beta^2$ ……(3.3)
$(2pq)^b=2\alpha \beta$ ……(3.4)
$n=\alpha^2+\beta^2$ ……(3.5)

と表せる。 (3.4)より、可能な $(\alpha,\beta)$ の組は

① $\alpha=2^{b-1}p^b,\beta=q^b$
② $\alpha=2^{b-1}q^b,\beta=p^b$
③ $\alpha=p^b,\beta=2^{b-1}q^b$
④ $\alpha=q^b,\beta=2^{b-1}p^b$
⑤ $\alpha=2^{b-1}p^bq^b,\beta=1$

の5通りである。

③の場合

法を $8$ として、 $p$ が奇数なので

$4p^4-1\equiv 3$ ……(4.1)
$p^{2b} \equiv 1$ ……(4.2)
$2^{2b-2}\equiv 1,4,0$ ……(4.3)

が成り立つ。特に、 $b\ge 3$ で $2^{2b-2}\equiv 0$ である。そこで、(4.3)の3通りの場合を括弧()で表すことにすると

$3\equiv A^m=p^{2b}-2^{2b-2}q^{2b}\equiv1-(1,4,0)\equiv(0,5,1)$ ……(4.4)

より矛盾。

④の場合

法を $8$ として、③の場合と同様にして、

$3\equiv A^m=q^{2b}-2^{2b-2}p^{2b}\equiv1-(1,4,0)\equiv(0,5,1)$ ……(5.1)

より矛盾。

②の場合

法を $8$ として、③の場合と同様にして、

$3\equiv A^m=2^{2b-2}q^{2b}-p^{2b}\equiv(1,4,0)-1\equiv(1,3,7)$ ……(6.1)

よって、 $b=2$ である。このとき、(2.1)(3.3)式より、

$A^m=(4p^4-q^4)^m=4q^4-p^4$ ……(6.2)

$m=1$ は明らかに不適。 $m \ge 2$ とすると、

$A^m\ge (4p^4-q^4)^2=16q^8-8p^4q^4+q^8 \gt q^8$ ……(6.3)

従って、(6.3)式より、 $q\ge 3$ なので、

$A^m \gt q^8 \gt 4q^4 \gt 4q^4-p^4$ ……(6.4)

となり矛盾。

⑤の場合

法を $8$ として、③の場合と同様にして、

$3\equiv A^m=2^{2b-2}p^{2b}q^{2b}-1\equiv(1,4,0)-1\equiv(1,3,7)$ ……(7.1)

よって、 $b=2$ である。このとき、(2.1)(3.3)式より、

$A^m=(4p^4-q^4)^m=4p^4q^4-1$ ……(7.2)

$m=1$ は明らかに不適。 $m\ge 2$ とすると

$A^m\ge (4p^4-q^4)^2=16p^8-8p^4q^4+q^8 \gt 16p^8+q^8$ ……(7.3)

また、 $A\gt 0$ より、

$4p^4\gt q^4$ ……(7.4)

従って、(7.3)(7.4)式より、

$A^m \gt 16p^8+q^8 \gt 4p^4q^4+q^8 \gt 4p^4 q^4 \gt 4p^4q^4-1$ ……(7.5)

となり矛盾。

①の場合

法を $8$ として、③の場合と同様にして、

$3\equiv A^m=2^{2b-2}p^{2b}-q^{2b}\equiv(1,4,0)-1\equiv(1,3,7)$ ……(8.1)

よって、 $b=2$ である。このとき、(2.1)(3.3)式より、

$A^m=(4p^4-q^4)^m=4p^4-1$ ……(8.2)

よって、

$m=1$ ……(8.3)

のとき明らかに成立。よって、 $m=1$ は求める解の１つである。 $m \ge 2$ とすると、

$A^m\ge (4p^4-q^4)^2=16p^8-8p^4q^4+q^8 \gt 16p^8+q^8$ ……(8.4)

従って、(8.4)式より、 $q\ge 3$ なので、

$A^m \gt 16p^8+q^8 \gt q^8 \gt 4q^4 \gt 4p^4-q^4$ ……(8.5)

となり矛盾。

求まった解

以上より、互いに素で偶奇が異なる $s=2p^2$ , $t=q^2$ から生成される原子ピタゴラス数 $A,B$ に対して、

$A^a+B^b$ が平方数 $n^2$ になる自然数 $(a,b)$ の組は、(2.4)(8.3)式より、

$(a,b)=(2,2)$ のみである。

今回も解は $(a,b)=(2,2)$ のみとなったので、次回は $(a,b)=(2,2)$ 以外に解の出てくる場合を調べたいと思います。

*1: $n$ は明らかに奇数である。

*2:ユークリッドの互除法がうまくできませんでした。やり方をわかった方がいたらどうか教えてください。

2019-09-06