第二回、量子コンピュータ(第一回)


前口上

これから3回にわたって量子コンピュータを取り上げて講義します。インターネットで「量子コンピュータ」というキーワードで検索すると、実に多くのページがひっかかることからわかるように、ここ数年量子コンピュータが話題を集めるようになってきました。実際、日本においても量子コンピュータが話題になっており、多くの人材と研究費が投入されています。けれども、その研究費を支払っている多くの市民にとって、「量子コンピュータって何?」と思うのが実情でしょう。この講義では、量子コンピュータとはなにか、そして量子コンピュータの意義とはどれほどのものか、ということを簡単にわかりやすく紹介したいと思います。

この講座を開くにあたって多くのWebページを調べてみました。下の参考文献に挙げられているように、いくつかのサイトで有用な情報が手に入ります。しかしながら、いずれも「量子コンピュータ」を専門的に扱いたい人を対象にした解説であるか、もしくは新聞記事に代表されるような、表層的な知識の伝達にとどまっているかの、いずれかです。ですので、インターネット講座として、量子コンピュータについてある程度つっこんだ解説記事をWebに掲載することは、意義あることと考えています。

この講義では、「整数論」にも焦点をあてることにしましょう。数学の分野の中でも「整数論」は、もっとも応用から離れた分野だと思われているかもしれませんが、意外なことに現在のコンピュータネットワークにとって、大切な地位を占めています。しかも簡単な整数論をしっていれば、おおまかな理解は可能です。「整数論」という分野のもつ奥深さを味わってもらうことにしましょう。

前口上はこのぐらいにして、さっそく本題に入ることにしましょう。

量子コンピュータとはなにか

まず、量子コンピュータとは何か、について概略をお話しましょう。

今現在普通に使われているコンピュータの内部では、数字は必ず2進数で表されます。例えば

00101101 <--- 45
11111111 <--- 255

などのようになります。このようにすると0から255までの数字は8桁の二進数で表すことができます。二進数にするメリットは、このようにすることで、数字を0と1の電気信号で表すことができるからです。例えばこれらの数字をメモリに記憶させるには、ある場所に電気がたまっていたら1,たまっていなかったら0として、そのような場所を8個用意すればいい。そうすることで0から255の数を区別することができます。このような0か1かを決める記憶の単位をビットといいます。0から255までを区別するのに8ビットの記憶容量が必要、などのように使います。

仮に8ビットのメモリAがあったとしましょう。このメモリAに対して、演算を行うことを考えます。演算とは加減乗除のような四則演算を含む数字の加工のことです。普通のコンピュータでは、メモリAの内容はただ一つです。例えばA=00101101(=45)のような感じです。メモリには、ただ一つの値が書き込まれているぞ、ということを

| A > = | 00101101> ... (0)

と書き表すことにしましょう。| A >という記号はケット記号といいます。普通のコンピュータでは、ある時刻にメモリAに書き込まれている状態は、ただ一つしかありません。このようなメモリを用いたコンピュータを、古典コンピュータと呼ぶことにします。実用化されているすべてのコンピュータは古典コンピュータです。

我々は「ある物体のある時刻での状態は、ただ一つに限られている」と普通は思っています。例えば、さっきのメモリの話では、ある時刻のメモリの状態はただ一つだ、ということです。ところが、このような我々の直感は、原子分子レベルではまったく通用しないことがわかっています。分子や原子ぐらいの小さな物体の振る舞いは、我々の直感を大きく裏切ってしまうのです。このような微視的世界を記述するのに「量子力学」という学問が必要になってきます。

(補足)歴史的には、量子力学の構築は1904年のプランクの光に関する理論を皮切りに、1927年にハイゼンベルクとシュレーディンガーによって集大成されました。間違いなく20世紀初頭のの物理学上の最大の発見といえます。このような大発見をコンピュータという、20世紀後半を引っ張ってきた発明と、本質的に結びつけようとしているのです。ちょっとロマンチックですね。

普通は、メモリと言えども、1ビットの記憶装置には、数千から数万個程度以上の原子で構成されているので、メモリの振る舞いは、我々の日常生活での常識と大きくことなることはありません。ところが、もしメモリを原子レベルの非常に微細なものでつくったらどうなるでしょうか。そうすると、そのメモリの動作は、もはや我々の日常生活に基づく直感から大きく外れてしまいます。直感から外れる振る舞いの最もたるものが、「重ね合わせ状態の存在」です。つまりメモリの例でいえば、「メモリに書き込まれている数値はただ一つだけに限らない。多数の数値の重ねあわせ状態が可能」ということです。

