自由研究３−４
下２桁の積
《目次》
１　下１桁の積
２　下２桁の積
３　素因数分解の困難さ
４　京都大学入試問題

■　２桁程度の整数ならば，何で割り切れるか簡単に分かります．しかし，４桁，５桁，．．．となってくると，どのような整数で割り切れるかを言い当てるのは，容易ではありません．（２，５の倍数は直ちに分かります．３，７，９，１１などの倍数も少し計算すれば見分けられます．しかし，横に電卓があれば割った方が速いようです．）

１　下１桁の積
　そこで，下１桁（１の位）の数を見て，組合わせを少しでも絞り込むことができないかどうか考えてみます．２の倍数，５の倍数はいつでも直ちに分かるので，これらについては割れるだけ割って，取り除いておきます．また，２つの整数の積において，結果が１の位に影響するのは，どちらも１の位の数だけです．そこで，１の位の数の積を演算表にまとめたのが次の表です．
　例えば，７×９＝６３ですので，７×９の１の位の数は３です．

積
1
3
7
9
1
1
3
7
9
3
3
9
1
7
7
7
1
9
3
9
9
7
3
1
■　この表は，行（横の並び）と列（縦の並び）を入れ替えても変わりません．（右下に向かう対角線に関して対称です．ｎ×ｍ＝ｍ×ｎだから）
その他，この表には，次のような特徴があります．
 
1.　どの行にも，どの列にも同じ数は登場しません．
2.　どの行にも，どの列にも１，３，７，９が登場します．
3.　積が１，３，７，９となる組合わせは４通りずつあります．
（1.の証明）
行の標題をｎ，列の標題をａ，ｂ（ａ＞ｂ）とすると，ｎａとｎｂが同じ数となるのは，ｎａ−ｎｂ＝ｎ（ａ−ｂ）が10で割り切れるときです．ところが２と５の倍数は取り除いてあるので，ｎは２，でも５でも割り切れません．また２≦a-b≦８なのでａ−ｂも１０では割り切れません．以上により，ｎａ−ｎｂは10で割り切れないので，ｎａ，ｎｂは異なる数です．（列についても同様にして示されます．）
（2.の証明）
1.によりどの行にも同じ数はないので，１，３，７，９が１回ずつあります．（列についても同様）
（3.の証明）
どの行にも１，３，７，９があるので，１，３，７，９はいずれも４回登場します．
■　以上の考察から分かること
　素因数分解をするに当たって，不要な組合わせの検討を省略できれば，画期的なことです．しかし，例えば積の下１桁が３となる組合わせは，１，３，７，９のどの数にもあり，１×３，(３×１)，７×９，(９×７)のいずれも可能です．（）内だけ省略可能です･･･要するに前が大きい方の数になる場合だけは検討しなくてもよいという自明の結論にたどり着きます．

２　下２桁の積
　同様にして，下２桁の数の積を演算表にまとめたのが次の表です．
積 1 3 7 9 11 13 17 19 21 23 … … 97 99
1 1 3 7 9 11 13 17 19 21 23 … … 97 99
3 3 9 21 27 33 39 51 57 63 69 … … 91 97
7 7 21 49 63 77 91 19 33 47 61 … … 79 93
9 9 27 63 81 99 17 53 71 89 7 … … 73 91
11 11 33 77 99 21 43 87 9 31 53 … … 67 89
13 13 39 91 17 43 69 21 47 73 99 … … 61 87
17 17 51 19 53 87 21 89 23 57 91 … … 49 83
19 19 57 33 71 9 47 23 61 99 37 … … 43 81
21 21 63 47 89 31 73 57 99 41 83 … … 37 79
23 23 69 61 7 53 99 91 37 83 29 … … 31 77
… … … … … … … … … … … … … … …
… … … … … … … … … … … … … … …
97 97 91 79 73 67 61 49 43 37 31 … … 9 3
99 99 97 93 91 89 87 83 81 79 77 … … 3 1
1.　どの行にも，どの列にも同じ数は登場しません．
2.　どの行にも，どの列にも１，３，７，９,...，97，99が登場します．
3.　積が１，３，７，９，．．．，97,99となる組合わせは４０通りずつあります．
（1.の証明）
行の標題をｎ，列の標題をａ，ｂ（ａ＞ｂ）とすると，ｎａとｎｂが同じ数となるのは，ｎａ−ｎｂ＝ｎ（ａ−ｂ）が100で割り切れるときです．ところが２と５の倍数は取り除いてあるので，ｎは２，５で割り切れません．また２≦a-b≦98なのでａ−ｂも100では割り切れません．以上により，ｎａ−ｎｂは100で割り切れないので，ｎａ，ｎｂは異なる数です．（列についても同様にして示されます．）
（2.の証明）
1.によりどの行にも同じ数はないので，１，３，７，９,...,97,99が１回ずつあります．（列についても同様）
（3.の証明）
どの行にも１，３，７，９,...97,99があるので，１，３，７，９,...,97,99はいずれも40回登場します．
■　以上の考察から，下２桁の組み合わせを検討しても，積が交換可能であることを除いて省力化できる材料はありません．

