累乗数の余りと下位桁の数を求める3つの方法

2^{50}を7で割ったときの余りを求めよ.$ $17^{50}を9で割ったときの余りを求めよ.$  3つの方法を示す.\ 実質的に同じだが,\ 多少のメリット・デメリットはある. {余りの種類は限られているからの余りは必ず循環する. { }\ よって,\ 具体的に書き出して周期性を調べる. 合同式}で指数の底の絶対値を小さくする.}{a^n≡ b^n od p(n:自然数)$}  $[3]$\ 二項定理を利用する. 例えば,\ 7で割ったときの余りでならば,\ 0~6の7種類しかない. よって,\ a^7までに必ず1乗と同じ余りになるものが存在し,\ 以降は循環する. 実際に書き出すのもよいが,\ やはり合同式を用いるのが簡潔で本質的である. このときに用いる公式は,\ 次のように繰り返して導かれる. 公式の適用例  pで割ったときの余りは,\ {(p+b)^nに変形してから二項定理を適用}するとわかる. 二項定理を用いた二項展開式が次である 下線部はpを因数にもつから,\ pで割り切れる.\ よって,\ 最後の項が余りである. 例として4^{10}を3で割ったときの余りを求めてみる. \ 合同式では,\ 下線部は0として扱うから,\ 先の例のように簡潔になる. 9の倍数余りを実際に書き出すと次のように{周期3で循環}することがわかる.     ここでは合同式を用いた解答を示した. \ 7で割ったときの余りであるから,\ {7を超えるところまで2を何乗かする.} \ 3乗で8となり7を超えるから,\ {50乗を3乗ごとにまとめ,\ 8≡1を適用}する. \ 17のように底が大きくなると,\ 具体的に書き出して調べるのは容易ではない. \ やはり,\ 合同式を利用する方法に慣れておきたい. \ 17≡-1od9\ のように{負の剰余を活用}すると圧倒的に簡潔になる. \ 二項定理を利用する別解も示す. \ 9で割ったときの余りは,\ {(9の倍数)+b}^n\ の形にして二項展開して求める. \ 17=91+8\ ではなく,\ 17=92-1\ のように{bの絶対値を小さくする}こと. 13^n-9^n-4^n\ は36で割り切れることを示せ.$ 36で割り切れる4の倍数)-4^n=(4の倍数)}$  $よって (13^n-4^n)-9^n=(9の倍数)-9^n=(9の倍数)}$ $ 4の倍数かつ9の倍数であるから,\ {36で割り切れる.}$ 36=49\ (4,\ 9は互いに素)\ より,\ {4の倍数かつ9の倍数}であることを示す. {合同式で底を小さくする}ことで容易に示すことができる. {a^n-b^n\ の因数分解公式を用いた別解}も重要である.\ この公式は暗記事項である. a²-b²=(a-b)(a+b),a³-b³=(a-b)(a²+ab+b²)\ の一般化である. 整数分野では{因数分解して積の形にする}ことが重要であり,\ この公式が役立つ. この公式は,\ {a^n-b^n\ がa-bで割り切れる}ことを意味しているのである.  3^n-1=(3-1)(3^{n-1}++1)\ より,\ 3^n-1は2の倍数である. これをうまく利用すると,\ 別解のように証明できる. 全ての自然数a}について,\ a⁵の1の位とaの1の位は等しい}.}$  \ \ $a⁵≡ aod5\ (∵\ フェルマーの小定理), また,\ 偶奇で分類して調べると,\ a⁵≡ aod2がすぐわかる. nを自然数とする.$ $ 3^{2n}+4^{n+1}\ は5の倍数であることを示せ.$ $ 19^n+(-1)^{n-1}2^{4n-3}\ は7で割り切れることを示せ. [東工大]$ 5の倍数である.}7で割り切れる 通常は数学的帰納法を用いて証明するパターンだが,\ 合同式を使うと簡潔に済む. {底と指数をそろえる}ことを目指して変形するとまとめることができる. 19は{絶対値が小さい負の剰余}で表す. 2^{4n-3}\ は,\ まず指数部分を簡単にすることを目指す. しかし,\ 整数問題であるから,\ 2^{-3}2^{4n}=182^{4n}\ と分数にすべきではない. よって,\ 上の解答のように変形することになるのだが,\ 慣れが必要かもしれない. 47^{2011}\ の一の位の数を求めよ.$ $21^{21}を400で割ったときの余りを求めよ.$ $99^{100}の下位5桁を求めよ.$ 一の位の数\ 3下線部の項は20²=400で割り切れる下線部の下位5桁は0であるから影響しない.$ {「下何桁の数」}を求める問題も,\ 実質余りを求める問題である. 例えば,\ {一の位の数は10で割った余り,\ 下位2桁は100で割った余り}である. \ 10で割った余りと考え,\ 合同式で求める. \ {2乗ごとにまとめ,\ 7²≡-1\ を利用}すると楽である. \ このように,\ 何乗かして余りが1になるものが見つかれば楽になる. \ 割る数が大きくなると,\ 合同式で底を小さくすることが困難になる. \ このような場合,\ 二項定理が威力を発揮する. \ 割る数400=20²\ を考慮し,\ {21=20+1と考えて二項展開}すればよい. \ 20²がある項は当然400で割り切れるから,\ 後は残った部分を400で割る. \ なお,\ 1^nは記述を省略した. \ {100000=100³で割ったときの余り}だが,\ やはり二項定理が役立つ. \ 100=99-1と考えて二項展開すると,\ 100³を因数にもつ部分は無視できる. \ 残りの部分を実際に計算し,\ その下位5桁を答えればよい.
タイトルとURLをコピーしました