重ねあわせ状態をもう少し説明するのに、先ほどのケットの記号を使うことにしましょう。例えば「メモリAが45(=00101101)と255(=11111111)の重ね合わせ状態である」ということをケット記号で

| A > = a | 00101101> + b | 11111111>  .... (1)

と書きます。ここでa,bは複素数です。なぜこのような形になるのか、というのは、この短いスペースでは解説しきれません。(それこそ量子力学の授業になってしまいます。)しかし、この講義では以下のことだけを了解しておいてもらえば十分です。まず複素数の組(a,b)と、メモリの状態とは対応があります。つまり異なる複素数の組(a,b)と(a',b')は異なるメモリ状態を表しています。ただし一つだけ条件があって、

...(2)

を満たすものとします。これを満たす複素数の一つの例は, (a,b)=(1,0)です。このときは、メモリの状態は

| A > = 1| 00101101> + 0 | 11111111> = | 00101101>

となります。最後の等式では、0がかかったケットは消え、1は省略しました。この状態は、まさしく式(0)で指定された状態そのものです。つまり、A=00101101に確定した状態を表します。つまり式'(1)で表される状態の特殊な場合が式(0)で表されている状態になります。

次に状態(1)をどうやって実現するか?これについては深入りしません。実験家が頑張れば、メモリをそういう状態ができるのだ、ということを信じてください。そのとき、aやbは、人間が思うままにあやつることができます。

最後にaやbは、どのような形で観測されるか?

| A > = a | 00101101> + b | 11111111>

のように始めのビットが違うので、このビットの状態がどうなっているかを調べたとします。その観測結果は二通りあって、

(1) 始めのビットが0 となっていることを観測する、つまり| A > = | 00101101>となっていることを観測する
(2) 始めのビットが1 となっていることを観測する、つまり| A > = | 11111111>となっていることを観測する

のいずれかになります。一回の試行では、このどちらかになること以上のことしかわかりません。しかし、メモリをN個用意して、それぞれのメモリをすべて | A > = a| 00101101> + b| 11111111> としておいたとします。そして、すべてのメモリで始めのビットを観測したとしましょう。するとNを大きくしていく極限で、(1)を観測する割合p(= (1)となる確率)と(2)を観測する割合q(=(2)となる確率)は一定値に近づき、それぞれ

... (3)

となるのです。これが重ね合わせ状態の意味です。式(2)は「全確率を足したら1」を保証するためのものです。

このような重ね合わせの状態も可能なメモリを搭載するコンピュータを「量子コンピュータ」といいいます。本質的に量子力学の原理に立脚しているので、このような名前がついています。

量子コンピュータを研究するそもそもの動機は、「量子コンピュータを使うことで、計算が劇的に早くならないだろうか?」ということです。大まかなアイディアは次のようなものです。量子力学によれば、メモリAの状態として、メモリAがとりうる値すべての重ね合わせ状態というのも可能です。例えばAがnビットメモリからなるとすれば、メモリはまでの数を表すことができます。このメモリの状態の一つのとして、可能な状態のすべて重ね合わせ状態、つまり

... (4)

という状態も可能です。(二進数のところは、10進数に書き直してあります。)さて、このメモリの状態を重ね合わせ状態を崩さずにおのおの別個に数値の加工ができるとします。(そのような演算は原理的に可能であることが知られている。)例えば、メモリの内容がnのとき、加工後はf(n)になるような操作fを考えましょう。この操作を状態| A >に及ぼした後、新しい状態| A'>は、

... (5)

となります。さてこのような演算が可能になるとすると、ある種の計算がとても早く行えると期待できますよね。「0からmまでのすべての整数nに対してf(n)を計算せよ」という問題があったとします。普通に0からmまでの整数を関数f(n)に入れてみるようなことをしなくてはいけません。もしf(n)が一つのnに対して計算が1日かかってしまうとします。すると0からmの全部の整数についてf(n)を計算するのにm日かかってしまいます。ところが上の計算では、たった一回だけメモリAに操作fを作用させるだけで、すべての整数nでf(n)が計算されてしまっているように見えます。この操作に必要な時間は1日で済みますから、計算時間を大幅に短縮できたことになります。別の言葉でいうと「量子コンピュータは、一台のマシンにおける究極の並列計算(何台ものマシンを同時に動かして計算すること)である」のです。

