$ f(n) = n^2+n+1 $とおく。このとき, $f(n^2) = n^4+n^2 + 1$であって, 因数分解すると $f(n^2) = f(n)f(n-1)$であることが分かる。そこで, $f(n)$の最大の素因数を$ p_n $とする。 (便宜上, $p_0 = 1$とする。)問題は$p_{n^2} = p_{(n+1)^2}$となる$ n $が無限に存在するかである。

このとき, $f(n^2) = f(n)f(n-1)$から $p_{n^2} = \max{\{ p_n, p_{n-1}\}}$ がすべての$n\in \mathbb{N}$ で成り立つことに注意すると, 次のことが分かる:

($\ast$) ・・・いかなる自然数$ K $をあたえても, $ i>j>M $を満たす自然数$ i,j $であって, $p_{i} = p_{j}$を満たすものが存在する。

もし, $p_{n^2} = p_{(n+1)^2}$を満たす$ n $が有限個だとするなら, そのような $ n $ の最大値を$ N_0 $とおく。このとき, $ m>N_0 $を自然数$ m $が満たすならば, 常に$p_{m^2} > p_{(m+1)^2}$ または $p_{m^2} < p_{(m+1)^2}$ を満たさなければならない。

素数の真の無限減少列を作ることはできないから, $ m>N_0 $ なるすべての$ m $で常に $ p_{m^2} > p_{(m+1)^2} $ となることはあり得ない。したがって, ある $ m_0 > N_0 $が存在して, $p_{m_{0}^2} < p_{(m_0 + 1)^2}$ となる。

$p_{m_0}\leq \max{\{ p_{m_0}, p_{m_0 -1}\} } < \max{\{ p_{m_0+1}, p_{m_0}\}} $ であるから, 右辺は$p_{m_0}$に等しくなっては成らないので, $\max{\{ p_{m_0+1}, p_{m_0}\} } = p_{m_0+1}$が分かる。すると, $p_{m_0}<p_{m_0 + 1}$ となる。

このとき, $p_{(m_0+1)^2} > p_{(m_0 + 2) ^2}$であると仮定すると不合理である。なぜなら, $p_{(m_0+1)^2} = p_{m_0+1}$であったから, $p_{m_0 + 1} > \max{\{ p_{m_0+2}, p_{m_0+1}\} }$ は成り立たない。よって, $p_{(m_0+1)^2} < p_{(m_0+2)^2}$ となり, ここから同様な議論より $ p_{m_0+1} < p_{m_0+2}$ が分かる。

帰納的に, $m_0\leq n$ を満たす任意の$ n $に対して, $p_{n} < p_{n+1}$ でなければならないことが分かる。これは, $(\ast)$ で$K=m_0$とした内容に矛盾する。

よって$p_{n^2} = p_{(n+1)^2}$ を満たす$ n $が無限に存在する。

2019-07-18

(解いてみたその2) IMO2019 Problem 4

解いてみた

解いてみた No.2 は先日あったというIMOのProblem 4.からです。(選手のみなさんお疲れ様でした)

本当はテストが間近にあるのでこんなの解いてる暇は無いんですけどね・・・つい気になってしまった。

問題.2

以下をみたす正の整数の組$ (k,n) $をすべて求めよ:

$ k! = (2^{n} -1)(2^{n} -2)(2^{n} -4) \cdots (2^{n} - 2^{n-1}) $

解答

以下の議論において, $ m\in \mathbb{N} $が素数$ p $で割り切れる最大の回数を$v_p (m)$ で表すこととする。

次の補題を示す。

補題.1

$P_{j} := \displaystyle\prod_{i=1}^{3^{j} }(2^{i} - 1) $ ($ j=1,2,\cdots $)とおく。このとき, 任意の$ j $に対して $v_3(P_j) \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $

(証明)

$ (2^{i} -1) $が$3$で割れるのは$ i $が偶数であるときだから,

