合同式の解法と剰余定理の応用
逆元の計算
合同式\(ax \equiv b \pmod{m}\)を解くことは、\(ax + my = b\)と等価です。これを拡張ユークリッドの互除法で解けます。
特に、\(a\)と\(p\)が互いに素の場合、\(a\)の\(p\)を法とする逆元を求めることができます。方法は\(ax \equiv 1 \pmod{p}\)を解くことです。
中国剰余定理（CRT）
問題設定
\(m_1, m_2, \ldots, m_n\)が\(n\)個の互いに素な整数であり、\ ...
7月1日 16:35 投稿