このように量子力学を用いて計算を行うと、効率的な計算が行えるのではないかという期待は、1980年代ほどから言われていました。しかし、実際に「古典コンピュータで時間がかかる計算でも、量子コンピュータなら早く解ける実例」がなかなか見つからなかったのです。先ほど、量子コンピュータ=究極の並列計算といいました。しかし、計算後の状態 (5)を得ても、そこからどのようにして計算結果f(n)を取り出すのか、が実は大きな問題です。先ほどの2状態の重ねあわせの観測結果(3)を思い出してください。せっかく並列計算ができていても、観測できるのはメモリの状態を多数回観測したときの確率なのです。望む結果を得るのにN回観測しなければいけないならば、一日かかる操作fをN回するはめになり、N日かかります。そしてNがあんまり大きいと、せっかくのスピードアップが無に成ってしまうのです。ということで、(4), (5)で考えた並列計算のアイディアは、そのままでは使い物になりません。

このような事情があって、量子コンピュータは最近までは一部の人々をのぞいて、それほど省みられることがありませんでした。しかし、1994年にShorによって「量子コンピュータを使うと、古典コンピュータに比べて因数分解が効率的に(すばやく)行えること」を理論的に証明したことによって、状況が一変するのでした。Shorはこの仕事により、1998年に応用数学分野におけるもっとも権威あるネヴァンリンナ賞を受賞しています。

量子コンピュータの動作原理の続きは、次回に回すことにして、今回の講義では「なぜ量子コンピュータによって効率よく因数分解ができることで、みんなそんなに大騒ぎをするのか?」という点を明らかにしましょう。

コンピュータネットワークにおける暗号技術

ちょっと話を変えて、インターネットでは欠かせない技術と成っている暗号技術について見てみましょう。

インターネットで暗号化が重要な役割を果たしていることは、ちょっと考えればわかると思います。例えば人に読まれて困るようなメールを書くとき、暗号化が必要です。それ以上に、例えばインターネットで銀行との取引を行うとき、取引を要求しているのが本当に本人であるかの認証が必要になります。この認証はパスワードによって行われますが、もしこのパスワードを送る途中でだれかがこの情報を取り出し、パスワードを解析できたら、、、、後は言わずもがなですね。もしも簡単に暗号が破られてしまうと、インターネット上での(リスクなしでの)商取引は事実上不可能になります。

暗号それ自体の歴史は長いです。推理小説ではお馴染みですよね。(シャーロック=ホームズだって踊る人形という短編で暗号解読をやっています。)第二次世界大戦の時には、相手の暗号を破るかどうかが、勝敗に大きな影響を与えたことは有名です。現在では、コンピュータが流通していますから、昔のように暗号化および解読(もとの文章にもどすこと)に人間が手間をかける必要がなくなりました。

さて暗号化する上で大切なことは二つあります。一つは他の第三者が解読するのが困難なこと。これは当然のことですよね。もう一つは、暗号化および解読が比較的容易に行えることです。こちらに対しては注意が必要で、また後で触れることにします。

まず、解読困難な暗号というのは、比較的簡単につくれます。A君とB君の間の通信を考えましょう。あるときお互いにあって、文字コードの取り決めをつくります。例えば、Aを25、Bを13にしよう、などというものです。これを暗号表をいうことにしましょう。これによって、メッセージを数字で送信します。しかし、同じ暗号表を使っていると、文字の出現回数などによってすぐに解読されてしまいます。ですので、ある程度のメッセージを送ったら、暗号表を変えてしまうのです。暗号表1、暗号表2、暗号表3、、、と大量につくっておいて(これはコンピュータの乱数を使えばいい)、次から次へと使い捨てにしてしまう。こうすると、暗号表が漏洩しないかぎり、とても強力な暗号となります。しかし、この暗号の欠点は、、、わかりますよね。事前に出会っておかないといけない。暗号表の取り決めをしなくてはいけないのです。よって出会ったことのない人に秘密のメッセージを渡すことができず、実用化は絶望的です。

現在使われている暗号化の手法は、1978年にR. Rivest, A. Shamir, L. Adlemanの三人によって与えられたもので、3人の頭文字をとって「RSA公開鍵暗号方式」と呼ばれます。この方法のいいところは、まったく初対面の当事者同士でも暗号通信が可能となることです。キーは「公開鍵」と呼ばれる鍵の使用にあります。(しゃれではなく。)そして、この方法は、興味深いことに、その基礎を整数論に置いているのです。