$\displaystyle\prod_{i=1}^{\frac{3^{j}-1}{2}}(4^{i} -1) = (2^{2} -1)(2^{4} -1)\cdots (2^{3^{j}-1} -1)$ の$3$で割れる回数を見れば良い。各$ i=1,2,\cdots ,\frac{3^{j}-1}{2}$に対して, $4^{i} -1$ が$ 3 $で割れる回数は, LTE Lemma より

$ v_3(4^{i} -1 ) = v_3(4-1) + v_3(i) = 1+v_3(i) $

なので, これの総和の$\displaystyle\sum_{i=1}^{\frac{3^{j} -1}{2}} (1+v_3(i)) = \dfrac{3^{j}-1}{2} + v_3\left( \left( \dfrac{3^{j}-1}{2} \right) ! \right)$ が$v_3( P_j )$に等しい。$v_3 \left( \left( \dfrac{3^{j}-1}{2} \right) ! \right)$ は, Legendreの定理より次のように評価される。

$ v_3 \left( \left( \dfrac{3^{j}-1}{2} \right) ! \right) = \displaystyle\sum_{i=1}^{\infty} \left\lfloor \dfrac{\frac{3^{j} -1}{2}}{3^{i}} \right\rfloor \leq \displaystyle\sum_{i=1}^{j-1} \dfrac{\frac{3^{j} }{2}}{3^{i}} = \displaystyle\sum_{i=1}^{j-1} \dfrac{3^{j-i}}{2} = \dfrac{1}{2} \cdot \dfrac{3}{2}(3^{j-1} -1) = \dfrac{3^{j}}{4} -\dfrac{3}{4} $

以上より $ v_3(P_j) \leq \dfrac{3^{j} -1}{2} + \dfrac{3^{j}}{4} - \dfrac{3}{4} = \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $ となる。

(証明終)

右辺の $( 2^{n} -1 )(2^{n} -2)(2^{n} - 4)\cdots (2^{n} - 2^{n-1})$は,

$2^{\frac{n(n-1)}{2}}\displaystyle\prod_{i=1}^{n}(2^{i} -1)$と書ける。これを$f_n$とおく。まず, $ k! $が$2$で$\dfrac{n(n-1)}{2}$ 回割れなければならないので、Legendreの定理より $\displaystyle\sum_{i=1}^{\infty} \left\lfloor \dfrac{k}{2^{i}} \right\rfloor = \dfrac{n(n-1)}{2}$

$ 3^{j-1} \leq n < 3^{j} $となるような $ j $ が, $ n $ に対して一意に取れることに注意する。明らかに $ \dfrac{f_n}{2^{\frac{n(n-1)}{2}}} $は$ P_j $の約数であるから,$ v_3(f_n) = v_3\left( \dfrac{f_n}{2^{\frac{n(n-1)}{2}}}\right) \leq v_3(P_{j+1})$

を満たす。補題1より, $v_3(f_n) \leq v_3(P_{j}) \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $

を得る。 $ v_3(k!) = v_3(f_n) $ であるから, $v_3(k!)$ も同じ不等式を満たさねばならず, $v_{3}(k!) = \displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{k}{3^{i}} \right\rfloor$ である。

したがって,

$\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{k}{3^{i}} \right\rfloor \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $ 　　と　　 $\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{k}{2^{i}} \right\rfloor = \dfrac{n(n-1)}{2} < \dfrac{3^{j}(3^{j} -1)}{2}$

を同時に満たす$ j $に限定される。

$ j\geq 2$であるとする。

2式目より, ガウス記号を$\lfloor x\rfloor \leq x$で評価すると $ \dfrac{n(n-1)}{2} < \displaystyle\sum_{i\geq 1}\dfrac{k}{2^{i}} = k$となる。

よって, $ k> \dfrac{n(n-1)}{2} \geq \dfrac{3^{j-1}(3^{j-1}-1 )}{2} \geq 3^{2j-3} >1 $ であるから,

