← 定理辞典📖 定理辞典

合同式・余りの周期

合同式(余りによる分類)

22 つの整数を mm でわった余りが等しいとき「mm を法として合同」(a≡b(modm)a\equiv b\pmod m)。これは a−ba-b が mm の倍数なのと同じで、余りは法 mm ごとにくり返す。

主張

整数 a,ba,b を 22 以上の整数 mm でわった余りが等しいとき、aa と bb は「mm を法として合同」といい、a≡b(modm)a\equiv b\pmod m と書く。これは「a−ba-b が mm の倍数」(m∣(a−b)m\mid(a-b))であることとちょうど同じ。整数を余りで仲間分けすると、どの数も mm 進むごとに同じ余りに戻る(余りの周期 mm)。たとえば 33 を法とすると、0,3,6,90,3,6,9 は余り 00 で合同、1,4,7,101,4,7,10 は余り 11 で合同、というふうに 33 つの仲間にきれいに分かれる。

a≡b(modm)  ⟺  m∣(a−b)a\equiv b \pmod{m}\iff m\mid(a-b)
01234567891011
00〜1111 を 33 でわった余りで色分け。同じ色どうしが「33 を法として合同」で、33 つおきにくり返す。

成り立つ条件

mm は 22 以上の整数(法)。a,ba,b は整数で、「余り」は 00 以上 mm 未満にとる。同じ法 mm のもとで考えること(法が違う合同式どうしはそのままでは混ぜられない)。

証明(なぜ成り立つ?)

「余りが等しい」と「差が mm の倍数」が同じことを、わり算の余りの定義から両向きに確かめる。

  1. 1

    aa を mm でわった商を q1q_1・余りを r1r_1、bb を mm でわった商を q2q_2・余りを r2r_2 とする(0≤r1,r2<m0\le r_1,r_2<m)。

    a=mq1+r1,b=mq2+r2a=mq_1+r_1,\qquad b=mq_2+r_2
  2. 2

    差をとると、余りが等しい(r1=r2r_1=r_2)なら r1−r2=0r_1-r_2=0 となり、a−b=m(q1−q2)a-b=m(q_1-q_2)。これは mm の倍数だ。

    a−b=m(q1−q2)+(r1−r2)a-b=m(q_1-q_2)+(r_1-r_2)
  3. 3

    逆に a−ba-b が mm の倍数なら、r1−r2r_1-r_2 も mm の倍数。ところが 0≤r1,r2<m0\le r_1,r_2<m なので ∣r1−r2∣<m|r_1-r_2|<m。mm の倍数で絶対値が mm 未満なのは 00 だけだから r1−r2=0r_1-r_2=0、つまり余りが等しい。こうして「余りが等しい   ⟺  \iff 差が mm の倍数」が示せた。

  4. 4

    さらに nn と n+mn+m は差がちょうど mm だからいつも合同。だからどの数も mm 進むごとに同じ余りに戻り、整数は法 mm で mm 個の仲間(余り 0,1,…,m−10,1,\dots,m-1)に分かれる。これが「余りの周期」だね。

逆

合同は足し算・引き算・かけ算で保たれる。a≡ba\equiv b、c≡d(modm)c\equiv d\pmod m ならば a±c≡b±da\pm c\equiv b\pm d、ac≡bd(modm)ac\equiv bd\pmod m。だから大きな数の計算も「余りだけ」で進められる(たとえば 77 の累乗の一の位は、1010 を法とした余りの周期で決まる)。ただし割り算は、法と共通因数があるとそのままでは使えないので注意が要る。

補足・つまずきポイント

合同式は「等号 == のなかま」として足し算・かけ算ができるのが強み。時計が 1212 でひと回りして戻るのも、1212 を法とした合同の世界だね。一次不定方程式 ax+by=cax+by=c は ax≡c(modb)ax\equiv c\pmod b と同じ見方ができて、整数の問題を「余りの世界」に持ち込む入口にもなる。

関連する定理

見て確かめる

言葉で読んだら、動くアニメと自分の手で確かめてみよう。

使いどころ

この定理が、実際の問題でどう効くのかを見てみよう。