<問２>素数p,qを用いて、
p^q+q^p
と表される素数をすべて求めよ。(p^qはpのq乗を表す)
---------------------
解説は下にスクロールしたところにある
スポンサードリンク
-----------------------
<解説>
(´・ω・`) 「だいたいこういう問題は1つか2つぐらいしか答えがなくて、その答え以外に解答がないことを証明すればいいんだよね。」
(´・ω・`) 「とりあえず、とっかかりがないとわからないのでpやqにいろいろ素数を代入してみよう」
まず、p=2、q=2を代入してみるp^q+q^p=4で素数ではない。
次に、p=2、q=3を代入してみるp^q+q^p=17で素数。
p=3,q=5を代入してみるp^q+q^p=368、偶数なので素数でない。
(´・ω・`) 「あれ？もしかして、pが奇数かつqが奇数の時は偶数になるからp^q+q^pは素数にならないのでは・・・・」
(´・ω・`) 「よし、これで少し証明を書いてみよう」
-----------------
(証明途中まで)
pが奇数かつqが奇数と仮定したら、p^q、q^pは奇数なので、
p^q+q^pは偶数。
p^q+q^p=2にはならなさそうなので、
pが奇数かつqが奇数の時、p^q+q^pは素数にならない。
またp=2,q=2の時は、p^q+q^p=4で素数にならない。
-----------------
(´・ω・`)「さあ、次はp=2でqは2以外の素数でp^q+q^pが素数になるものを探すか」
p=2,q=3の時、p^q+q^p=17で素数
p=2,q=5の時、p^q+q^p=57で3の倍数なので素数じゃない
(全ての位の数字を足して3の倍数になれば、その数字は3の倍数)
p=2,q=7の時、p^q+q^p=177で3の倍数なので素数じゃない
・・・・・・
(´・ω・`)「あれ？q=3以外では、3の倍数になるんじゃね？」
(´・ω・`)「じゃあ、2^qとq^2の3で割ったときの余りを考えてみよう」
2^1=2を3で割ると余りは2
2^2=4を3で割ると余りは1
2^3=8を3で割ると余りは2
2^4=16を3で割ると余りは1
・・・
(´・ω・`)「これって3で割った余りが2,1,2,1,2,1・・・って続くんじゃね？」
(´・ω・`)「それでqが奇数の時は、2^qを3で割ったときの余りは2やわ」
(´・ω・`)「まあ、この証明は後でしよう」
(´・ω・`)「次にq^2を3で割ったときの余りを考えよう。q=3以外はqは素数なので余りが1か2やね。」
(´・ω・`)「mを正の整数として、q=3m+1 or q=3m+2の時、q^2は3で割ったときの余りが1だ。」
(´・ω・`)「となると、2^qを3で割ると余りが2でq^2を3で割ると余りが1だから・・・」
(´・ω・`)「q=3以外の時、2^q+q^2は3で割ると、余りが3になるぞ。」
(´・ω・`)「お？q=3以外の時、2^q+q^2は3の倍数になるから素数にならないぞ」
-----------------
(証明続き)
p=2でqは2以外の素数の時、
p=2,q=3の時、p^q+q^p=17で素数
p=2でqは3以外の素数の時を考える。
mを正の整数として、q=3m+1 or q=3m+2と表せる。
（qは素数なのでq=3以外でqは3の倍数にならない）
q=3m+1の時、
q^2 =(3m+1)^2=3（3m^2+2m)+1で、q^2を3で割ったときの余りは1
q=3m+2の時、
q^2 =(3m+2)^2=3（3m^2+4m+1)+1で、q^2を3で割ったときの余りは1-①
2^n(nは正の整数)を3で割った余りは、nは奇数の時は2と仮定する。
n=1の時、2^n=2で3で割った余りは2で成り立つ。
n=k（奇数）で、2^kを3で割った余りは2となったとき(aは整数として、2^k=3a+2の時) 、
2^(k+2)=3(4a+2)+2となり、n=k+2(奇数)の時も2^nを3で割った余りは2になる。
数学的帰納法より、2^n(nは正の整数)を3で割った余りは、nは奇数の時は2である。-②
①と②より、
p=2でqは3以外の素数の時、p^q+q^pは3の倍数になる。
p^q+q^p=3ということはなさそうなので、
p=2でqは3以外の素数の時、p^q+q^pは3の倍数で素数でない。
これらをまとめると、
p=2,q=3の時、p^q+q^p=17以外にp^q+q^pは素数にならない。
(証明終)
-----------------
(´^ω^`)「こういう入試問題は、解けるように作ってあると考えると解きやすいね」
0 件のコメント:
コメントを投稿