$p$ を素数, $a$, $b$ を整数とし, $1\leq a\leq p-1$ とする. このとき, $1$ 次合同式 $$ ax \equiv b \pmod{p} $$ の解は $$ x\equiv (-1)^{a-1}\frac{1}{p}\binom{p}{a}b\pmod{p} $$ によって与えられることを証明せよ.
解答例 1
まず, $\displaystyle\binom{p}{a}\equiv 0\pmod{p}$ より, $\displaystyle\frac{1}{p}\binom{p}{a}$ は整数である. よって, $\displaystyle (-1)^{a-1}\frac{1}{p}\binom{p}{a}b$ も整数である.
$\displaystyle\binom{p-1}{a-1}\equiv (-1)^{a-1}\pmod{p}$ が成り立つことから, \begin{align*} a(-1)^{a-1}\frac{1}{p}\binom{p}{a}b &= (-1)^{a-1}\binom{p-1}{a-1}b \\ &\equiv (-1)^{a-1}(-1)^{a-1}b \\ &= b\pmod{p}. \end{align*}
最終更新日：2011年11月02日