$ \displaystyle\sum_{i\geq 1} \left\lfloor \dfrac{3^{2j-3}}{3^{i}} \right\rfloor = \dfrac{3^{2j-3}-1}{2} < \displaystyle\sum_{i\geq 1} \left\lfloor \dfrac{k}{3^{i}} \right\rfloor \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4}$ となる。*1

$ 3^{j-2} = J $とすると, $ \dfrac{3^{2j-3} -1}{2} = \dfrac{3J^{2} -1}{2} < \dfrac{9}{4}J - \dfrac{5}{4} = \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $ である。真ん中を整理すると

$ 3(2J^2 -3J +1) <0 $となる。左辺は$ 3(J-1)(2J-1) $であって, $j\geq 2$としたから $ J\geq 1 $である。よって, この不等式は成立し得ないので$ j\geq 2 $は不適。$ j=1 $とすることで, $1\leq n< 3$となるので $ n=1,2 $が必要。

元の式の右辺に代入して

$(2^{1} - 2^{0}) = 1$, $(2^{2} -2^{1})(2^{2} -2^{0}) = 6$ より,

$ (k,n) = (1,1), (3, 2) $ のみ。

（急いで書いてきたのでちょっとミスあるかもね）

階乗の入る不定方程式は個人的に難しいイメージがあります・・・。まあ, Legendreの定理とか使うものは結構限られると思いますが。$ a^{n} - b^{n}$の形を見たらやはりLTEなのですね。IMOの問題は次のリンクから見れます。

https://www.imo-official.org/problems.aspx

*1:ここで$ j=1 $とすると, $3^{2j -3}$が自然数とならないために不等式が成立しなくなる。

2019-07-14

(解いてみたその1) 2013駿台全国模試より

解いてみた

ツイッターで見かけた次の問題を解いてみました。出典は駿台全国模試とのこと。

問.

以下で $x$ の整式 $f(x)$, $g(x)$, $f_{m}(x)$ ($ m=1,2,\cdots ,n $)はすべて整数係数で, 最高次の係数が$ 1 $であるとする。

(1) $ f(\sqrt{2} ) = 0$, $g(\sqrt{2} + \sqrt{3}) = 0$を満たす$ f(x) $, $ g(x) $をそれぞれ一つ求めよ。

(2) 平方数でない$ n $個の正の整数$ a_k $ ($ k=1,2,\cdots ,n $)に対して, $ \alpha_n = \displaystyle\sum_{k=1}^{n} \sqrt{a_k} $とする。このとき, $ f_n(\alpha_{n})=0 $を満たす$ f_{n}(x) $が存在することを示せ。

(3) $ \displaystyle\sum_{k=10}^{29} \sqrt{k^{2}+1} $が無理数であることを示せ。正, 必要ならば$ k\geq 1 $で $ k< \sqrt{k^{2}+1} < k+ \dfrac{1}{2k}$ が成り立つことを用いてよい。

元ツイートはこちら

こういう問題(特に(2))は受験生は見通しがもてるまでに時間がかかると思います。

先に掲載した2問と同じく体の理論です。体の2次拡大や最小多項式の話。 pic.twitter.com/CNrfWuWCnM
— 数学教師 (@CLCbXY8IVF7BsPV) July 13, 2019

(解答)

(1) $ f(x) = x^{2}-2$

$ g(x) = ( (x+\sqrt{3})^{2} -2 )( (x-\sqrt{3})^2 -2 ) = (x^{2} + 1 + 2\sqrt{3}x)(x^2+1 - 2\sqrt{3} x) = (x^{2}+1)^2 - (2\sqrt{3} x)^2 = x^{4} -10x^{2} +1$

でよい。(ただし, 実際は$ f $は決して$ 2 $次以下にはならない。$ g $も$ 4 $次以下にはならない。)

(2) 帰納的に構成する。$ f_{1}(x) =x^{2} - a_{1}$でよい。整数係数で最高次が$ 1 $である $f_{n-1}(x)$ が得られたとする。この$ f_{n-1}(x) $を

