公式など
- あまり
- a ÷ b のあまりを r としたとき、0 ≤ r < b なことに注意
- 整序関係
- ax | bx ⟺ a | b (x ≠ 0 のとき)
- 合同式
- $ab \equiv ac \pmod{an}$ ならば $b \equiv c \pmod n$
- $b \equiv c \pmod{an}$ ならば $\lfloor b/a \rfloor \equiv \lfloor c/a \rfloor \pmod{n}$
- 高度合成数
- gcd と lcm はかけ算に関して分配的
- a gcd(b, c) = gcd(ab, ac)
- a lcm(b, c) = lcm(ab, ac)
- 特に (ℕ, gcd, ×) は半環を成す
- min, plus 代数と同様。素因数分解したときの指数で min plus したものだと思えば良い。
- ルジャンドル関数
- $N!$ の素因数分解における $p$ の指数
- 横に切って考える（ルベーグ積分的な）
問題を解くテクニック
- mod a -b では、[a] = [b] だと考えて、[a] に [b] を代入するとわかりやすい
- 例: mod (2^n -1) は 2^n を 1にする。
- 最大公約数で割って、互いに素な場合を考える（互いに素なほうが簡単）
- 周期がある場合は LCM を考える
メモ