3

(高校生向け)整数問題の感覚を磨くために②

130
1
$$$$

この記事は続編です。①を見てからご覧ください。
「整数の感覚を磨くために①」

2-1.素数の扱い

素数も結構出てくる印象です。また素数問題の対処法には整数問題の重要な考え方が詰まっています。

1.素数と友達になろう

友達と仲良くなる時は何が大切でしょう。相手のことをよく知ることですね。まずは素数のことについてよく知りましょう

素数

$2 以上の自然数で、正の約数が 1 とその数自身のみであるもの$

何を今更…と思うかもしれませんが、これが素数の全てです。
素数というのはその特殊性から、有限化の切り口の宝庫です。ここから現れる特徴を見ていきましょう。(以下特に断りがない限り、pは素数、p以外の文字は整数とします)

1.積の形で表現された素数

$x< y、p=xyとする。$
こんな形があったとします。ちょっと眺めてみて、ここから得られる情報を考えてみてください。
$(x,y)=(1,p)(-p,-1)$
が確定するのがわかりますか?素数の定義通り、pの約数は±1、±pです。2文字の積で表されているため、(約数)×(約数)の形で表せるから確定、といった具合です。
(前回の分数の話でも言ったんですが、約数を書き出すときにマイナスを忘れないでください。)
ここからわかるように、素数と因数分解は相性最高です。簡単に有限化できてしまうからです。

2.大小と偶数奇数

$2t+4k-6=pとするとき、pを求めよ$
ちょっと考えてみてください。本シリーズ①の導入でもちょっとチラつかせたやつです。
答えは2です。$(左辺)=2(t+2k-3)$となるためpは2の倍数です
素数の中で偶数であるのは2のみです。ある素数が偶数であるとわかった瞬間それは2で確定します。これは超強力な条件として働くことが多いです。
あと当然ですが、素数は必ず2以上です。当然すぎてあまり意識してないですが、不等式評価でよく使います。

3.ある素数の倍数

$p-4は素数で、p-4≡0(mod3)とする。pを求めよ。$
合同式は知っている前提で進めます。p-4は素数で3の倍数らしいです。はい、p-4は3ですね。つまりpは7です。
ある素数pが何か(素数)の倍数となった時、pはその素数で確定です。
今回で言ったら3の倍数ですが、6、9、30などは素因数3と他にも持つので素数ではありません。よって今回は3で確定です。
また、何かの倍数となるときの「何か」が素数であるというのは結構重要です。
例えば、pが4の倍数となる、これはあり得ません。実際に書き出せばわかるでしょう。
これを逆手に取れば、例えば「nが素数でないことを証明せよ」なんて出たら、nが4の倍数だとか6の倍数だとか示せばいい、なんていう1つの武器にもなり得ます。

4.取りうる余剰の限定

3と似た内容ですが若干違います(3の延長に近いかも?)。
例えば、$mod3$を考えます。$p$を2、3でない素数とします。
普通、$mod3$が取り得る値は0,1,2です。ですが、素数pに対しては1、2のみです(現在pが3でないとわかっているので)。3でも言った通り、素数は何かの倍数(その素数自身を除く)になり得ません。
また、$mod4$を考えた時、pに対しては1と3のみです。
$p≡2(mod4)$であれば2の倍数となってしまうからです。
こんな感じで、素数に対しては取りうる余りの種類が減ります。この「取り得る余剰」というアイデアは整数問題のあらゆる場面(特に証明問題)で効いてきます。覚えておいて損はないでしょう。
またこの考え方が直接的な解法になる場合は稀ですが(証明を除く)、有限化した後の更なる絞り込みで有効になる場合が多いです。

5.実験

これは素数の性質とは関係ないんですが、素数問題で「実験させる」という意図の問題はそれなりに多い印象です。基本的には「実験をしていたら何か法則が見えた」という流れが多いんですが、それは問題作成者側がその法則が出現するように作ったからです。今回はもう1歩踏み込んでこの構造を理解しようと思います。まぁ、これは問題をやりながら解説します。

2.問題の中に現れる素数の性質

では、今の性質が問題ではどう現れるか見てみましょう。
また、解説の中で性質1とか言うことがありますが、それは今解説した1〜4の性質のことを言っています。

$n^{2}+3n+2が素数となるような整数nを全て求めよ$

舐めるなよ!!って言いたくなるかもしれませんが、本当に完璧な解答ができるでしょうか。
「素数と因数分解は相性最高」でしたね。今回は因数分解するのも必然性があります。

解答(性質1によるアプローチ)
$(与式)=(n+2)(n+1)$
$よって、これが素数となるときn+2=±1またはn+1=±1つまりn=-1,-3,0,-2が必要。$
$このうち条件を満たすのはn=0,-3のみ。$
$よって、n=0,-3$