まずは、RSA方式で通信をする手順を先に述べておきましょう。送信者B君が受信者A君に秘密でメッセージを送ることにします。(余談ですが、なぜかこの分野では、A君とB君をAliceとBobと呼ぶことが多い。図ではそうしました。)

0.(準備段階) A君側で二つの素数p, qを用意する。そしてそれらの積n=pqを計算する。次に
... (6)
となる二つの整数e, dを見つける。二つの整数の組(e, n)を公開鍵と呼び、dを秘密鍵と呼ぶことにする。なお合同式≡の記号の意味がわからない人は、補足を読んでください。
1.(鍵の公開)A君は公開鍵(e,n)を常に公開している。送信者Bはこの公開鍵をA君から教えてもらう。
2.(暗号化)送信者Bは、まずメッセージ文章はあらかじめ決められた規則で整数にコード化する。(例えばA=1,B=2,C=3,・・・Z=26などとする。)i番目の文字コードをM_iとする。メッセージはコンピュータ内ではこの整数列M_iによって表現される。これを送信者Bは、Aからもらった公開鍵(e,n)を用いて、整数列M_iから整数列E_i を生成する。
... (7)
E_iが暗号化された整数列である。(読みにくいけど、M_iをe乗したものをnで割った余りということです。)
3.(送信・解読)暗号化した整数列E_iをAに送信する。Aはもらったもらった整数列E_i からもとの整数列M_i を
... (8)
によって解読することができる。

これらの手順を模式的に表したのが以下の図です。

不思議なのは、復元のところでしょう。暗号数列E_i から、もとの数列M_i が

によって求まってしまうのは、不思議としか言いようがありません。どういう仕組みでしょうか。実は整数論の有名な定理であるフェルマーの小定理

をうまく使っているのです。ここでpは素数で、a, pは互いに素な整数です。

(補足)フェルマーは、ルネサンス期に現れた数学者です。近代整数論は、彼に始まったといって、過言ではありません。つい最近証明された「フェルマーの(大)定理」で有名ですね。本文ででてきた小定理は、それに比べればずっと証明が簡単です。どの整数論の本にも載っていますし、群論の応用としてもでてきます。各自調べてみるなり、自力で証明するなりしてみてください。

フェルマーの小定理を前提にして話を進めましょう。p, qを互いに素な整数としていますので、


の二つが同時に成り立ちます。(M_iはp, qと素になるようにとる必要があるが、あとでみるようにp, qは大きい素数を取るので、それより小さなコードM_iを使っているときは、この条件をかならず満たすことができる。)合同式の両辺を整数乗してもいいので、


も成り立ちます。この二つが同時に成り立つときは、

 ... (A)

が成り立つことを証明できます。(任意課題、これを示せ。)n=pqとなるので、もうこれでほぼ証明終了ですね。式(6)より

と書けることに注意します。(kは整数)(7)より

,,, (B)

が言えます。またさらに

... (C)

とかけ、この最後の式が(A)を用いて、

... (D)

となります。((A)の両辺をk乗してさらにM_iを掛ければい。) (B)〜(D)によって、証明したい式、

を示すことができます。証明終了。あざやかですね。

RSA暗号が効率的に実行可能であること

このようなRSA暗号が、実際にコンピュータ上で実現できるでしょうか?というのは、準備段階で次の計算を行わないといけないからです。

(A)大きな素数p, qをみつけること
(B)を満たすような整数e, dを見つけること。

もしもこの計算に非常に多大な時間がかかるならば、この暗号はやはり実用的ではない、ということになります。幸いなことに、この二つは効率的に計算できます。この節で「効率的」とは何であるか、も明らかにしていくことにしましょう。

まず(A)の方から行きましょう。まず乱数によって、適当な素数xを持ってきます。これが素数かどうかがすばやく判定できるといいのですよね。それには、片っ端からxより小さい整数をもってきて、xで割ってあげればいい、と思うかもしれませんが、それは計算に非常に時間がかかります。少なくともルートxより小さい奇数すべてで割ってみなくてはいけません。つまり、xが素数かどうかを判定するのにかかる典型的な時間が、数xのルートに比例するのです。