$ f_{n-1}(x) = \displaystyle\sum_{j=0}^{N} b_{j} x^{j} $ で表す。

各$j=0,1,\cdots $に対して,

$(x+\sqrt{a_n})^{j} = \displaystyle\sum_{l=0}^{j} \binom{j}{l}x^{j-l}(\sqrt{a_n})^{l}$

$(x-\sqrt{a_n})^{j} = \displaystyle\sum_{l=0}^{j} \binom{j}{l}x^{j-l}(-\sqrt{a_n})^{l}$

であり, $ l $が偶数の場合に現れる項は上の二つで共通している。$ l $が奇数の項では符号のみが反転して現れる。それは, 以下の式からも明らかである。

$ (x\pm \sqrt{a_{n}})^{j} = \displaystyle\sum_{\substack{ 0\le l\le j\\ \mbox{$ l $は偶数}} }\binom{j}{l} x^{j-l} (a_{n})^{l/2} \pm \sqrt{a_{n}} \displaystyle\sum_{ \substack{ 0\le l\le j\\ \mbox{$ l $は奇数}} } x^{j-l}(a_{n})^{(l - 1)/2} $

ここで, 2つの$ \sum $の部分は整数係数多項式になっているから, 共通した整数係数多項式$ F_j(x), G_j(x) $が存在して

$(x+\sqrt{a_n})^{j} = F_j(x) + \sqrt{a_n} G_{j}(x)$

$(x+\sqrt{a_n} )^{j} = F_j(x) -\sqrt{a_n} G_{j}(x)$

と書けることになる。これと$f_{n-1}(x)$の$\sum$の表示をもとに, ある$F'_{n-1}(x), G'_{n-1}(x)$という整数係数多項式が存在して,

$f_{n-1}(x\pm \sqrt{a_n}) = F'_{n-1}(x) \pm \sqrt{a_n} G'_{n-1}(x)$

となることが分かる。そこで,

$f_n(x) = f_{n-1}(x+\sqrt{a_n}) f_{n-1}(x-\sqrt{a_n})$と定めると,

$f_n(x) = F'_{n-1}(x)^2 - a_nG'_{n-1}(x)^2$ となり, 明らかに整数係数多項式をなす。\\

また, $f_{n-1}(x)$の仮定から$f_{n-1}(x\pm \sqrt{a_n})$の先頭係数は明らかに$ 1 $ なので，$f_n(x)$の先頭係数も明らかに$ 1 $である。さらに, $x= \alpha_n $を代入すると, $\alpha_{n} -\sqrt{a_n} = \alpha_{n-1}$に注意して

$f_{n}(\alpha_{n}) = f_{n-1}(\alpha_{n} + \sqrt{a_n}) f_{n-1}(\alpha_{n} - \sqrt{a_n})=0$ となる。

よって

$ f_1(x) = x^2 - a_{1} $,　$f_{n}(x) = f_{n-1}(x+\sqrt{a_n})f_{n-1}(x-\sqrt{a_n})$ から定めればよい。\qed

(3) 有理数であったと仮定する。$\dfrac{q}{p} = \displaystyle\sum_{k=10}^{29} \sqrt{k^2+1}$とおく。($ p,q $は自然数で, 互いに素)

(2) より, $\dfrac{q}{p}$はある先頭係数が$ 1 $の整数係数多項式$ F(x) $の根になる。そこで, $F(x) = x^{d} + c_1x^{d-1}+\cdots + x^{1}x_{d-1} + c_d$ ($c_i$は整数) と書いて, $x=\dfrac{q}{p}$を代入し,

$\left(\dfrac{q}{p}\right)^{d} + c_1 \left(\dfrac{q}{p}\right)^{d-1} + \cdots + c_d = 0$

$p^{d}$を両辺にかけると

$q^{d} + pc_1q^{d-1} +\cdots p^{d}c_{d} = 0$

なので, この式から$q^{d}$は$p$の倍数なので, $ p=1 $でなければならない。(互いに素としたため)

