第１２２問の解答

１．問題　［整数の性質］

　整数を入れると、次のような動作をする装置があります。

　入ってきた整数の各位の数の和を求める。これを、整数が１ケタになるまで繰り返す。
　（例）１３２７　→　１＋３＋２＋７＝１３　→　１＋３＝４

  1. 　この装置に、ある数Ａの１１倍の数を入れたところ、７になった。では、この装置にＡをそのまま入れると どんな数が出てきますか。
  2. 　Ｂ＝●●●・・・・●●（７７ケタ全てが●）があります。この装置にＢ×Ｂを入れたところ、７が出てきたそうです。　では、 ●にあてはまる数（１ケタの整数です！）として考えられる数を全て答えてください。　

２．合同式、剰余系について

（はじめに）　

ある整数をこの装置にかけると、元の整数を９で割った余り（ただし９の倍数のときは９）が帰ってくることが分かるので、この問題は９を法とする剰余系で考えると簡単に解けます。ちょうど、マサルさんが夏季合宿で忙しく、今週の算チャレがお休みなので、少し詳しく解説することにしましょう。

（合同式と記法）

　ｎを正の整数とします。整数ａとｂに対して、その差（ａ−ｂ）がｎで割り切れるとき、すなわち、ｎで割った余りが等しいとき、ａとｂはｎを法として合同であるといい、ａ ｂ（ｍｏｄ　ｎ）と書きます。

（合同式の法則）

　等式同様、次の関係が成り立ちます。

  1. ａａ（ｍｏｄ　ｎ）
  2. ａｂ（ｍｏｄ　ｎ）　ならば　ｂａ（ｍｏｄ　ｎ）
  3. ａｂ（ｍｏｄ　ｎ）、ｂ ｃ（ｍｏｄ　ｎ）　ならば　ａ ｃ（ｍｏｄ　ｎ）
  4. ａｂ（ｍｏｄ　ｎ）、ｃｄ（ｍｏｄ　ｎ）、ｋが整数　ならば
    ａ＋ｃｂ＋ｄ（ｍｏｄ　ｎ）、ａ−ｃ ｂ−ｄ（ｍｏｄ　ｎ）、
    ａ×ｃｂ×ｄ（ｍｏｄ　ｎ）、ｋ×ａ ｋ×ｂ（ｍｏｄ　ｎ）

　最後の積の場合のみ証明してみましょう。
　ａｂ（ｍｏｄ　ｎ）、ｃ ｄ（ｍｏｄ　ｎ）より、（ａ−ｂ）、（ｃ−ｄ）はｎの倍数。

　従って、ａ−ｂ＝ｐ×ｎ、ｃ−ｄ＝ｑ×ｎと表されます。
　すると、ｋ×ａ−ｋ×ｂ＝ｋ×（ａ−ｂ）＝ｋ×ｐ×ｎ　となり、
　　　　　ｋ×ａ ｋ×ｂ（ｍｏｄ　ｎ）

　また、ａ×ｃ−ｂ×ｄ＝ａ×ｃ−ａ×ｄ＋ａ×ｄ−ｂ×ｄ
　　　　　　　　　　　　＝ａ×（ｃ−ｄ）＋（ａ−ｂ）×ｄ
　　　　　　　　　　　　＝ａ×ｑ×ｎ＋ｐ×ｎ×ｄ＝（ａ×ｑ＋ｐ×ｄ）×ｎ
　よって、ａ×ｃ ｂ×ｄ（ｍｏｄ　ｎ）

（剰余類と剰余系）　

さて、ｎがある整数のとき、ｎで割った余りは、０，１，・・・、ｎ−１のｎ通りなので、整数全体は、ｎを法として合同な整数どうしを集めてできるｎ個の集まり（集合）に分割されます。

このときできるｎ個の集合を、ｎを法とする剰余類といい、それぞれの剰余類から１つづつとった代表の集まり（例えば、０，１，・・・、ｎ−１）を剰余系といいます。

従って、｛１，２，３，４，５，６，７，８，９｝は、９を法とする剰余系の１つです。

