高校入試問題

2^29(2の29乗)は9桁の正の整数であり、すべての桁が異なっている。
実際に計算することなく、0以上9以下の整数のうち2^29の桁には入ってない数字を求めよ。


解答解説

まず、この問題をみた時に、これだけでは全く見当がつかないと思います。
そこで文章を見直してみましょう。「9桁」で「全ての桁」が異なっていて、「入ってない数字」を求めるとあります。
2の29乗という膨大な計算量だと各桁をa+10b+100c…と考えるのも難しいと思います。
ところで、膨大な累乗数においてもそれをある整数で割った時の余りはわりと簡単に求まるのは有名です。
x^yはそれを何かで割った余りを考えれば解けることは非常に多いです。
ここで、2^29を何かで割った余りを求めれば解けないかを考えます。

9で割った余りは、全ての桁の数字の和を9で割った余りと同値です(3の場合も同じ)。

これは中学受験などでもよく使う大事なことです。
0+1+…+9=45=5×9
含まれてない数字をaとします。
すると2^29の各桁の和は45-aになります。
aは1~9なので45-a=4×9+(9-a)・・・① (9-aが余りになる)

次に2^29を求めようとしましょう。
その前にa≡p (mod n), b≡q (mod n)のとき、
ab≡pq (mod n)であることを証明します。
a=nt+p, b=ns+q (t,sは整数)であるので、
ab=tsn^2+(tq+sp)n+pq であり、これをnで割った余りはpqなのは明らかです。
このことより、
大きな数を何かで割った余りを求めるときには、その数を分解して一つ一つの余りの積を考えればいいです。

ここで元の問題に戻りましょう。
2^6≡1(mod 9) なので

2^29 (mod 9)
=2^6×2^6×2^6×2^6×2^5 (mod 9)
≡1×1×1×1×2^5 (mod 9)
≡2^5=32 (mod 9)
≡5(mod 9)・・・②

①、②より、9-a=5, a=9-5=4
よって求める値は4です。

最後に、ここでは使いませんでしたが
フェルマーの小定理について触れておきます。
pを素数、aをpと互いに素な整数とすると互いに素:最大公約数が1である
a^(p-1)≡1 (mod p) (a≡b (mod p) というのは、a,bをpで割った時の余りが等しいということです)
これはaの(p-1)乗をpで割ると余りは1になる、という有名な定理です。