第122問の解答
1.問題 [整数の性質]
整数を入れると、次のような動作をする装置があります。 入ってきた整数の各位の数の和を求める。これを、整数が1ケタになるまで繰り返す。
(例)1327 → 1+3+2+7=13 → 1+3=4
- この装置に、ある数Aの11倍の数を入れたところ、7になった。では、この装置にAをそのまま入れると どんな数が出てきますか。
- B=●●●・・・・●●(77ケタ全てが●)があります。この装置にB×Bを入れたところ、7が出てきたそうです。 では、 ●にあてはまる数(1ケタの整数です!)として考えられる数を全て答えてください。
2.合同式、剰余系について
(はじめに)
ある整数をこの装置にかけると、元の整数を9で割った余り(ただし9の倍数のときは9)が帰ってくることが分かるので、この問題は9を法とする剰余系で考えると簡単に解けます。ちょうど、マサルさんが夏季合宿で忙しく、今週の算チャレがお休みなので、少し詳しく解説することにしましょう。
(合同式と記法)
nを正の整数とします。整数aとbに対して、その差(a−b)がnで割り切れるとき、すなわち、nで割った余りが等しいとき、aとbはnを法として合同であるといい、a
b(mod n)と書きます。
(合同式の法則)
等式同様、次の関係が成り立ちます。
- a
a(mod n)
- a
b(mod n) ならば b
a(mod n)
- a
b(mod n)、b
c(mod n) ならば a
c(mod n)
- a
b(mod n)、c
d(mod n)、kが整数 ならば
a+cb+d(mod n)、a−c
b−d(mod n)、
a×cb×d(mod n)、k×a
k×b(mod n)
最後の積の場合のみ証明してみましょう。
ab(mod n)、c
d(mod n)より、(a−b)、(c−d)はnの倍数。
従って、a−b=p×n、c−d=q×nと表されます。
すると、k×a−k×b=k×(a−b)=k×p×n となり、
k×ak×b(mod n)
また、a×c−b×d=a×c−a×d+a×d−b×d
=a×(c−d)+(a−b)×d
=a×q×n+p×n×d=(a×q+p×d)×n
よって、a×cb×d(mod n)
(剰余類と剰余系)
さて、nがある整数のとき、nで割った余りは、0,1,・・・、n−1のn通りなので、整数全体は、nを法として合同な整数どうしを集めてできるn個の集まり(集合)に分割されます。
このときできるn個の集合を、nを法とする剰余類といい、それぞれの剰余類から1つづつとった代表の集まり(例えば、0,1,・・・、n−1)を剰余系といいます。
従って、{1,2,3,4,5,6,7,8,9}は、9を法とする剰余系の1つです。
3.解答例(ほとんどの皆さん)
(問題の装置が返す整数)
問題の装置が返す整数は、さきほど挙げた9を法とする剰余系{1,2,3,4,5,6,7,8,9}であることを、まず証明しましょう。
ある整数aをこの装置にかけたとき、最初に返ってくる整数をg(a)、最終的に返ってくる整数をf(a)とします。
a=pk×10k+pk-1×10k-1+pk-2×10k-2+・・・+p1×101+p0とすると10
1(mod 9)から、
pkpk×10
pk×102
pk×103
・・・
pk×10k(mod 9)となります。(以下mod 9を省略します。)
同様にして、pk-1
pk-1×10k-1、pk-2
pk-2×10k-2、・・・、p0
p0
よって、g(a)=pk+pk-1+pk-2+・・・+p1+p0
pk×10k+pk-1×10k-1+pk-2×10k-2+・・・+p1×101+p0=a
すなわち、g(a)aが分かります。
同様にして、a
g(a)
g(g(a))
・・・
f(a)となります。
f(a)は、題意から1桁の正の整数、すなわち1から9のいづれかとなり、言い換えれば9を法とする剰余系{1,2,3,4,5,6,7,8,9}の1つの要素に等しくなります。
例を挙げてみましょう。
a=123のとき、a6であり、f(a)=g(a)=6、
a=567のとき、a9であり、g(a)=18、g(g(a))=9=f(a)である。
(問1)
B=A×11とします。題意から、f(B)=f(A×11)
7。
従って、f(A)×f(11)7、f(A)×2
7。
両辺に5を掛けて、f(A)×1035、
よってf(A)×18となり、f(A)=8と分かります。
(問2)
A=●とおきます。
まず、f(B×B)=7から、Bを求めましょう。
f(B×B)f(B)×f(B)
7+18
25
よって、f(B)×f(B)−250、(f(B)+5)×(f(B)−5)
0。
これから、f(B)+5
0、またはf(B)−5
0がまず得られる。
f(B)+50のとき、f(B)+5
9、よってf(B)
4。
f(B)−50のとき、 f(B)
5。
あと考えられるケースとして、次のようなものがあるが、これを満たすf(B)はない。
- f(B)+5
3、f(B)−5
3
- f(B)+5
3、f(B)−5
6
- f(B)+5
6、f(B)−5
3
さて、B=●・・・●(77桁)だから、
f(B)f(77×A)
f(77)×f(A)
5×f(A)
4,5。
両辺に2を掛けて、10×f(A)8,10、よって f(A)
8,1が分かります。
答:問1: 8、問2: 1,8
以上