taiseinimanの日記

国家公務員総合職合格、名工大院生、INTP

京大ー復習ー整数

京大理系１：整数a,bはどちらも３で割り切れないが、a^3 + b^3は81で割り切れる。

これを満たす(a,b)のうち、a^2 + b^2を最小とする組とその値を求めよ。

$\displaystyle 京大理系２：2以上の整数Nに対して、数列a_nを以下のように定める。$

$\displaystyle (i): a_1 = 2^N - 3$

$\displaystyle (ii): a_nが偶数ならa_(n+1) = a_n/2 、a_nが奇数ならa_(n+1) = (a_n - 1)/2$

$\displaystyle このときどのような自然数Mに対しても、$

$\displaystyle \sum_{n=1}^M \leqq 2^{n+1} - N - 5となることを示せ。$

$\displaystyle 京大文系１：素数p,qに対してp^q + q^pが素数となる組を全て求めよ。$

$\displaystyle$

$\displaystyle (京大理系１－復習)$

$\displaystyle こういう考えもある。$

$\displaystyle a^3 + b^3 = 対称式だ、a+bとabで表すことができる。$

$\displaystyle a^3 + b^3 = (a+b)(a^2 -ab + b^2) = (a+b)\{(a+b)^2 - 3ab\}$

$\displaystyle a^4 + b^4 = (a^2+b^2)^2 -2a^2b^2 = \{(a+b)^2 -2ab\}^2 - 2(ab)^2$

$\displaystyle a^5 + b^5 = (a+b)(a^4 - a^3b + a^2b^2 - ab^3 + b^4)$

$\displaystyle = (a+b)([{(a+b)^2 -2ab}^2 - 2(ab)^2] -ab\{(a+b)^2 -2ab\} + (ab)^2 )$

$\displaystyle 一般に、Q(n) = a^n + b^nとすると、$

$\displaystyle Q(2n+1) = (a+b)\{ (-ab)^n +\sum_{k=0}^{n-1}(-1)^{2n-k}\{ (ab)^nQ^2(n-k) - 2(ab)^k \} \}$

$\displaystyle また、Q(2n) = a^{2n} + b^{2n} = (a^n + b^n)^2 - 2(ab)^n$

$\displaystyle = Q^2(n) -2(ab)^nなので、$

$\displaystyle Q(n)は必ずa+bとabの式で表すことができる。$

$\displaystyle 交代式W(n) = a^n - b^n = (a-b)(\sum_{k=0}^{n-1}a^{n-k-1}b^k)であり、$

$\displaystyle W(2n+1)のbを-bとおいてやれば、$

$\displaystyle Q(2n+1) = (a-b)(\sum_{k=0}^{n-1}a^{n-k-1}(-b)^k)$

$\displaystyle aを-aとおけば、Q(2n+1) = (b-a)(\sum_{k=0}^{n-1}(-a)^{n-k-1}b^k)$

$\displaystyle 今挙げた因数分解公式は暗記したほうがいい。$

$\displaystyle aは３で割り切れないということを$

$\displaystyle a = 3k + r (rは余りで０でない)とおいたほうがいいときと、$

$\displaystyle a ≡ r (mod 3)とおいたほうがいいときの２つある。$

$\displaystyle すべて同値である。$

$\displaystyle まあそんなことは問題見てもわからない時があるので、$

$\displaystyle とにかく、試していくしか無い。(総当たり法も一つのやり方)$

$\displaystyle aもbも３で割り切れないのだけど、a^3 + b^3は対称式なのだから、$

$\displaystyle 3の余りで場合分けした時以下の３つしか無い。$

$\displaystyle a = 3k + 1, b = 3m + 1$

$\displaystyle a = 3k - 1 , b= 3m - 1$

$\displaystyle a = 3k + 1 , b= 3m - 1$

$\displaystyle a = 3k + 2 とおくより、a = 3m - 1とおいたほうがいいだろう。$

$\displaystyle a^3 + b^3みたいに因数分解できるなら、したほうが殆どの場合よい。$

$\displaystyle まず思い当たるのがa^3 + b^3 = (a+b)(a^2 - ab + b^2)である。$

$\displaystyle a^2+b^2 = (a+b)^2 - 2abとおいて計算するほうがいいと思えるようになったほうがいい。$

$\displaystyle そうすると、a^3 + b^3 = (a+b){(a+b)^2 - 3ab}$

$\displaystyle 重要なこととして、$

$\displaystyle a = 3f(k) + rは３の倍数でないということ。$

$\displaystyle 当たり前だけど、例えば、a = 3(k^4 +23k^2 + k +432) + r$

$\displaystyle みたいな式になると、３の倍数かどうかわからなくなる人がいる。$

$\displaystyle a = 3k + 1 , b = 3m + 1のとき、$

$\displaystyle a+b = 3(k+m) + 2なのだから３の倍数でないので３を持たない。$

$\displaystyle (a+b)^2 = 9(k+m)^2 + 12(k+m) + 4$

$\displaystyle ab = 9km + 3k + 3m + 1$

$\displaystyle よって、\{(a+b)^2 - 3ab\} = 3f(k,m) + 1となって３を持たない。$

$\displaystyle つまり３を一つも持たないので81 = 3^4で割り切れない。$

$\displaystyle a = 3k - 1 , b = 3m-1のとき、$

$\displaystyle a+bは３を持たない。$

$\displaystyle (a+b)^2 = 9(k+m)^2 -12(k+m) + 4$

$\displaystyle ab = 9km - 3m -3k + 1$

$\displaystyle よって、a^3 + b^3は３を一つも持たない。$

$\displaystyle a = 3k - 1, b = 3m + 1のとき、$

$\displaystyle a+b = 3(m+k)$

$\displaystyle (a+b)^2 = 9(m+k)^2$

$\displaystyle ab = 9km + 3k - 3m - 1より、$

$\displaystyle \{(a+b)^2 - 3ab\} = 3\{3f(k,m) + 1 \}であるから、$

$\displaystyle a^3 + b^3 = 9(m+k)(3f(k,m) + 1)$

$\displaystyle よって、m+kが9の倍数のときに限ることがわかる。$

$\displaystyle m+k = 9n ⇔ m = 9n - kとおいてやれば、$

$\displaystyle (1)...a = 3k-1かつb = 3(9n-k)+1 = 27n - 3k + 1とき満たす。$

$\displaystyle a^2 + b^2は対称式なのだから、$

$\displaystyle (2)....a = 27n - 3m -1,b = 3m+1 と(1)のときの最小値を求めれば良い。$

$\displaystyle まあ、普通は二次関数を使うでしょう。$

$\displaystyle (1)のとき、a^2 + b^2 = (a+b)^2 - 2abを用いて、$

$\displaystyle = 3^6n^2 -2(3^4kn - 9k^2 + 3k -27n +3k -1)$

$\displaystyle = 3^6n^2 - (2・3^4k + 3^3)n + 18k^2 -12k +2$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$

$\displaystyle$