剰余数の性質
数理論 へ戻る
大学生のための数学 へ戻る
2014.10.20____
ここに登場するアルファベットは、 特に指定のない限り、 正の整数を表すものとします。
（00） ｎ で割ると ｍ 余る数（Ｂ）に ｎ を加えた数を ｎ で割った余りは ｍ である。
解 説 ：
乗余数の性質の基本です。
MOD ( Ｂ , n ) ＝ ｍ MOD ( Ｂ , n ) ＝ MOD ( Ｂ＋ｎ , n ) ＝ ｍ
Ｂ ≡ Ｂ＋ｎ ≡ ｍ ( mod ｎ )
（01） ｎ で割ると ｍ 余る数（Ｂ）に ｋ を加えた数を ｎ で割った余りは、 ｍ に ｋ を加えた数を ｎ で割った余りに等しい。
解 説 ：
乗余数の性質の基本です。
MOD ( Ｂ , n ) ＝ ｍ MOD ( Ｂ＋ｋ , n ) ＝ MOD ( MOD ( Ｂ , n )＋ｋ , n ) ＝ MOD ( ｍ＋ｋ , n )
Ｂ ≡ ｍ ( mod ｎ ) Ｂ＋ｋ ≡ ｍ＋ｋ ( mod ｎ )
（02） ｎ で割ると ｍ 余る数（Ｂ）に Ａ をかけた数を ｎ で割った余りは、 ｍ に Ａ をかけた数を ｎ で割った余りに等しい。
解 説 ：
乗余数の性質の基本です。
MOD ( Ｂ , n ) ＝ ｍ MOD ( Ａ×Ｂ , n ) ＝ MOD ( Ａ × MOD ( Ｂ , n ) , n ) ＝ MOD ( Ａ×ｍ, n )
Ｂ ≡ ｍ ( mod ｎ ) Ａ×Ｂ ≡ Ａ×ｍ ( mod ｎ )
（１） ｎ で割ると １ 余る数（Ｂ）は、 何乗しても ｎ で割ると １ 余る。
解 説 ：
Ｋ を任意の自然数とする。
MOD ( Ｂ , n ) ＝ １ MOD ( Ｂ , n ) ＝ MOD ( ＢＫ , n ) ＝ １
Ｂ ≡ １ ( mod ｎ ) Ｂ ≡ ＢＫ ≡ １ ( mod ｎ )
ｎ で割ると１余る数は、 ０ 以上の整数 ｍ を使うと、 
で表されます。
５乗以上の展開については、 次の２項定理を利用すると、 簡単です。
すべて最後の項以外は ｎ で割り切れますので、 何乗しても余りは １ になることが解かります。
（２） ｎ で割ると Ａ 余る数（Ｂ）を Ｋ乗した数を ｎ で割った余りは Ａ をＫ乗した数を ｎ で割った余りに等しい。
解 説 ：
MOD ( Ｂ , n ) ＝ Ａ MOD ( ＢＫ , n ) ＝ MOD ( ＡＫ , n )
Ｂ ≡ Ａ ( mod ｎ ) ＢＫ ≡ ＡＫ ( mod ｎ )
Ｑ と Ｗ を ０ 以上の整数とします。 ｎ で割ると Ａ 余る数を ｎＱ＋Ａ と ｎＷ＋Ａ とします。 ２項定理を使って Ｋ乗 した数を展開しますと、 〇×ｎ の形になっていない項はどちらも 
だけです。 これは（１）を拡張して一般化したものです。
（３） 素数 Ｓ で割ると Ａ 余り、 素数 Ｔ で割ると Ａ 余る数（Ｂ）は、 ＳＴ で割ると Ａ 余る。
解 説：
MOD ( Ｂ , Ｓ ) ＝ Ａ MOD ( Ｂ , Ｔ ) ＝ Ａ MOD ( Ｂ , ＳＴ ) ＝ Ａ
Ｂ ≡ Ａ ( mod Ｓ ) Ｂ ≡ Ａ ( mod Ｔ ) Ｂ ≡ Ａ ( mod ＳＴ )
０ 以上の整数 ｍ を使うと、 素数 Ｓ で割ると Ａ 余り、 素数 Ｔ で割ると Ａ 余る数は、 ｍＳＴ＋Ａ で表されます。 したがって、 この数を ＳＴ で割ると Ａ 余ります。
（４） ｎ で割ると Ａ 余る数（Ｃ）と ｎ で割ると Ｂ 余る数（Ｄ）がある。 この２つの数を加えた数を ｎ で割った余りは、 Ａ＋Ｂ を ｎ で割った余りに等しい。
解 説 ：
MOD ( Ｃ , ｎ ) ＝ Ａ MOD ( Ｄ , ｎ ) ＝ Ｂ MOD ( Ｃ＋Ｄ , ｎ ) ＝ MOD ( Ａ＋Ｂ , ｎ )
Ｃ ≡ Ａ ( mod ｎ ) Ｄ ≡ Ｂ ( mod ｎ ) Ｃ＋Ｄ ≡ Ａ＋Ｂ ( mod ｎ )
Ｑ と Ｗ を ０ 以上の整数とします。 ｎ で割ると Ａ 余る数を ｎＱ＋Ａ とし、 ｎ で割ると Ｂ 余る数を ｎＷ＋Ｂ とします。 ２つの数を加えると ｎ（Ｑ＋Ｗ）＋（Ａ＋Ｂ） になります。 この数の第１項は ｎ で割り切れますので、 この数を ｎ で割った余りは、 第２項の Ａ＋Ｂ を ｎ で割った余りになります。
（５） ｎ で割ると Ａ 余る数（Ｃ）と、 ｎ で割ると Ｂ 余る数（Ｄ）がある。 この２つの数をかけた数を ｎ で割った余りは、 ＡＢ を ｎ で割った余りに等しい。
解 説：
MOD ( Ｃ , ｎ ) ＝ Ａ MOD ( Ｄ , ｎ ) ＝ Ｂ MOD ( ＣＤ , ｎ ) ＝ MOD ( ＡＢ , ｎ )
Ｃ ≡ Ａ ( mod ｎ ) Ｄ ≡ Ｂ ( mod ｎ ) ＣＤ ≡ ＡＢ ( mod ｎ )
Ｑ と Ｗ を ０ 以上の整数とします。 ｎ で割ると Ａ 余る数を ｎＱ＋Ａ とし、 ｎ で割ると Ｂ 余る数を ｎＷ＋Ｂ とします。 ２つの数をかけると 
になります。 この数の第１項と第２項は ｎ で割り切れますので、 この数を ｎ で割った余りは、 第３項の ＡＢ を ｎ で割った余りになります。
（６） 複数の ｎ で割り切れない自然数の積を ｎ で割った余りは、 それぞれの数を ｎ で割った余りの積を ｎ で割った余りに等しい。
解 説 ：
これは（５）を拡張して一般化したものです。
（７） 素数 Ｓ と Ｓ の倍数でない 数 Ｈ があるとき、 ＨＳ−１ を Ｓ で割った余りは １ である。
（８） 数 Ｈ が 素数 Ｓ とも 素数 Ｔ とも互いに素のとき、 Ｈ(Ｓ−１)(Ｔ−１) を ＳＴ で割った余りは １ である。
解 説 ：
これは、 Ｎ ＝ ＳＴ のときのオイラーの定理です。 オイラーの定理とは次のようなものです。
「 ある正の整数 
よりも小さくて、 かつ、 と互いに素の正の整数の数（かず）を 
で表すとき、 と互いに素の任意の正の整数 
について、 
は必ず で割り切れる。」
※ 数理論 ＞ オイラーの定理
（９） ｎ ＝ ＳＴ （ Ｓ と Ｔ は 素数 ） のとき、 ｎ よりも小さな数 Ｈ の Ｋ乗 （ ただし、 Ｋ は （Ｓ−１） と （Ｔ−１） の最小公倍数の倍数 ） を ｎ で割った余りは １ である。
解 説 ：
この性質は、 ＲＳＡ暗号に用いられています。
（10） ｎ と ｎ よりも大きくない数 ｍ があるとき、 ｎ の階乗に ｍ を加えた数を ｍ で割った余りは ０ である。
解 説 ：
MOD ( ｎ！＋ｍ , ｍ ) ＝ ０
ｎ！＋ｍ ≡ ０ ( mod ｍ )
ｎ の階乗は ｍ の倍数です。
（11） ａＰ ≡ ａＲ ( mod ｂ ) で、ａ と ｂ が互いに素ならば、 Ｐ ≡ Ｒ ( mod ｂ ) である。