数学問題006 京大の整数…?

さて、今日はまず、2018年の京都大学の整数問題を解いてみましょう。

 

整数問題についてある程度の経験がある人間からしたら、

え、なに、京大どうしたの?

と突っ込んでしまいたくなるような問題でしたね。

 

問題1:2018京都大学

 

\displaystyle n^3 - 7n + 9 が素数となる整数 \displaystyle n を全て求めよ。

 

サトゥー

わからなくても、とりあえず色々実験するのが大事やでー

 

解説

 

ある程度整数問題を解いていると、ふとこんなことを思うようになります。

サトゥー

困った時はとりあえず「mod」や〜

 

困った時はmod

「mod」とは要するに合同式のことですね。

つまり、「剰余による分類」という典型手法が得てして整数問題では効果的なことが多いわけです。

 

サトゥー

特にこういう、一見とっかかりがなさそうな問題には効果てきめんです(偏見)

 

まぁ「合同式使うと減点される」という謎の迷信を信じるならば、普通にn=3m+1とか頑張って書いて場合分けしてください。僕は面倒なので使いますよ。ここについて文句禁止ね。はいー

 

困ったらだいたいmod2(つまり偶奇)から順番に剰余で場合分けして変形すれば、mod7あたりでなんとかなるパターンが多いです。

これで解決しないならば、他の周期性、対称性、因数分解とか、何か他の手を打ちましょう。

 

めも

困った時はとりあえず「mod」

 

さて、この問題はそれ以上特に面白みのない問題なので、ちゃっちゃと解いてしまいましょうか。

 

 

「剰余による分類」という手法について整理しておく

 

さてさて、ここまでは今日の記事の「前フリ」のようなものです。

今日は、整数問題の典型手法である「剰余による分類」について整理しておきたいと思っています。

 

なんで剰余で分類するのか

まぁ読んで字の如く。あまりで分類するんですね。

なんで分類するの?

っていうと、あまりには必ず周期があるからなんですね。

 

例えば、整数nをpで割ったあまりというのは、nが増えていくと0,1,2,3,…,p-1,0,1,…といったように、周期pで0~p-1を1ずつ増えていく数列が現れるんですね。

この性質を利用すると、無限にある整数から「pで割ったあまり」という特徴だけを抽出して、有限個(p個)の整数のグループにまとめることができるんですね。無限という難しい概念を考えずに、有限の範囲で物事を考えることができるようになるわけです。

しかも「あまり」というのは、整数問題の基本である「約数・倍数関係」と結構直結してくる話なので、この分類は非常に便利なんですね。かなり強い武器になることが少なくないんです。

 

メモ

とりあえず「余り」に着目して分類して考えるのが有効なことが多い

 

同様のアプローチで解ける問題

どんな時に強さを発揮するのか、数問だけ難関大の入試問題で例を見てみましょうか。

 

正の整数 \displaystyle n で \displaystyle n^n + 1 が3で割り切れるものを全て求めよ

(2003 一橋大学 誘導略)

とか、(答えは6で割って5余る自然数)

\displaystyle 3^a - 2^b =1 を満たす整数の組 \displaystyle (a ,b ) を全て求めよ

(2018 東北大学 誘導略)

とか。(これは若干面倒なので、あとでちゃんと扱います)

素数 \displaystyle p, q を用いて、\displaystyle p^q + q^p と表される素数を全て求めよ

(2016 京都大学)

 

こういう、一見とっつきようがなさそうな問題では、困った時の「mod」を考えてみるといいかもしれません。

 

問題2:2018東北大学

さて、先ほど取り上げた東北大の問題を実際に解いてみましょう。

\displaystyle 3^a - 2^b =1 を満たす整数の組 \displaystyle (a ,b ) を全て求めよ

(2018 東北大学 誘導略)

誘導が面倒なので省いております。

 

解説

この問題、まぁ誘導を省いた僕がよく無いんですが、、そもそも整数問題として扱うためには「整数」であることをちゃんと言っておく必要がありますね。(つまりaとbが正であることをしっかり述べておく必要がある)

整数としての処理をするなら、まずは整数であることを確認しよう

これ、意外と引っ掛け的な要素になり得るので注意してください。(まぁクッソ意地悪ですが)

「本当にその処理が有効なのか?」という確認は常に持っておくべきですね。文字で置き換えたら必ず変域を確認するだとか。

 

さてさて、その辺も含めた解答例がこちら。

 

 

サトゥー

b=2d-1としましたが、d使いませんでしたね。

まぁ思考の痕跡が残って良いと思うので、そのまま解答に載せます。

 

という感じで、最後の方は「2乗-2乗」の形から積の形に変形しています。

はーい。今日はこの辺で。整数は頻出のパターンを他にも、おさらいしていこうかと思っています〜〜

それではまた。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)