10 (Favした一覧ページはユーザーページから) Tweet

このページは,競技プログラミングで使うことがある数学的性質・テクニックをまとめるページです。
初めての人から見て、自明ではなさそうなものをまとめたいと思います。 必須な知識ではない豆知識的な項目もあります。
特に明記されてなければ,整数を扱うものとします。

和なら剰余を先に行っても良い
(差も同様だが、負になる時は気をつける)

$a=km+i,b=lm+j$ とおくと,
$(a+b) \% m =(km+i+lm+j)\% m = (i+j)\%m= ((a\%m)+(b\%m))\%m $ となるので
$(a+b) \% m =((a\%m) +(b\%m))\%m $ が成り立ちます。

積なら剰余を先に行っても良い

$a=km+i,b=lm+j$ とおくと,
$(a*b) \% m =((km+i)*(lm+j))\% m = (klm^2+kmj+lmi+ij)\%m = ij \%m =((a\%m)*(b\%m))\%m $ となるので
$(a*b) \% m =((a\%m)*(b\%m))\%m $ が成り立ちます。

$a,b$ が正なら $a / b$ の切り上げは $(a+b-1) /b$
（切り捨てが発生する場合の記述）

$b=1$ の時は $(a+b-1)/b=a=a/b$ なので成立します。
$b \ge 2$ とします。
$a$ が $b$ の倍数の時は $a = k b$ なので $k \le a/b + (b-1) /b < k+1$ になります。
そうでない時、$a$ を $b$ で割ったあまりは $1$ ... $b-1$ のどれかになるので
$a$ は $kb+ 1$ ... $kb+(b-1)$ のどれかで表されることになります。
なので $a+b-1$ は
$(kb+1)+(b-1)=(k+1)b$
...
$(kb+(b-1))+(b-1)=(k+1)b+(b-2)$
のどれかで表されることになります。
これらを $b$ で割った時の範囲を考えると以下のようになります。
$(k+1) \le (a+b-1)/b < (k+2)$
整数型の除算では小数点以下が切り捨てられることを利用すると、
$(a+b-1) /b$ での計算値は、$a$ が $b$ で割り切れる時は $k$ ,割り切れない時は $k+1$ になります。
つまり $a / b$ の切り上げは $(a+b-1) /b$ として記述できることになります。

$n$と互いに素の数$a$,$b$の積$ab$も$n$と互いに素である。

$n$と$a$は互いに素なので、これらを共通して割り切る素数は存在しない。
$n$と$b$も互いに素なので、これらを共通して割り切る素数は存在しない。
もし$ab$と$n$が互いに素でなければ(背理法の仮定)、$ab$と$n$を共通して割り切る素数$p$が存在する。
$n$は$p$の倍数なので、仮定から$a$と$b$はどちらも$p$の倍数ではないが、そうすると$ab$が$p$の倍数であることと矛盾。
よって$ab$と$n$は互いに素。

互いに素の数$a$,$b$の 和$a+b$と積$ab$は互いに素である。

証明は互いに素な二数の和と積どうしも互いに素になることはどうやって証明... - Yahoo!知恵袋から拝借する。
もし、互いに素でなければ共通で割れる素数$k$が存在する。
よって、以下の２式が存在することになる。