$p=1$より, $\dfrac{q}{p} = q$となるので整数とならなければならない。

しかし, $\displaystyle\sum_{k=10}^{29} \sqrt{k^{2}+1}$が整数であるなら, $\displaystyle\sum_{k=10}^{29}(\sqrt{k^{2}+1} - k)$も整数である。ところが, これを不等式$ k<\sqrt{k^{2} +1} < k+\dfrac{1}{2k} $　($ k=10,\cdots, 29$) で評価すると

$\displaystyle\sum_{k=10}^{29} 0 < \displaystyle\sum_{k=10}^{29} (\sqrt{k^{2}+1})< \displaystyle\sum_{k=10}^{29} \dfrac{1}{2k} < \displaystyle\sum_{k=10}^{29} \dfrac{1}{2\cdot 10} = \dfrac{1}{20} \times 20 =1$

で, $\displaystyle\sum_{k=10}^{29} (\sqrt{k^{2}+1})$ は整数となりえないので不合理。よって無理数である。

いくつか大学数学の言葉でいいかえられる問題です。$ A $を環として, ある数 $ s $ が$A$係数の最高次$ 1 $の多項式の根になることを $ s $は$A$上整である, と言ったりします。

(1) $\sqrt{2}$, $\sqrt{2}+\sqrt{3}$ は$\mathbb{Z}$上整であることを示せ。

(2) $\alpha_{n} $は $\mathbb{Z}$ 上整であることを示せ。

(3) $\displaystyle\sum_{k=10}^{29}\sqrt{k^{2}+ 1}$は無理数であることを示せ。

こういう代数学の背景があるので今の自分にとっては若干見通しが立ったものの, (2) は受験生の自分じゃ思いつかなかったかも。ちなみに (3) で使われるのは$ \mb{Z} $の整閉性と呼ばれるもので, すなわち「$\mathbb{Z}$上整な$ \mathbb{Q} $の元は $\mathbb{Z}$の元に限る」が成り立ちます。だから, $\dfrac{q}{p}\in \mathbb{Q}$っておいたのが$ p=1 $になってしまうんですね。( $ \mathbb{Z}$はUFDですが, UFDならば整閉整域であるというのはよく知られたことです )

2019-06-08

闇のゲーム第2回と 2019駿台全国理系3番(3)

解いた記録

6/8(土)は作問サークルの活動日でしたので, 駿台全国模試理系数学をみんなであつまって解いてみて, 景品(お菓子など)を争奪する「闇のゲーム」をやってました。今回で第2回です。第1回は2019センターでした。

今回集まったのは7人。そもそもこのサークルのメンバーの多くが京大理学部生ですので, 毎度熾烈な戦いであることです。

終わった時間も記録して若干の加点制度もあったりして, その得点を競って順位をつけてます。んで, 今回の結果がこちら。

f:id:LimRim2326:20190608224536j:plain

まあ採点はてきとーーにやってますけれども, みんなさすがやんなあ

今回私は185点だったんですが, 自分にしてはめずらしく整数問題が解けませんでした。悔しいなあ

その問題が今回の第3問の(3)です。

(1) $a$を整数として. $a+1$が$3$の倍数であるとき, $a^{2}-a+1$は$3$の倍数ではあるが$9$の倍数ではないことを示せ。

(2) $b^3+1=3^c$を満たす自然数の組$(b,c)$を全て求めよ。

(3) $x^2-16y^6=3^{50}$を満たす自然数の組$(x,y)$を全て求めよ。

悔しかったのでこれの(3)の解答を書こうと思います。(2)までは簡単で, (2)の答えは$(b,c)=(2,2)$のみです。うまく(2)に帰着させるようです。

解答

(3) 因数分解する。$(x-4y^{3})(x+4y^{3})=3^{50}$なので$x-4y^{3}=3^{n}$と置ける。このとき, $x+4y^{3} = 3^{50-n}$であり, $y$は自然数なので$0\le n <25$である。

