初等整数論 | Notion

1. あまり

$a$ を $b$ で割ったときの余りを $r$ としたとき、$0 \leq r < b$ なことに注意
- 例
  - Q5. A を割ると B あまる数 | アルゴ式
  - ARC 176 B - Simple Math 4
余りの冪等性
- $(x \bmod a) \bmod a = x \bmod a$
余りの順序
- $a < b$ のとき、$(x \bmod a) \bmod b = x \bmod a$
  - 例えば $\bmod 5$ をした後に $\bmod 12$ をしても変わらない
- 応用例
  - エクサウィザーズ2019 D - Modulo Operations (解説は挿入DP を参照)
商とあまりの相互変換
- $a = bq + r$ という式で、あまり $r$ から商 $q$ を求めることができるし、商 $q$ からあまり $r$ を求めることもできる。
  - $q = (a-r)/b$
  - $r = a - bq$
- 商もあまりも割り算の関連だから、親和性が高い
- 商とあまりは以下のように表現されがち
  - 商: $q = \lfloor a/b \rfloor$
  - あまり: $r = a \bmod b$
- 応用例
  - あまりから商
    - ABC452 E - You WILL Like Sigma Problem
    - ABC443 G - Another Mod of Linear Problem
  - 商からあまり:
    - ABC448 E - Simple Division

$Ma \equiv Mb \pmod{MN}$ ならば $a \equiv b \pmod N$
- $M\neq 0$ のとき
- 逆も成り立つ
- $ax \mid bx \iff a \mid b$ ($x \neq 0$ のとき) と関連あり
$a \equiv b \pmod{MN}$ ならば $\lfloor a/M \rfloor \equiv \lfloor b/M \rfloor \pmod{N}$
- $M \neq 0$ のとき
- 参考: ARC167 B, ARC167 の A問題, B問題を画像でまとめてみました - ぱるまの日記
- $\lfloor a/M \rfloor$ を ${}\bmod N$ で求めたい場合は $a$ を ${}\bmod MN$ で求めればよい
- tbw: 商の代わりにあまりにしたバージョン
$a \equiv b \pmod{MN}$ ならば $a \equiv b \pmod{N}$
- $MN$ の倍数なら $N$ の倍数ってこと

$ax \equiv 0 \pmod M$ の解
- $a$ と $M$ が互いに素の場合: $x \equiv 0 \pmod M$
- $a$ と $M$ が互いに素とは限らない場合: $x \equiv 0 \pmod {M/\gcd(a,M)}$
$ax \equiv b \pmod M$ の解

$G=\gcd(a,M)$ と置く。
- $b$ が $G$ の倍数でない場合は解を持たない。
- $b$ が $G$ の倍数の場合
  
  $a'=a/G,\ b' = b/G,\ M' = M/G$ と置いたとき、
  
  $a'x \equiv b' \pmod{M'}$ の解
  
  つまり $x\equiv \operatorname{inv\_mod}(a', M')\cdot b'\pmod{M'}$ が答え
- 詳しい解法
$x \equiv a \pmod M,\ x \equiv b \pmod N$ の解

ACL の CRT を使えばいい（互いに素でない場合も対応してる）
- $M$ と $N$ が互いに素な場合: 解が $\operatorname{mod}{MN}$ で求まる
- $M$ と $N$ が互いに素とは限らない場合: 解が $\operatorname{mod}{\operatorname{lcm}(M,N)}$ で求まる
参考: 代数学を使った整数論

出題例