（51）の「17^17を256で割った余りを求めよ」の解き方をお願いします🙇🏻‍♀️

Question

🍇こつぶ🐡 · Answer

画像参照

景(けい) · Answer

16^2=256に注目です！

ととろ · Answer

17=16+1 と考えて
(16+1)¹⁷ を2項係数を使って展開すると
16ⁿの項は n≧2 の場合に256で割り切れるから
残りの項だけ考えれば良い、
という感じ
16² = 256

和 · Answer

256が16²ということはなるべく気づきたいところです
（最悪、素因数分解して256=2⁸
そこから17=16+1として、16がポイントになることがわかります

17¹⁷=(16+1)¹⁷
二項定理で展開して
16¹⁷ + ₁₇C₁×16¹⁶ + ₁₇C₂×16¹⁵ + …… + ₁₇C₁₅×16² + ₁₇C₁₆×16 + 1

これらの項のうち、最後の2つ₁₇C₁₆×16 + 1だけは
256(つまり16²)で割り切れません

※そこまでの項は、すべて16²×(整数)の形なので、
256=16²で割り切れて、「256で割った余り」には無関係です

ということで、最後の2項₁₇C₁₆×16 + 1に注目です
この値は17×16+1 = (16+1)×16+1 = 16²+16+1 = 16²+17です
これは16²を超えるので、これ自体はまだ余りではありません
これをさらに16²で割った17が求める余りです

Answers