因数分解をした後は、「因数のどちらかは1」を使って有限化します。毎度言いますが、マイナスを忘れないでください。
また、「どちらかが1」というのはもちろん必要条件です。十分性の確認をしましょう。
素数と因数分解は相性最高ですが、今回は因数分解できる形だから使っただけです。素数には他にも性質はあるんでしたよね。この素数→因数分解という流れはとても有名なのですが、これだけに囚われないようにしてください。素数に関してこれしか扱っていない参考書などもザラにあるので。
例えば、こんな見方もできます。(へーそうなんだくらいでいいです)

解答(性質3によるアプローチ)
$(与式)≡n^{2}-n≡n(n-1)$ $ (mod2)$
$ここで、n(n-1)は連続2整数の積だから、(与式)は2の倍数。$
$また、(与式)は素数だから、(与式)=2$
$これを解いて、n=0,-3$

いやどっからmod2出てきた?って思うかもしれませんが、一旦認めてください。後ほどわかります。
これは性質3「素数の倍数を考える」からアプローチしたものです。今回で言うとその素数は2です。2の倍数と確定させる→素数だから2確定、と言った流れです。
このように、因数分解以外にも有用なアプローチがあることを認識してください。因数分解に囚われているとこのような視点が持てなくなります。まぁこの問題をこんな解き方をする変態はいないと思いますが笑

$n^{3}-7n+9が素数となるような整数nを全て求めよ$

なんか問題1と似てますね。この問題はどんだけ擦られんねんってくらい擦られてるので見たことがある人もいるかもしれません。京大の問題です。(まぁそのくらい良問ってことです)
どうアプローチしましょうか。
素数主体の問題は一旦冒頭で述べた4つの素数の性質を考えてみるといいです。
積の形にするために因数分解を試みますか?いいアプローチです。でも残念ながらこの式はワンチャン因数分解できそうでできないです。
偶奇を考えますか?この場合だとmod2で考えるということですね。
mod2で考えるということはn≡0か1です。これを式に代入して0の時も1の時も全体がmod2で0になれば勝ちですが、そう上手くは行かないようです。
あーどうしようか。はい。困ったら実験です。

実験
$n=0,1,2,3,4…を代入してみる$
$順に、式全体は9,3,3,15,45,…$

なんか変だと思いませんか?なぜか何を入れても3の倍数になります。
ここでアンテナを立てましょう。性質3「素数の倍数を考える」が有効そうです。今回で言うと3です。もし、この式が確定で3の倍数になるなら、(与式)=3という等式が立ちます。やってみましょう。

目標:(与式)≡0 (mod3)

$以下、法を3とする$
$n^{3}-7n+9≡n^{3}-n=(n-1)n(n+1)$
$(n-1)n(n+1)は連続3整数の積だから、3の倍数。$
$\therefore (与式)≡0$

はい勝ち確です。これで性質3を当てはめれば終了です。
あとは(与式)=3とし方程式を解くだけなので省略しますが、答えは1,2,-3です。

ちなみに、問題1のmod2を使ったアプローチは実験していったらなぜか全部2の倍数だった、だからmod2を選んだとでも思っておけばいいでしょう。

実際この問題はかなりの良問で、エッセンスがいくつか得られます。

実験について

整数問題で実験は超ウルトラスーパー重要です。というか、整数に限らず数学では超大事です。
実験の目的は法則を得るためのみではありません。例えば、確率の問題で設定が複雑であれば実験をして様子をつかめます。漸化式などでも同じことが言えます。軌跡の問題などでは、少し実験すればなんとなく答えの図形が見えてくる、なんてこともあります。
法則性を得られなくても、その実験は失敗ではありません。
予想が立ったまま臨むかそうでないかでは安心感が違いますからね。

modについて

先程実験が大切と言ったばかりですが、この程度の問題であれば実験なしで解きたいですね笑。
まぁそれには経験を積む必要があるので今は意識しなくて結構です。
さて、modについてですが、modを用いた式変形にもポイントがあります。
まずは、目標を明確にしましょう。
今回は、-7という係数を-1にすることで因数分解できると見えたので係数-1を選びました。また、modにかけたら因数分解できる形が現れた・連続整数が現れたという構造は整数問題で頻出です。これは知っておくべきでしょう。
また、この問題くらいは実験なしで解きたい、ということについて
僕が初めてこの問題を見た時、まずほぼ確でmod3使うんだろうなーと思いました。だって明らかに怪しいポイントが多すぎます(笑)
まず定数項の9が怪しいです。mod3にかければ消えます。またnが3乗なのも怪しいです。なぜなら、3乗なら連続3整数になる可能性があるからです。
それでやってみたらやっぱりそうだった、みたいな感じです。
(因みに、こんな風に係数や定数項の数を怪しむというのも意外と大切です。作問者が意味もなくその数値にしたと思いますか?)
今はしっかり実験しましょう。ただ、それこそ「感覚」が身に付いたらこういう見方もできるようになります。