ここで計算量という考え方を導入しましょう。まず、同じ計算の仕方でも、その良し悪しによって計算速度が変わります。どうやって計算をさせるのか、ということを計算のアルゴリズムといいます。xがメモリにしてLビットで表現される量であるとします。メモリがLビットあれば、0000.....000から1111.....111まで2^L個の異なる数を表現すき、これによって、2^L個の自然数を表現できます。このメモリに記憶した数をもとに、計算をおこなったとします。このとき、

「計算アルゴリズムが効率的である」とは、演算の回数がLの多項式に比例すること
「計算アルゴリズムが効率的でない」とは、演算の回数がLの指数関数となること

と定義します。この定義に従って、先ほどの素数判定のアルゴリズムを見直してみましょう。もしxの素数かどうかの判定に「もしもxより小さいすべての整数でxを割ってみる」というアルゴリズムを採用すると、それには、

回程度のの演算が必要となります。これは典型的な「非効率」なアルゴリズムです。

このような計算がいかに効率が悪いかは、すぐにわかります。例えば、L=100つまり100ビットで扱える数が素数かどうかを調べるのに、この方法では、2の50乗もの計算を行わないといけません。2の50乗といったら、大変な計算回数です。Lがさらに増えていくと、計算がそれこそ「ねずみ算的に」増えていくので、「非効率」というわけです。「非効率」ということばを、「手におえない計算」と言い直してもいいくらいです。

ある数xを与えたときに、それが素数かどうかを調べるのは、Rabin-Solovay-Strassenのアルゴリズムが便利です。これは与えられた数xが素数かどうかを、効率的に判定してくれます。ちょっと不思議なアルゴリズムなので、簡単に紹介しましょう。

まず、次のような整数aに対する判定関数F(a)を用意します。ここでaはxより小さい数を入れることにします。

(1)整数a-1の素因数分解を行う。そのときの2の個数をkとし、

とする。

(2)

もしくは、0からkの間のすべての整数iで

が成り立つかどうかを判定し、もし成り立つのならF(a)=1とし、それ以外だったら、F(a)=0とする。

以上の判定関数は効率的に計算できます。(任意課題、これを確かめよ。)ます。さて、この判定関数F(a) (0<a<x)に関して、以下のような定理が数学的に証明されています。(証明はしません。残念ながらまだフォローできていないのです。)

xが素数なら、すべてのaでF(a)=1である。
xが合成数なら、3/4の確率でF(a)=0である。

これをつかえば、例えば100個の異なる整数をでたらめにえらんで、それぞれをこの関数に代入したとする。もしもF(a)=0となるaがあれば、xは合成数確定である。もしも100個すべてのaでF(a)=1となったときは、「xが素数である」か「xは合成数なのだが、たまたま偶然100個ともF(a)=1となってしまった」かのどちらかである。しかし後者が実現する確率は、(1/4)^100となって果てしなく小さい。よって、実質的に、xを素数と判定してもいいことになります。(間違うリスクはあるのだが、無視できるほど小さい。)このアルゴリズムならば、計算回数はLにほぼ比例することになります。

というわけで、ランダムに整数をとりだして、それが素数かどうかを以上の方法で判定していけば、何回かやるうちに素数がみつかります。こうして、大きな素数p, qを効率的にみつけることができました。

つぎに(B)、すなわち

を満たすような整数e, dを見つけること。

のほうですが、こちらはユークリッドの互除法を利用して効率的に計算できることが知られています。具体的な方法についてはここに述べませんが、こちらに簡単な解説があるようです。

古典コンピュータによってRSA暗号がほぼ解読不可能であること

RSA暗号が、普通のコンピュータでは解読が絶望的であることを最後に示しましょう。この暗号の解読をもくろむ敵がいたとします。敵は公開鍵(e,n)を簡単に手に入れることができますが、暗号解読のためには、さらに秘密鍵(d,n)を知る必要があります。もし、かりに公開鍵の一つであるnを因数分解n=pqと因数分解できたらどうでしょうか。すると敵は、p, q, eまでの知識を得ることになります。すると、既知のp, q, eより

を解いて、秘密鍵dを取り出すことができます。前節の最後で解説したように、この計算は効率的にできます。そうすると、もうRSA暗号はまる裸ですよね。

