？？？？

\begin{aligned} r \ _n\mathrm{C}_r &= r\ \frac{n!}{(n-r)!r!} \\ &=n\ \frac{(n-1)!}{(n-r)!(r-1)!} \\ &= n \ _{n-1}\mathrm{C}_{r-1} \\ \end{aligned}

$n \in \mathbb{P},r \in [1, n-1]$ のとき

\begin{aligned} r \ _n\mathrm{C}_r &= n \ _{n-1}\mathrm{C}_{r-1} &= \end{aligned}

RSA

使う定理

modの証明で $a\equiv b \pmod n$ のときは以下を前提とする．

\begin{align*} q_a,q_b,r \in \mathbb{Z}\\ r<n\\ a = q_an + r \\ b = q_bn + r \\ \end{align*}

\begin{align*} a-b&=(q_a-q_b)n　\\ \therefore a-b &\equiv 0 \end{align*}

$c = q_cn + r_c$ とする．

\begin{align*} a + c &= (q_a+q_c)n + r + r_c \\ b + c &= (q_b+q_c)n + r + r_c \\ \therefore a+c &\equiv b+c \end{align*}

$r+r_c>0$ の場合でも， $r+r_c = q_rn+r_r$ として

\begin{align*} a + c &= (q_a+q_c+q_r)n + r_r \\ b + c &= (q_b+q_c+q_r)n + r_r \\ \end{align*}

1.1の3行目 $a-b=(q_a-q_b)n$ の両辺に $c$ をかけて

\begin{align*} ac &= q_acn + rc \\ bc &= q_bcn + rc \\ \therefore a+c &\equiv b+c \end{align*}

$rc \geq n でも補足1と同様$

$rc>0$ の場合でも，$rc = q_rn+r_r,r_r<n $として

\begin{align*} ac &= (q_ac + q_r)n + r_r \\ bc &= (q_bc +q_r)n + r_r \\ \end{align*}