この2式から,

$8y^3= 3^{50-n}-3^{n} = 3^{n} (3^{50-2n} -1)$　・・・$(\ast)$

を得る。左辺の$3$で割れる回数は常に$3$の倍数であることから, 右辺の$3$で割れる回数$n$も$3$で割れなければならない。そこで, $n=3k$ ($0\le k\le 8$)とおく。*1このとき, $y$は$3^{k}$で割れる整数となっており, $(\ast)$を整理すると

$\left(\dfrac{2y}{3^{k}}\right)^3 +1 = 3^{50-6k}$

となる。そこで, $\dfrac{2y}{3^{k}}=b, c=50-2n$とおき, $b^{3} +1 =3^{c}$なので$(b,c)=(2,2)$となる。$c=50-2n=2$ だから, $n=24$ ($k=8$)となる。このとき,

$x=\dfrac{3^{50-24}+3^{24}}{2} = 5\cdot 3^{24}$,　$y= \dfrac{3^{8}}{2}\cdot b=3^{8}$となる。

よって, $(x,y)=(5\cdot 3^{24}, 3^{8})$ のみ。(解答終)

難しく考えすぎちゃったな・・・

*1:しらみつぶししたくなるが, そうすると大変。

2019-06-08

Twitterで見た超難問模試ってやつ

なんかTwitterで超難問模試とかいうのが流れてきたので少し解いてみました

超難問模試問1〜問3 pic.twitter.com/piHj45x3nT
— エボルト (@arboClovE) May 29, 2019

これ。整数たくさんあるな～～～ってなったので見てみた。1,3,5番はいけそうだったんで解いてみた。(6番もやったけどツイート主にまちがっとるって言われた)

ツイート主さんに送ってみた解答pdfです。

drive.google.com

1番

まあ要は整数になるときが素数なんでしょってことなんであの分数式が整数になればよくって。$\dfrac{2y^x}{x^y-y^x}$が自然数になるって考えればいつもの (分母)$\geq$ (分子)の必要条件があるわけでして。そこからまあ頑張れば評価はできるよな～って感じで方針的にはそこまで迷いませんでした, 計算はあれですが

3番

こういうのは得意。まずは$\geq 2$ではどうせ解はないだろうと予想。解がなくなるためには何が$a=1$と異なる状況を生み出すか, といえば$\mathrm{mod} 9$ですよね。そんでなんやかんやして, $6m+5$が指数に乗りましたから, 位数的な観点で剰余の振る舞いが少なくなるように$6k+1$型の(なるべく小さい)素数を$\mathrm{mod}$に取るといいだろうってのがあります。経験的に身についたテクニックです。すると自然に$\mathrm{mod} 13$の手が出て, $7^{6m}$ の$13$で割った余りというのは確かにたったの2通りしか異なる剰余を見せないんです。そうしてどっちの場合でも, なるべき剰余を回避してしまい, 不適であることが導かれる。いつも通りですよね。読者は$5^{a}+12^{b}=13^{c}$とかも挑戦されたい。($c=1$の場合がくせ者です。)

5番

むずい。はじめはマスターデーモンみたく$ n $の最小素因数でも取るか? と思ったがうまくいかず。逆に分子から素因数$ p $を取ってみて, なんか位数とか見ていけば$ n $の構成する素因数が制限を受けるという。$2^{n-1}=(2^{k})^{2^s}=K^{2^s}$って見るのがポイントだったんだなあ、おもしろい　なんか不定方程式botに有名問題として乗ってたけど有名なんだなあ

高校数学(?)はついよくやってしまう　最近問題作ってないからおもろいの作りたいなあ

Rim[N→∞]cos(2πen!/3)

数学。

院試解いてみた集

注意

京都大(留学生入試)

京都大(数学II)

H18数学II(1,2).pdf - Google ドライブ

東工大

東北大

大阪大

神戸大

解いてみた4(APMO2004)

(解いてみたその3) Shortlist 2013 N3