 | a-bがmで割り切れるとき、a≡b (mod m)と書きます。
この式は等式と似た性質があります。
ちなみにフェルマーの小定理は
pを素数、aをpで割り切れない整数とするときa^(p-1)≡1 (mod p)と書けます。
267≡8 (mod 37)だから
267^311≡8^311 (mod 37)
フェルマーの小定理から、8^36≡1 (mod 37)だから
8^311≡8^(36*8+23)≡8^23
≡(2^3)^23≡2^69≡2^(36+33)≡2^33 (mod 37)
8*2^33≡2^3*2^33≡2^36≡1 (mod 37)だから
8x≡1 (mod 37)の解xがx≡2^33となる。
8x≡1≡1+111≡112≡8*14 (mod 37)だからx≡14 (mod 37)
よって2^33≡14 (mod 37)となるから
結局267^311≡14 (mod 37)となることがわかる。
|