• $ab = pk$ (pはある整数）- 式1
• $a+b = qk$ (qはある整数）

$a$と$b$は互いに素なので,式1の左辺の$a$,$b$のどちらかは約数$k$を持つことになる。（$k$は素数であることから）
ここで,$a$が約数$k$をもつとすると, $a=rk$ と表現できることになる。
$b=(a+b)-a= qk - rk = k(q-r) $
$b$は約数$k$を持ってしまうことになる。$a$と$b$は互いに素だったため、これは矛盾する。
また,$b$が約数$k$を持つとしても同様に説明できる。
よって 共通で割れる素数$k$は存在しないため、$a+b$と$ab$は互いに素であることが分かる。

$a$,$b$が互いに素のとき$gcd(a,kb)=gcd(a,k)$

$a$,$b$が互いに素の数のとき、共通で割れる素数はない。
つまり、$a,kb$が共通で割れる素数を考える場合、$a$と$k$との公約数になる。
つまり$gcd(a,kb)=gcd(a,k)$。

$ac \equiv bc \pmod n \rightarrow a \equiv b \pmod {\frac{n}{g}}$ ($g$は$c$と$n$の最大公約数)

証明は【数の構成】合同式で遊ぼう～掛けてもいいなら割ってもいい？ | 大人が学び直す数学を参照

ここで$c$と$n$の最大公約数(g)が1のとき、つまり$c$と$n$が互いに素のときは、法を変更せずに両辺共通の値で割れることを意味する。

$a^{\varphi (n)} \equiv 1 \pmod{n} $（オイラーの定理）

$\varphi (n)$はオイラーのトーシェント関数、$n$以下の$n$と互いに素の数
Wikipediaに証明が記載されているので引用と、少し補足する。オイラーの定理 :Wikipedia

$n$と$n$以下で互いに素の数すべての集合
$A=\{b_1,b_2,...,b_{\varphi(n)}\} $
をそれぞれ $n$と互いに素の数である$a$との積を取ると,
$B=\{ab_1,ab_2,...,ab_{\varphi(n)}\}$
法$n$上では、$A$と$B$の集合は一致する。
よって集合$A$のすべての要素の積を$P$とすると $P \equiv a^{\varphi (n)} P \pmod{n} $
つまり、$a^{\varphi (n)} \equiv 1 \pmod{n}$

集合$A$と$B$が一致する理由を示す。
集合$A$は$n$との互いに素のすべての数の集合だったため、集合$B$も$n$との互いに素の数すべての集合であればよい。
「$n$と互いに素の数$a$,$b$の積も互いに素である」ため集合$B$もすべて$n$と互いに素の数である。
また、集合の要素数が増えることはないので、集合の要素数が減ることはないことを示す。
つまり$B$の要素で重複しているものがないということを示す。

$x=b_i, y=b_j$ （どちらも$n$以下で$n$と互いに素の数に注意）とおく。
この時 $ax \equiv ay \pmod {n} $となる$y$が他に存在するか考える。（存在しなければ単射であり、$B$の要素に重複しているものがないことを指す）

逆元 $a^{-1}$を持つため, $a \cdot a^{-1} \equiv 1$ より
$a(x-y) \equiv 0 \pmod {n} $の両辺に$a$を割ると,
$ a^{-1} \cdot a \cdot (x-y) = (x-y) \equiv 0 \pmod {n} $

$x-y$が$n$の倍数の場合のときに合同であるが、
$x,y$はそれぞれ$n$未満の数であるため$x-y=0$以外に$n$の倍数になることはない。
よって$x=y$である。つまり$b_i$ただひとつしかないことが示せる。

$p$が素数で、$a$と$p$が互いに素なときに $\frac{n}{a} \%p = n*a^{p-2} \%p$である。

整数$a$の、法$p$に関する合同類環における乗法逆元$a^{-1}$を求める。
フェルマーの小定理より、$p$は素数で$a$と$p$が互いに素なとき、
$a^{p-1} \equiv 1 \pmod p$
$a$と$p$が互いに素なので両辺$a$で割り、左右を入れ替えると
$a^{-1} \equiv a^{p-2} \pmod p$
両辺に$n$をかけると、
$n/a \equiv na^{p-2} \pmod p$
となるので、$\frac{n}{a} \%p = n*a^{p-2} \%p$である。
この性質を使うと、組み合わせのコンビネーション$C$など,剰余を求める必要があるが割り算が発生する際などに利用できる.
（data9824さんのコメントから拝借いたしました。）
$p$が素数でない場合も、$a$と$p$が互いに素なら$a^{-1} \equiv a^{\phi(p) - 1} \pmod p$は成り立つ。

小ネタ・トリビア

整数値$N$を2乗したものを4で割った時のあまりは、$N$が偶数の場合は$0$,$N$が奇数の場合$1$

$N=2k$の時、$N^2=4k^2$
$N=2k+1$の時、$N^2=4k^2+4k+1=4(k^2+k)+1$であるため