04-03合同式で理解しておきたいこと

合同式で特に理解しておきたいところでは、合同式の計算性質
べき乗の減算方法、倍数の証明方法を理解して身につける必要があります。

1.合同式の計算性質
 $a≡b(\bmod m)、c≡d(\bmod m)$
 ①和、差、積は普通にできる
  $a+c≡b+d(\bmod m)$
  $a-c≡b-d(\bmod m)$
  $ac≡bd(\bmod m)$
 ②べき乗数もできる
  $a^n≡b^n(\bmod m)$
 ③除は、割る数$r$と法$m$が互いに素のとき、可能
   $ar≡br (\bmod m)$
  は、$r$と$m$が互いに素のとき
   $a≡b (\bmod m)$

2.べき乗の減算方法
  ①$a$が$m$より大きい場合、$a≡mk+b≡b(\bmod m)$となることと
   $a^n≡b^n(\bmod m)$を利用します。
   
  ②$a$を何乗かすると$m$より大きくなるので、
   その部分を計算して、小さい$c$にします。
   $a^n≡mk+c≡c(\bmod m)$
   
 (例)$2019^{2019}$を$5$で割ったときの余りを求めよ。
  ①$2019≡5\times403+4≡4(\bmod m)$
  ②$4^2≡16≡3 \times5+1≡1(\bmod m)$
 つまり
  $2019^{2019}\equiv4^{2019}\equiv4\cdot(4^2)^{1009}\equiv4(\bmod5)$となる
 すなわち、$2019^{2019}$を$5$で割ったときの余りは4

3.倍数の証明方法
 $n$で割るとあまりが$a$になるというような証明の場合
 法を$n$として証明します。
 $n$のべき乗から余りを簡単に計算できるので、重宝します。
 
 (例)$n$を自然数とするとき、$n^5-n$は$5$の倍数であることを証明せよ
  $n=0、1、2、3、4$について$n^2-n(\bmod5)$を計算してみると
  下表のようになり$n^2-n≡0(\bmod5)$となる
  つまり、$n$を自然数とするとき、$n^2-n$は$5$倍数である。
  
  

シェアする

  • このエントリーをはてなブックマークに追加

フォローする