$2以上の整数nに対し、nとn^{2}+2が共に素数となるのはn=3の場合に限ることを示せ。$

これも京大の過去問です。
いやーこの問題は親切ですね。なんせ「mod3を使え」って問題文に書いてあります(笑)。これこそ実験するまでもありません。(まぁ実験してみるのもいい経験になるでしょう。)
もう少し詳しく言うと、性質3ですね。つまり、2つの式のどっちかは確定で3の倍数となることを示せばよさそうです。先程の解説を見た人は楽勝で方針が立ってほしいところですね。

解答
$以下、法を3とする。$
$n^{2}+2≡n^{2}-1=(n-1)(n+1)$
$ここで、(n-1)n(n+1)≡0より、$
$n,n^{2}+2の少なくとも1つは3の倍数である。…①$
$(i)n=3$
$この時、n^{2}+2=11より、適当。$
$(ii)n^{2}+2=3$
$nは2以上の整数だから、これを満たすnは存在しない。(証明終)$

①がポイントです。連続3整数は元々積の形になっているとは限りません。自分で作りに行けばいいのです。
また実際に実験してみると、どっちがが3に倍数になるよう作られています。

さて、そろそろ「構造を理解する」の意味がわかってきましたか?
もしかしたら気づいていたかも知れませんが、問題1も問題2と問題3は構造的には全く同じですよね。一見違う問題に見えても、同じ構造があの手この手と言い方を変えて出てきているにすぎません。入試にはこういうケースが非常に多いです。だから構造を覚える、というか理解することが重要なのです

$素数a,b,cが$
$a-b-8$
$b-c-8$
$が共に素数となるという条件を満たすとする。$
$この時、aをbを用いて表せ。$

え、c関係なくね?って思ったそこのアナタ。すいません、これは一橋大の過去問の改題です。ちなみに、元の問題はa,b,cを全て求めよでした。勝手に誘導をつけた感じです。
さて、前の4題との最大の違いはなんでしょうか。(まぁもう改題しちゃってるのでわかると思いますが)少し考えてみてください。
はい。文字が複数あることですね。これは嫌ですねー。嫌なら消してしまえばいいのです。
前回の記事でも言いましたが、「何が邪魔か」を考えるようにしてください。ちなみに、「bを用いて表す」ということも意図があります。
元の問題はa,b,cを全て求めよでした。これを考えやすいようにするために文字消去をするんですが、どの文字に統一すればよいでしょうか。
今回、2つの式両方にbが登場しているのでbが妥当でしょう。
ここで、素数関連の文字消去の方法について紹介します。

素数関連の文字消去

(A)性質2を使う
「偶奇を考える・大小評価をする」ですね。これは素数という超強力な制約を活かしています。偶奇を考えると言っても、「偶数→2を確定させる」というのがメインです。素数問題で複数文字が出てきた場合、この条件を使えるケースが非常に多いです。
(B)分数型への強制変換
前回の記事の内容です。前回触れなかったんですが、分数型への強制変換は実質的な文字消去です。前回の記事を見直してみればわかると思います。
また、素数は分数型と非常に相性がいいです。分数型の基本の考えは「約数による絞り込み」でしたね。アレ、素数って約数が2つ(マイナスも入れれば4つ)しかありませんよね?これはかなりいいシナジーです。

2つの方法を紹介しましたが、この方法が絶対ではありません。随時考える必要があります。ですが、この2つの方法で解決できる場合が多いのも事実です。特に(A)は優先的に考えて欲しいです。
では、解答へ移りましょう。

解答
$a-b-8が素数だから、a-b-8 \geq 2$
$同様に、b-c-8 \geq 2$
$よって、a>b>c \geq2 である。$
$このとき、a,bは2でない素数だから奇数である。$
$よって、a-b-8は偶数でありかつ素数だから、a-b-8=2$
$よって、a=b+10(答)$

性質2をこれでもかというくらい使っています。
まず、一文字消去(A)を考える時、(奇数)±(奇数)=(偶数)という基本的な性質を使うことがかなり多いです。なぜなら、2以外が全て奇数である素数と相性がいいからです。
ですが、今回これを使うためには素数a,bが2でないことを保証する必要があります。これを使うために「大小評価」を利用します。
大小関係によって2があり得なくなる、という流れも頻出です。
最後の、偶数かつ素数だから2というのは性質3に通づるものがありますね。

また、「いずれも素数となる」という条件が頻繁に出てきていますが、それに関するかなり詳しい記事を見つけたので、是非ご活用ください。
bloom様「いずれも素数系完全攻略」

問題を通じてわかること

