mod n -> mod p

设 $\mathbb{Z}$ 为整数集。

前提:

1. $c, m, e, n, p, q, r \in \mathbb{Z}$
2. $n = pqr$
3. $c \equiv m^e \pmod n$

推导:

• 由前提 3 及同余的定义可知： $n | (c - m^e)$
• 这意味着存在某个整数 $k$，使得： $c - m^e = k \cdot n$
• 将前提 2 代入上式： $c - m^e = k \cdot (pqr)$
• 重新组合等式右边： $c - m^e = (kqr) \cdot p$
• 令 $k' = kqr$。因为 $k, q, r \in \mathbb{Z}$，所以 $k' \in \mathbb{Z}$。 $c - m^e = k' \cdot p$
• 根据整除的定义，上式意味着： $p | (c - m^e)$
• 再次根据同余的定义，可得： $c \equiv m^e \pmod p$

结论: $c \equiv m^e \pmod n \implies c \equiv m^e \pmod p$