(36.1) この節の初めのほうは数学の話である。 Z/mZ, Z/m, Zm などと書かれる環の演算について、 初めての人にもわかりやすい形で説明する。 くわしくは代数学の時間に習うであろう。
(36.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」と書くこともある。
(36.3) 「modulo」は 原語（ラテン語）に忠実に読めば「モドゥロー」だろうが、 普通は「モドゥロ」「モデュロ」「モジュロ」などと読む。
(36.4) たとえば 「3 ≡ 8 (mod 5)」、 「28 ≡ 3 (mod 5)」、 「-2 ≡ 8 (mod 5)」など。
(36.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)」 が成り立つ。
(36.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) が成り立つことは容易に確かめられる。
(36.7) 任意の整数 x に対し、 0 以上 m-1 以下の整数 y がただひとつ存在して x ≡ y (mod m) となる。
(36.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 の整数倍を加減する。）
(36.9) 練習： #define M 6 などとし、 mod M での乗法の表（九九の表のようなもの） を出力するプログラムを書いてみよ。
(36.10) このとき、§28 の練習問題の 3 番のように、 左と上に被乗数・乗数が出力されるようにできればよいが、 それがむずかしい場合、 1 から M-1 までの表にするとよい。 （0 は掛ければ 0 とわかっているので。）
(36.11) 1 から M-1 までの乗法の表で、 各行各列に 1 から M-1 までのすべての数が現れるのは、 M がどのような場合か？
(36.12) 除法を考えよう。 a ≡ bx (mod m) が成り立つような x が、a を b で割った商である。 modulo 6 で考えるとき、3 を 2 で割ることはできない。 いかなる数 x についても 2 × x は偶数であり、 それと奇数である 3 とが modulo 6 で等しくなることはあり得ないからである。 modulo 5 で考えるなら、3 を 2 で割った商は存在する。 2 × 4 = 8 ≡ 3 (mod 5) であるから 4 が答えである。 （9 と答えてもよいが、ここでも答えは 0 以上 m-1 以下の整数の中から選ぶことにしよう。）
(36.13) m が素数のときを考えよう。 素数らしく p と書くことにすると、 modulo p で考えるとき、 任意の数に対し、その数を 1 以上 p-1 以下の任意の整数で割ることができる。 すなわち、 任意の整数 a と 1 以上 p-1 以下の任意の整数 b に対し、 ある整数 x が存在して a ≡ bx (mod p) を満たす。
(36.14) 証明： a - bx = pq を満たす整数 x と q が存在することを示せばよい。 移項して bx + pq = a とすれば、 b と p は互いに素だから、代数学の時間に習った定理から x と q の存在がわかる。
(37.1) 適当な十進二桁の素数 p を一つ選び固定する。 任意の整数 a と 1 以上 p 未満の整数 b に対し modulo p で a を b で割った商を返す関数 int divmod(int a, int b) を書け。 すなわち、 積 bx が modulo p で a になるような整数 x を返す関数を書け。 x は 1 以上 p 未満に値をとるようにせよ。
(37.2) main() もつけて、 そのままコンパイルして動かすことのできるものを提出すること。 main() をどんなふうに書くかは各自の判断に任せる。
(37.3) 提出方法などは課題１に準ずる。 ただし件名は「kadai2」 （←全て半角文字、アルファベットは小文字、途中にスペースをいれない） とせよ。
(37.4) ヒント： 答えは 1 以上 p-1 以下の整数のうちに必ずあるわけだから、 順に調べてゆき、見つかったらそこでその値を return すればよい。 よって、return を置く位置は関数の最後ではない（かもしれない）。
(37.5) 素数 p は勝手に選んで、 レポート内に「私は素数 17 を選びました」 「modulo 17 で割り算をする関数を書きました」 のように書けばよい。 選んだ数が素数であることをプログラム内で確かめる必要はない。
(37.6) 答えが二つある場合があるかどうかは、各自考えること。 もしそういう場合があったとしても、そのうちの一つを返すように書けばよい。
(37.7) 商は存在すると仮定してプログラムを書いて構わない。 「もしも見つからなかった場合」のために if などを使う必要はない。
(37.8) 間違って 0 で割った場合のことは考えなくてよい。 （でも、呼び出したらどうなるか実験してみるのはよいことである。）
(37.9) ヒント：余りを求める演算子は % であった。 10 % 3 は 1 となる。
(37.10) このプリントで使っている「≡」の記号はテキストファイル内では使えない。 printf() で出力させる文章やレポートの中に使いたいなら、 「=」で代用することをすすめる。 （「≡」は確か機種依存文字だったので使わないほうがよいだろう。）