３　素因数分解の困難さ
　暗号は，軍事・外交などの秘密を要する分野ばかりでなく，預金の送信など通信を用いた社会生活において不可欠なものになっています．今日最も信頼度の高い暗号は，公開鍵方式と呼ばれるもので，素因数分解の困難さに依存しています．
　素因数分解の困難さとは，桁数の大きな２つの素数の積（１００桁×１００桁程度）だけを公開しておいて，もとの２数を隠しておけば，これを素因数分解するには，高速なコンピュータを用いても何千億年もかかるということです．このような大きな数で暗号化すると，文章を復元できるのは（事実上）もとの２つの素数を知っている本人だけになり，（事実上）安全な通信が行えるようになります．

　素因数分解の困難さを覆す何らかの方法が見つかれば，通信の安全性が保障されず，社会生活が混乱してしまうおそれがあります．しかし，実際にやってみると分かるように，５桁程度の整数の素因数分解でも，事実上「力まかせの総当たり」でいくしか仕方ありません．下何桁を見て絞り込むことさえほとんど見込みはありません．こんな訳で，桁数の大きな整数の素因数分解が困難であるからこそ，通信が安全に行えるということで，この問題が難しいことについて納得してください．


４　京都大学入試問題
　受験問題に興味のある方のために，参考までに１９９９年度前期京都大学入試問題を紹介しておきます．なお，入試問題そのものには，素因数分解との関わりは一切触れられていませんので，このような文脈の中で紹介するのは，このホームページ作者の個人的な好みのせいであることを断っておきます．
 
　０以上の整数ｘに対して，Ｃ(ｘ)でｘの下２桁を表わすことにする．たとえば，Ｃ(12578)＝78，Ｃ(6)＝6である．ｎを２でも５でも割り切れない正の整数とする．
(1)　ｘ，ｙが０以上の整数のとき，Ｃ(ｎｘ)＝Ｃ(ｎｙ)ならばＣ(ｘ)＝Ｃ(ｙ)であることを示せ．
(2)　Ｃ(ｎｘ)＝１となる０以上の整数ｘが存在することを示せ．
（１９９９年度前期京都大学入試問題の引用）
答案
(1)　ｎｘ−ｎｙ＝ｎ（ｘ−ｙ）が100で割り切れるとき，ｎは２でも５でも割り切れないから，ｘ−ｙが100で割り切れる．ゆえに，Ｃ(ｘ)＝Ｃ(ｙ)．
（Ｃ(ｘ)≠Ｃ(ｙ)ならば，ｎ（ｘ−ｙ）は１００で割り切れないといってもよい．）
(2)　(1)の結果により，２でも５でも割り切れないどんなｎについても，Ｃ(ｎ・０)，Ｃ(ｎ・１)，Ｃ(ｎ・２)，Ｃ(ｎ・３)，．．．Ｃ(ｎ・９８)，Ｃ(ｎ・９９)は異なる数となるから０，１，２，３，．．．，９８，９９が１一回ずつ登場する．したがって，Ｃ(ｎｘ)＝１となる０以上のｘが存在する．

←←メニューに戻る　←問題に戻る