Jul 292012
 

\(m\in\Bbb N^+,a\in\Bbb Z,\) 并且 \(( a, m ) = 1\), 则一次同余方程
\[ax\equiv b\pmod m\]
有唯一解 \(\dfrac ba\).

\(\dfrac ba\) 只是一个形式分数, 并不是我们需要的真正答数. 那么, 如何通过这个分数找出真正的解呢?

我没有看到什么书来系统论述这个问题. 单墫在他的大部头著作”数学竞赛研究教程”介绍中国剩余定理的时候, 在一个例题的解答里, 简略的提到了下面的变换 I 与 III. 人民教育出版社的新版普通高中课程标准实验教科书中, 有一本选修数学教材”初等数论初步”, 也谈到了这种办法, 并冠名为形式分数法, 更进一步指出这个办法是基于同余式的恒等变形,并在配套的教师用书给出了证明.

具体来说, 从 \(\dfrac ba\) 这个分数出发, 找出这个真正的解, 可以采取如下三个变换:
I      分子或分母可以加上 \(m\) 的整数倍. 换句话说, 分母或者分子可以换成对模 \(m\) 同余的数;
II     可用用与 \(m\) 互质的数同时乘以分母和分子;
III    可以约分.

在实际应用中, I 和 III 是必须要的, 而且足以把解找出来, 于是下面的第二件事情是成立的:

  1.  手术的合法性;
  2. 一次同余方程的解必定可以通过这三个变换得出.

至于 \(1\) 也比较显然, 就此打住.

\(\dfrac ba\) 是一个形式分数, 实际是一个整数. 把握这一点比较要紧. 下面是一个问题:

\(p\) is a odd prime, then

\[ 2^p-1\equiv (-1)^{\frac{p-1}2}{{p-1}\choose{\frac{p-1}2}}\pmod{p^2}. \]

proof.  Let \(n=\frac{p-1}2\), it is easy to see that

\[ (-1)^n\binom{p-1}n=\prod_{k=1}^n\frac{k-p}{k}\equiv\prod_{k=1}^n(1-\frac pk)\equiv1-p\sum_{k=1}^n\frac1k\pmod{p^2},\]

Remembering  that \(\sum\limits_{k=1}^{p-1}\dfrac1k\equiv0\pmod{p^2}\), we get that

\[\begin{split}2^p-1&=1+\sum_{k=1}^{p-1}\binom pk\equiv1+p\sum_{k=1}^{p-1}\frac{(-1)^{k-1}}k\\
&\equiv1+p\sum_{k\,odd}\frac1k-p\sum_{k\,even}\frac1k\equiv1-2p\sum_{k\,even}\frac1k\\
&\equiv1-p\sum_{k=1}^n\frac1k\pmod{p^2}.  \Box\end{split}\]

 Leave a Reply

(required)

(required)

This site uses Akismet to reduce spam. Learn how your comment data is processed.