こんにちは。horyです。
整数で素数が絡む問題は目にしたことが誰でもあると思います。
今回は素数が絡む問題のポイントと攻略を中心に記事をまとめました。
素数とは・・・
素数とは「1と自分自身以外に約数をもたない数」のことです。
例えば、「2」「3」「5」「7」は素数であると言えます。
1は素数ではないと約束します。
素数で大事なのは、偶数の素数は「2」のみということ・「2」以外の素数は全て奇数ということです。
また、問題を解く上で以下の3点が重要になってきます。
(というか整数問題全般で重要)
- (約数)×(約数)の形にする
- 余りで判別する
- 範囲の絞り込みを用いる
上の3つの重要性は以下の記事でも説明しているので読んでおいてください。
問題1_因数分解を利用
因数分解を利用する問題です。
この問題ですが、無理矢理因数分解の形に持ち込んで「（約数）×（約数）」の形に持ち込みます。
約数の大小を考えて絞り込めるとベストです。
問題1 解答・解説
xが自然数なので・・・約数の大小関係が分かります。
素数なので・・・
ここで落とし穴ですが、ここで解答をやめたら減点されます。
なぜなら、「x=1」を求めたことは必要条件を求めただけで、十分性の確認をしなければなりません(本当に素数になってるかどうか分からない)。
以上が解答になります。
問題2_余りで判断
以下は余りで判断する問題です。
一見難しそうに見えますが見かけ倒しです。
ところで・・・最初に以下のことを言いました。
- 偶数の素数は2のみ
- 2以外の素数は全て奇数
そして、整数の和について(0は偶数)・・・
- 偶数+偶数=偶数
- 偶数+奇数=奇数
- 奇数+奇数=偶数
になります。なので・・・
問題2 解答・解説
以上より、a,bのどちらか一方は必ず2になります。
a,bは等価なので、今回は「a=2」として考えます。
を考えます。平方数が出てきました。余りで分類する方法が使えそうです。
試しに「b=3」を代入してみます。
素数を1つ求めることができました・・・
ところで、「こんな感じで無限に求めないといけないの？」と思うかもしれませんが、
このような問題では、条件を満たすものをいくつか見つけたら、そこから新しいモノを見つけるのではなく、「これ以上見つからないこと」を示すのが有効です。
今回であれば・・・
以外に存在しないことを示します。
前回の記事でも説明しましたが、「平方数を特定の数で割ると余りは特定になる」という面白い性質があります。
今回は3の倍数に注目します。
以上から平方数を3で割った余りに2は存在しないです。
また、2のb乗については二項定理を利用します。
bは2以上の素数(奇数)ということを思い出すと本問では3で割った余りは必ず2になります。
よって、bが3の倍数以外の時は全て3より大きい3の倍数になるので素数になりません。
だから、bが3の倍数の時、素数となり、bも素数なので「b=3」です。
aとbは等価なので・・・
以上が解答になります。
