(32.1) この節は数学の話である。 Z/mZ, Z/m, Zm などと書かれる環の演算について、 初めての人にもわかりやすい形で説明する。 くわしくは代数学の時間に習うであろう。
(32.2) 2 以上の整数 m をひとつ選び固定する。 二つの整数 a と b に対し、a-b が m で割り切れるとき、 すなわち a-b = mq となる整数 q が存在するとき、 「a と b は m を法として等しい」 「a と b は modulo m で等しい」 などと言い、 「a ≡ b (mod m) 」「a ≡ b (m) 」 などと書く。 mod m で考えていることが明らかな場合は単に 「a ≡ b」とだけ書くことも多いし、 さらに省略して「a = b」と書くこともある。
(32.3) 「modulo」は 原語（ラテン語）に忠実に読めば「モドゥロー」だろうが、 普通は「モドゥロ」「モデュロ」「モジュロ」などと読む。
(32.4) たとえば 「3 ≡ 8 (mod 5)」、 「28 ≡ 3 (mod 5)」、 「-2 ≡ 8 (mod 5)」など。
(32.5) この関係は同値関係である。すなわち、 「a ≡ a (mod m)」、 「a ≡ b (mod m) ならば b ≡ a (mod m)」、 「a ≡ b (mod m) かつ b ≡ c (mod m) ならば a ≡ c (mod m)」 が成り立つ。
(32.6) a ≡ a' (mod m) かつ b ≡ b' (mod m) ならば a+b ≡ a'+b' (mod m), a-b ≡ a'-b' (mod m), ab ≡ a'b' (mod m) が成り立つことは容易に確かめられる。
(32.7) 任意の整数 x に対し、 0 以上 m-1 以下の整数 y がただひとつ存在して x ≡ y (mod m) となる。
(32.8) よって、0, 1, 2, ..., m-1 だけを数だと思い、 その間に加法、減法、乗法を定義することができる。 たとえば 「3 + 5 = 8 ≡ 2 (mod 6)」、 「3 - 5 = -2 ≡ 4 (mod 6)」、 「3 × 5 = 15 ≡ 3 (mod 6)」など。 （つまり、普通に計算し、 結果が「0 以上 m-1 以下」という範囲をはずれたら、 その範囲に収まるよう m の整数倍を加減する。）
(32.9) 除法を考えるため、逆数について考えよう。 ax ≡ 1 (mod m) が成り立つような x を a の modulo m での逆数と呼ぶ。 2 の modulo 6 での逆数は存在しない。 いかなる数 x についても 2 × x は偶数であり、 それと奇数である 1 とが modulo 6 で等しくなることはあり得ないからである。 2 の modulo 5 での逆数は存在する。 2 × 3 = 6 ≡ 1 (mod 5) であるから 3 が答えである。 （8 と答えてもよいが、ここでも答えは 0 以上 m-1 以下の整数の中から選ぶことにしよう。）
(32.10) m が素数のときを考えよう。 素数らしく p と書くことにすると、 1 以上 p-1 以下の任意の整数について、 modulo p での逆数が存在する。 すなわち、 1 以上 p-1 以下の任意の整数 a に対し、 ある整数 x が存在して ax ≡ 1 (mod p) を満たす。 この x は 1 以上 p-1 以下の範囲にとれる。
(32.11) 証明： ax - 1 = pq を満たす整数 x と q が存在することを示せばよい。 移項して ax + p(-q) = 1 とすれば、 a と p は互いに素だから、代数学の時間に習った定理から x と q の存在がわかる。 見つかった x が p で割り切れることはありえないので、 x を 0 以上 p-1 以下の範囲にとり直せば、それは 0 ではありえない。
(33.1) 適当な十進二桁の素数 p を一つ選び固定する。 1 以上 p 未満の整数 x に対し modulo p での逆数を返す関数 int inv(int x) を書け。 すなわち、 積 xy が modulo p で 1 になるような整数 y を返す関数を書け。 y は 1 以上 p 未満に値をとるようにせよ。
(33.2) main() もつけて、 そのままコンパイルして動かすことのできるものを提出すること。 main() をどんなふうに書くかは各自の判断に任せる。
(33.3) 提出方法などは課題１に準ずる。 ただし件名は「kadai2」 （←全て半角文字、アルファベットは小文字、途中にスペースをいれない） とせよ。 締め切りは 2007 年 02 月 02 日（金）13 時 00 分。
(33.4) ヒント： 答えは 1 以上 p-1 以下の整数のうちに必ずあるわけだから、 順に調べてゆき、見つかったらそこでその値を return すればよい。 よって、return を置く位置は関数の最後ではない（かもしれない）。
(33.5) 素数 p は勝手に選んで、 レポート内に「私は素数 17 を選びました」 「modulo 17 での逆数を返す関数を書きました」 のように書けばよい。 選んだ数が素数であることをプログラム内で確かめる必要はない。
(33.6) 答えが二つある場合があるかどうかは、各自考えること。 もしそういう場合があったとしても、そのうちの一つを返すように書けばよい。
(33.7) 「p が素数なら 1 以上 p-1 未満の整数の modulo p での逆数は必ず存在する」 という命題は正しいものと仮定してプログラムを書いて構わない。 「もしも見つからなかった場合」のために if などを使う必要はない。
(33.8) 間違って inv(0) などとして呼び出された場合のことは考えなくてよい。 （でも、呼び出したらどうなるか実験してみるのはよいことである。）
(33.9) ヒント：余りを求める演算子は % である。 10 % 3 は 1 となる。
(33.10) このプリントで使っている「≡」の記号はテキストファイル内では使えない。 printf() で出力させる文章やレポートの中に使いたいなら、 「=」で代用することをすすめる。 （「≡」は確か機種依存文字だったので使わないほうがよいだろう。）
(34.1) 今学期の初めには、(1.4) に書いたように、 この授業で配布したアカウントを来年度末まで使う予定でした。 しかし、 総合メディア基盤センターのコンピュータのシステムが新しくなるのに伴い、 来年度への継続はできなくなったそうです。 また、今学期末には更新作業のためセンター実習室は使えなくなります。 よって、アカウントや実習室が使えるのは授業期間（補講期間を含む）が終わるまで、 と思っておいてください。
(34.2) ただし、いつアカウントが廃止されるかはわかりませんので、 今学期終了後も、しばらくはパスワードはきちんと管理しておいてください。 すなわち、 「授業期間が終わったからパスワードを書いた紙はもういらないや」 と言って人目につくところに捨てたりすることはしないでください。
(34.3) 来学期の「計算数学１」では新たにアカウントを配布する予定です。
(34.4) 自分のホームに置いてあるファイルをとっておきたい人は、 授業期間中に、各自でなんとかしてください。 家のパソコンなどにメールアカウントを持っている人は、 メールに添付して送ってしまうのが最も簡単で安全です。 来学期にまた使いたいなら、新しいアカウントをもらったあと、 そのメールを送り返せばよいでしょう。