読者です 読者をやめる 読者になる 読者になる

Sokratesさんの備忘録ないし雑記帳

思考の流し台. 駄文注意. 数学以外の話も多い.

$2^{100}$を$7$で割った余りを多項式を計算する方法~tsujimotterさんのおはなしを受けて~

 あー, おなかいたい......

 

 みなさんこんばんは.

 ある日曜数学者です.  

 固有名詞化しつつある「ある日曜数学者」という単語ですが, 今度から「オペラ座の日曜数学怪人」と名乗ろうか「仮面の日曜数学者」と名乗ろうか迷っています. 

 

 先日から胃がきりきりする事態に襲われていて, 仕事をしているとき以外は寝ている生活をしていました. 最近, ストレスフルな生活が続いているせいでしょうか......

(しにそう

 

 さて, 今日のテーマは次の記事にインスパイアされたものです. 

tsujimotter.hatenablog.com

 

 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さんの問題に別解を与えることはできませんでしたが, 「ある種の余りを求める問題にはこんな解き方もあるのかぁ」という話でした. 

(泣きたくなってきた