３．解答例（ほとんどの皆さん）

(問題の装置が返す整数)

問題の装置が返す整数は、さきほど挙げた９を法とする剰余系｛１，２，３，４，５，６，７，８，９｝であることを、まず証明しましょう。

ある整数ａをこの装置にかけたとき、最初に返ってくる整数をｇ（ａ）、最終的に返ってくる整数をｆ（ａ）とします。

ａ＝ｐｋ×１０ｋ＋ｐｋ-1×１０ｋ-1＋ｐｋ-2×１０ｋ-2＋・・・＋ｐ1×１０1＋ｐ0とすると１０１（ｍｏｄ　９）から、
ｐｋｐｋ×１０ ｐｋ×１０2 ｐｋ×１０3 ・・・ ｐｋ×１０ｋ（ｍｏｄ　９）となります。（以下ｍｏｄ　９を省略します。）

同様にして、ｐｋ-1ｐｋ-1×１０ｋ-1、ｐｋ-2ｐｋ-2×１０ｋ-2、・・・、ｐ0ｐ0

よって、ｇ（ａ）＝ｐｋ＋ｐｋ-1＋ｐｋ-2＋・・・＋ｐ1＋ｐ0
ｐｋ×１０ｋ＋ｐｋ-1×１０ｋ-1＋ｐｋ-2×１０ｋ-2＋・・・＋ｐ1×１０1＋ｐ0＝ａ
すなわち、ｇ（ａ）ａが分かります。

同様にして、ａ ｇ（ａ） ｇ（ｇ（ａ）） ・・・ ｆ（ａ）となります。

ｆ（ａ）は、題意から１桁の正の整数、すなわち１から９のいづれかとなり、言い換えれば９を法とする剰余系｛１，２，３，４，５，６，７，８，９｝の１つの要素に等しくなります。

例を挙げてみましょう。
ａ＝１２３のとき、ａ ６であり、ｆ（ａ）＝ｇ（ａ）＝６、
ａ＝５６７のとき、ａ９であり、ｇ（ａ）＝１８、ｇ（ｇ（ａ））＝９＝ｆ（ａ）である。

（問１）

Ｂ＝Ａ×１１とします。題意から、ｆ（Ｂ）＝ｆ（Ａ×１１）７。
従って、ｆ（Ａ）×ｆ（１１）７、ｆ（Ａ）×２７。
両辺に５を掛けて、ｆ（Ａ）×１０ ３５、
よってｆ（Ａ）×１ ８となり、ｆ（Ａ）＝８と分かります。

（問２）

Ａ＝●とおきます。
まず、ｆ（Ｂ×Ｂ）＝７から、Ｂを求めましょう。
　ｆ（Ｂ×Ｂ）ｆ（Ｂ）×ｆ（Ｂ） ７＋１８ ２５
よって、ｆ（Ｂ）×ｆ（Ｂ）−２５ ０、（ｆ（Ｂ）＋５）×（ｆ（Ｂ）−５） ０。

これから、ｆ（Ｂ）＋５ ０、またはｆ（Ｂ）−５ ０がまず得られる。
ｆ（Ｂ）＋５０のとき、ｆ（Ｂ）＋５ ９、よってｆ（Ｂ） ４。
ｆ（Ｂ）−５０のとき、 ｆ（Ｂ）５。

あと考えられるケースとして、次のようなものがあるが、これを満たすｆ（Ｂ）はない。

  1. ｆ（Ｂ）＋５ ３、ｆ（Ｂ）−５ ３
  2. ｆ（Ｂ）＋５ ３、ｆ（Ｂ）−５ ６
  3. ｆ（Ｂ）＋５ ６、ｆ（Ｂ）−５ ３

さて、Ｂ＝●・・・●（７７桁）だから、
　ｆ（Ｂ）ｆ（７７×Ａ） ｆ（７７）×ｆ（Ａ） ５×ｆ（Ａ） ４，５。
両辺に２を掛けて、１０×ｆ（Ａ） ８，１０、よって ｆ（Ａ）８，１が分かります。

　　　答：問１： ８、問２： １，８

以上