若人は浪人生

東西を股にかける(うろうろする)浪人生の物語

【数学】整数問題の解法と罠 part2


 こんにちは、しぃと申します。

 早速、前回の続きです。

2.余りで分類

 これも因数分解と同じほど整数問題で見かけます。

例題


             2         n          =              3          m - 1      + n 2  
を満たす正の整数の組(m,n)をすべて求めよ









        

【解説】

 因数分解がきつそうなので整数の余りを考えます。2の倍数、3の倍数……と小さいものから値の候補を絞ります。




(1)m=1のとき

 2ⁿ=n²+1

これを満たすのはn=1
(厳密にはn=2,3,4で等式が成り立たないことを調べて、帰納法でn≧5で 2ⁿ>n²+1 を示せばよい)



(2)m≧ 2 のとき
 左辺は偶数だから、右辺も偶数。よってnは奇数である。

 よって、n=2k-1(kは正の整数)とおける。
ここで

2 2k - 1   = 2 4 k - 1

であるから、3を法として合同式を用いると、

2ⁿ≡2

一方、
n²≡0,1 だから

(右辺)≡0,1

したがって、与式は成り立たない。

故に、(m,n)=(1,1)




【ポイント】

 ポイントは合同式です。その紹介を少々。
(ご存知の方が多いと思いますが……)


整数pを整数qで割った余りがr(q>r)のとき、
“p≡q(mod r)”
と表記します。
 mod r は「r を法として」ともいいます。

これを用いるとかなり記述がスッキリします。




 例えば、「整数nが4で割ってあまり3のとき、n³ を3で割った余りを求めよ」

という問題で、合同式を用いなければ、
      n=4k+3
とおいて(4k+3)³ を計算する必要がありますが、合同式なら、

3³≡27=4×6+3≡3(mod4)

と表現できます。





 初めて知った!という方は教科書や青チャート等の参考書を見るのをオススメします。
 
 ネットだと細かいところが抜けていることが多い気がするので(特大ブーメラン)





 


 さて、整数問題でまず確認して欲しいのが偶奇ですね。



 等式の偶奇がどのような条件で一致するのかを調べるのが定石です。


 
 また、3の倍数のチェックもよく使いますね。
おそらく3の倍数が絡む問題が1番多いです。



 特に覚えたいのが、n² (nは整数)を3で割った余りも4で割った余りも0,1のいずれかになることですね。



 普通にn=3k,3k+1,3k+2 とおいて二乗してあげれば証明出来ますし、合同式を用いると、

0²≡0
1²≡1
2²=4≡1

と証明できます。(4の倍数も同様)




 よくある入試問題として、整数nの多項式素数であるnを求める問題があります。


 だいたいこのような問題では、多項式は偶数あるいは3の倍数となるので、nを2や3で割った余りで場合分けしてあげて、素因数を持つことを示すパターンが多いです。

 こういう問題では調べるのが煩雑になりやすいので、合同式が光りますね!


 






以上で解説を〆とします。

ごちゃごちゃしててすみません。



 スマホで慣れないHTMLで編集したので疲れました(*´Д`*)
 




 それではまた〜