ということで、RSA暗号解読のためには、整数nを二つの素数p, qに因数分解できれば、よいことになりますが、実は因数分解を行うことが絶望的に難しいのです。もう、うすうす感づいたかもしれませんが、現在「整数の因数分解を効率的に行うアルゴリズム」は知られていないのです!(注意:面白いことに「因数分解を効率的に行うアルゴリズムが存在しないこと」の証明は、知られていません。ですから、もしかしたら古典コンピュータで整数の因数分解を効率的に行うことができるかもしれません。そういうアルゴリズムができてしまったら、きっと高値で売れるでしょうね。でもそのかわり、インターネット上の商取引は壊滅的ダメージをうけるでしょう。想像するだけでも恐ろしい。)

因数分解を行うアルゴリズムのうち、もっとも原始的なものは、整数nをそれより小さいすべての数について、割ってみることです。これは、大体ルートx程度の演算が必要です。よって、Lビットで表される整数xについては、さっきと同じく

回程度の演算が必要です。よって、これはあきらかに非効率なアルゴリズムですね。最新の因数分解のアルゴリズムでは、演算回数を

にまで減らすことができます。さきほどの指数関数型よりは早く計算ができますが、しかし相変わらずLの増大と共に急激に演算回数が増えてしまいます。

文献[1]によれば、2000桁の整数の因数分解の難しさを、ある計算科学者は「世界中に存在するすべてのコンピュータをもちいても、その数を因数分解できないというばかりではない。実際はもっと劇的である。この宇宙に存在する各分子がすべて(古典的)コンピュータで、宇宙の全寿命にわたって全速力で計算をつづけてきたと想像してみよう。たとえそうだとしても、その数を因数分解するには不十分なのです。」と表現したそうです。恐ろしいですね。

まとめ

最後にまとめてみましょう。

(1)現在普及しているインターネット上の暗号は因数分解の困難さに依存している。

(2)古典コンピュータでは、現在のところ因数分解を効率的におこなうことができない。

それに加えて、

(3)量子コンピュータでは、因数分解を効率に行えることを1996年にShorが証明した。

ということも述べました。このことのインパクトが、ご理解いただけたでしょうか?つまり「もし量子コンピュータができてしまうと、今現在あるインターネット上の暗号が破られてしまうぞ」ということを意味しているのです。Shorの数学的な証明は、金融機関の注目を浴びるという、まことに珍しい反応が起こったのです。

この講義は、Shorの定理を証明することを目標とします。次回は、量子コンピュータの基本的な事柄について、突っ込んだ講義をしたいと思います。

参考文献

[1] 量子コンピューティング --- 量子コンピュータの実現へ向けて
C. P. ウィリアムズ/S. H. クリアウォータ著 西野哲朗、荒井隆、渡邉昇訳、シュプリンガーフェアラーク東京
詳細な解説があります。本講義の内容をさらに深めたい人向け

[2] 量子コンピュータの基礎、細谷暁夫著、サイエンス社
大変わかりやすく手軽な入門書です。おすすめ。

[3] 量子コンピュータ入門、西野哲朗著、東京電機大学出版局
情報科学よりの解説があります。計算論に詳しい。

参考になるサイト

「量子コンピュータ」や「RSA暗号」をキーワードに検索をすると、たくさんのページがでてきます。役に立ちそうなページを以下に紹介します。

[1] インタラクティブ・サイエンス・コラム 量子コンピュータに関するやさしい解説があります。

[2] 楽天市場の中のSSL暗号解説 RSA暗号が実際に使われている様子を知ることができます。

[3] 川畑史郎のホームページ  川畑氏は量子コンピュータを専門にする研究者です。量子コンピュータ関係の研究機関・研究者のリンク集が強力です。

[4] インターネットの新サービスに対応したセキュリティハンドブックの提唱 RSA暗号の詳細がわかります。

合同式についての補足

本文中で合同式の記号≡を使いましたが、これに初めて出会う人のために若干補足します。先ず定義は、

とは、(aをnで割った余り)=(bをnで割った余り)を意味します。例として


があげられます。これは簡単ですね。要は29を7で割った余りも、50を7で割った余りも1だぞ、ということです。この式は、あたかも等式のように扱えるので、整数の証明では重宝します。合同式の性質として、基本性質



が成り立ちます。特に最後はなかなか便利で、例えば上の例から

が言えます。意味的にもオッケーなことを確認してください。合同式から、

を利用すると普通の数式にいけます。これを利用すると以下の合同式の性質が導けます。

このようにあたかも等式のごとき性質をうまく使って、本文中の証明が行われています。

(任意課題)以上の性質を証明してください。