さて、今まで4題を扱ってきました。
振り返って見てほしいんですが、今回難しい式変形をしたでしょうか。
前回の分数型の処理は結構難しい変形があったりしたんですが、今回は1つもしていません。
modの処理が難しかったかもしれませんが、それはmodが難しいのであって素数が難しいのではありません。
今回使ったのは、すべて最初に紹介した4つの性質です。
逆に考えれば、素数が出てきたらこの4つの性質を意識すれば基本okってことです。
もし解けないのならば、それは素数ではない別の何かが足りていない可能性が高いです。

練習問題

素数の性質1〜4をしっかり意識しましょう。
(現在続きを作成中です。更新までお待ちください。)

京大2021(文)

$pが素数ならばp^{4}+14は素数となり得ないことを示せ$

ヒントを開く(クリック)

素数の性質1〜4を使えないか考えましょう。それでも方針が立たない場合は実験です。


解答を開く(クリック)

$以下3を法とする。$
$pとp^{4}+14が共に素数となるようなpが存在すると仮定する。$
$p^{4}+14≡p^{4}-1≡(p^{2}+1)(p^{2}-1)$
$ここで、(p^{2}-1)p^{2}(p^{2}+1)は連続3整数の積だから、p^{2},p^{4}+14のいずれかは3の倍数である。$
$p^{4}+14は素数の時、3の倍数すなわち3にはなり得ない。$
$よってp^{2}が3の倍数である。$
$今、pは素数だからpも3の倍数であるからp=3である。$
$この時、p^{4}+14=95となりこれは素数でないから矛盾。$
$以上より題意は満たされる(証明終)$


解説を開く(クリック)

最初の1行が最大のポイントです。
「pが素数なら(与式)は素数となり得ない」を「pと(与式)は共に素数となり得ない」と解釈します。
こうすることで問題3とほぼ同じ問題になります。
実験すると「どっちかが3の倍数」になります。mod3で構造を解き崩しましょう。
まぁでもこのくらいの問題なら問題を見た瞬間にmod3を予感してほしいところです。定数項+14が怪しすぎるからです。mod3にかければ-1となるので因数分解できるようになります。
さて、その後の流れですがいつも通り連続3整数積を作ります。
$p^{2}-1$を因数分解するかどうかですが、まぁ正直どっちでもいいです。今回はpが素数でありp^{2}でも対応できるため因数分解しませんでした。
(ちなみにここでは、
$pが素数の時、p^{2}がkの倍数ならpもkの倍数$
という超絶重要性質を使っています)
また、背理法を使っていますが少し解説したいと思います。

整数と背理法は相性がいい

まず整数問題が他の単元とは浮いているように見える理由は、その最大の特徴「離散性」にあります。
離散性とは、飛び飛びの値を取ると言うことです。もう少し詳しく解説しましょう。
我々が普段の数学で扱っているのは基本「連続量」です。関数の問題などでは、整数以外にも小数、分数などすべての値を取りますよね。グラフで言えば、点がすべて繋がって線になっているイメージです。
対して、「離散量」である整数は、文字通り整数しか取りません。小数などは取りません。グラフで言えば、点が打ってあるけど線では繋がっていないというイメージです。
これが整数最大の特徴で、この超強力な性質があるから有限化ができるのです。
さて、では背理法と相性がよい理由です。背理法の基本の流れは
①示したいことを否定する
②その仮定から矛盾を導く
③最初の否定が誤りであるという結論
です。一つずつ見ていきます。
①
例えば「pは素数であることを示せ」と言われたとします。仮定を否定します。するとpは合成数(自然数で、1とその数自身以外の約数を持つ数)だと仮定できるので、p=stなどと置けます。
「nは奇数であると示せ」などと言われれば、これを否定しn=2kなどと置けます。
この感覚がわかりますか?つまり、整数においては「仮定を否定することによって定量化しやすくなる」という場面が非常に多いです。
②
整数には「離散性」という超強力な条件があります。これを逆手に取ると、矛盾が示しやすいということになります。
また、条件が強ければ強いほど矛盾を示しやすいという感覚もわかりますか?特に素数なんかは最強に強い性質です。なんせ素数の①~④の性質に引っ掛からなかった瞬間アウトになるので。

絶対に背理法なんてことはありません。数学的帰納法とももちろん相性がいいです。あれは離散量に関する証明なので。また、特殊な手法を用いずにフツーに証明する場合も全然あります。ただ、今述べた性質に当てはまりそうな時は優先的に背理法を考えるべきでしょう。

終わりに

さて、素数とは友達になれたでしょうか?
今回見ていただいた通り、素数は非常に強力な友達です。素数を見たら「ラッキー」と思えるようにしてください。
次回は平方数を扱う予定です。
それでは次回まで。

投稿日:9日前
更新日:7日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

入試数学しかやりません

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中