あー, おなかいたい......
みなさんこんばんは.
ある日曜数学者です.
固有名詞化しつつある「ある日曜数学者」という単語ですが, 今度から「オペラ座の日曜数学怪人」と名乗ろうか「仮面の日曜数学者」と名乗ろうか迷っています.
先日から胃がきりきりする事態に襲われていて, 仕事をしているとき以外は寝ている生活をしていました. 最近, ストレスフルな生活が続いているせいでしょうか......
(しにそう
さて, 今日のテーマは次の記事にインスパイアされたものです.
tsujimotterさんは「$3^{100}$を$19$で割った余り」を求める4通りの方法を紹介されていました.
すなわち
1. 直接計算してぶん殴る方法.
2. 合同式を用いて, 周期性を見つける方法.
3. フェルマーの小定理を用いる方法.
4. 平方剰余の相互法則を用いる方法.
の4つです.
さて, この記事を読んでいた私は, この問題を「多項式の割り算によって解けないだろうか? 」と思いつきました.
というのは下にあげるような類題を「多項式の割り算」を用いて解いたことがあるからです.
「$2^{100}$を$7$で割った余りはいくつか?」
当然この問題も上の1~4のやり方でも解くことができますが, 次のように多項式の割り算によって解くこともできます.
解法
まず, 次の事実に注意する.
\[x^{33}-1=\left(x-1\right)\left(x^{32}+x^{31}+\cdots +1\right)\]
すなわち,
\[x^{33}=\left(x-1\right)\left(x^{32}+x^{31}+\cdots +1\right)+1\]
すると, $7=2^3-1$であるから,
\begin{align*}\left(2^3\right)^{33}&=\left(2^3-1\right)Q\left(2^3\right)+1 \\2^{99}&=7\cdot Q\left(2^3\right)+1\end{align*}
ただし, \[Q\left(x\right)=x^{32}+x^{31}+\cdots +1\]である.
よって,
\[2^{100}=7\cdot 2Q\left(2^3\right)+2\]
であるから, 商と余りの一意性より$2^{100}$を$7$で割った余りは$2$である.
で, この解法を元の「$3^{100}$を$19$で割った余り」に応用することができるかなと思ったのですが......
結論から申し上げると不可能なようです. 上の解法は割る数が$2^n-1$という形になっていたので, 上のようにできたのですが, 今回はそうなっていません. せいぜい$19=3^3-8$とできるくらいです.
この変形を使うと, 次のような事実がわかりますが, 正直そんなに簡単にならないです.
「$3^{99}$を$19$で割った余りと, $2^{99}$を$19$で割った余りは等しい. 」
証明のようなもの
次の事実に注意する. \[a^n-b^n=\left(a-b\right)\left(a^{n-1}+a^{n-2}b + \cdots + ab^{n-2}+b^n\right)\]
すると, \[\left(3^3\right)^33-8^{33}=\left(3^3-8\right)Q\left(3^3, 8\right)\]
ただし, \[Q\left(a, b\right)=a^{n-1}+a^{n-2}b + \cdots + ab^{n-2}+b^n\]である.
よって, \[3^{99}=19Q\left(3^3, 8\right)+2^{99}\]
これは, $3^{99}$を$19$で割った余りと, $2^{99}$を$19$で割った余りは等しいことを示している.
んー, あまり面白い発見ではありませんな......
$2^9\equiv3^9\equiv -1\pmod{19}$に気が付けば, すぐにわかる事実ですしね.
そんなわけで, tsujimotterさんの問題に別解を与えることはできませんでしたが, 「ある種の余りを求める問題にはこんな解き方もあるのかぁ」という話でした.
(泣きたくなってきた