問題2(整数問題,剰余の計算,レベル3)の解答

 

 

問題:

 

 \(10^{2012}\)を\(63\)で割った余りを求めよ.

 

 

解答1:

 

 \(10^{2012}\)を\(63\)で割った余りを求めるために,自然数\(n\)について\(100^{n}\)を\(63\)で割った余りが,\(n\)についてどのように推移するのか調べてみる.

$$ 100^{1} \equiv 37 \left(mod 63\right) $$
$$ 100^{2} \equiv 100\cdot{100^{1}} \equiv 100\cdot{37} \equiv 3700 \equiv 46 \left(mod 63\right)$$
$$ 100^{3} \equiv 100\cdot{100^{2}} \equiv 100\cdot{46} \equiv 4600 \equiv 1 \left(mod 63\right)$$
$$ \cdot \cdot \cdot $$
$$ 100^{3n} \equiv \left(100^{3}\right)^{n} \equiv 1^{n} \equiv 1 \left(mod 63\right) \tag{1}$$

 この式(1)を用いて,\(10^{2012}\)を\(63\)で割った余りを求める.

$$ 10^{2012} \equiv 100\cdot{100}^{3\cdot{335}} \equiv 100\cdot{1} \equiv 100 \equiv 37 \left(mod 63\right) $$

 

 よって,\(10^{2012}\)を\(63\)で割った余りは\(37\)

 

 

解答2:

 

 \(10^{2012}\)を\(63\)で割った余りを求めるために,自然数\(n\)について\(10^{n}\)を\(9\)で割った余りと\(10^{n}\)を\(7\)で割った余りを求める.これらが\(n\)に対してどのような関係になるのか,まずは\(9\)で割った余りから調べてみる.

$$ 10^{1} \equiv 1 \left(mod 9\right)$$

ここで,\(10^{n}\)を\(9\)で割った余りも\(1\)となる.なぜなら,\(10^{n}\)から\(1\)を引いたら\(9\)が\(n\)個並んだ数となって\(9\)の倍数となるからである.

$$ 10^{n} \equiv 1 \left(mod 9\right) \tag{1}$$

 

 次に,\(10^{n}\)を\(7\)で割ったときの余りを調べてみる.

$$ 10^{1} \equiv 3 \left(mod 7\right) $$
$$ 10^{2} \equiv 10\cdot{10^{1}} \equiv 10\cdot{3} \equiv 30 \equiv 2 \left(mod 7\right)$$
$$ 10^{3} \equiv 10\cdot{10^{2}} \equiv 10\cdot{2} \equiv 20 \equiv 6 \left(mod 7\right)$$
$$ 10^{4} \equiv 10\cdot{10^{3}} \equiv 10\cdot{6} \equiv 60 \equiv 4 \left(mod 7\right)$$
$$ 10^{5} \equiv 10\cdot{10^{4}} \equiv 10\cdot{4} \equiv 40 \equiv 5 \left(mod 7\right)$$
$$ 10^{6} \equiv 10\cdot{10^{5}} \equiv 10\cdot{5} \equiv 50 \equiv 1 \left(mod 7\right)$$
$$ \cdot \cdot \cdot $$
$$ 10^{n\cdot{6}} \equiv \left(10^{6}\right)^{n} \equiv 1^{n} \equiv 1 \left(mod 7\right) \tag{2}$$

つまり,式(1)と式(2)から\(10^{6\cdot{n}}\)は\(7\)で割っても\(9\)で割っても余りが\(1\)であることがわかった.これは言い換えると\(10^{6\cdot{n}}-1\)は\(7\)でも\(9\)でも割り切れる数,つまり\(63\)の倍数であると言える.よって

$$ 10^{6\cdot{n}} \equiv 1 \left(mod 63\right) \tag{3}$$

ここで,求めたいのは\(10^{2012}\)を\(63\)で割った余りであった.それは式(3)を用いて

 

$$ 10^{2012} \equiv 10^{6\cdot{335}+2} \equiv 10^{6\cdot{335}}\cdot{10^{2}} \equiv 1\cdot{100} \equiv 100 \equiv 37 \left(mod 63\right)$$

 

よって求める余りは\(37\)

 

 

 

講評:

 

 まず,\(10^{2012}\)の膨大さに怖気づいてはならない.こういった問題は必ず簡略化の手段があり,見かけ倒しである.もし簡略化の手段がなければこうやって数学の問題として登場すること自体考えられないことである.実際解答にも示した通り,指数というのは剰余(割り算の余り)の上では単なる循環する整数となっており,決して莫大な数値にはならない.なお,解答では\(63\)を\(7\)と\(9\)に分解したり,\(10^{n}\)を\(100^{m}\)に書き換えたりして解答をシンプルにしたが,\(10^{n}\)を\(63\)で割ったときの余りが\(n\)について周期\(6\)になるということを,剰余の式を使って愚直に示しても答えは導き出せる.