Bachet定理声称，若两个正整数$a,b$互素，则存在整数$u,v$,使得

\begin{equation}

au+bv=1

\end{equation}

Bachet定理的证明, 通常书上使用欧几里德算法，那是一个构造性的证明,构造出了具体的$u,v$.但是Bachet定理的一个特殊情形不一定用到构造性的证明方法,只用到存在性的证明就足够了.下面,我来给出弱Bachet定理存在性的证明.

 

我先证明引理1:

若正整数$a$是一个素数，则对于集合$\{1,2,\cdots ,a-1\}$中的任何一个元素$m$来说，都存在该集合中的唯一的一个元素$n$,使得

\begin{equation}

mn\equiv 1 \mod a

\end{equation}

 

证明:证明请参见我的博文的最后一部分.那个证明是存在性的证明,不是构造性的.

 

利用引理1很容易证明下面的弱Bachet定理:

若正整数$a$是一个素数，且正整数$b$不是$a$的倍数，则存在整数$p,q$,使得

\begin{equation}

pb+qa=1

\end{equation}

这是因为，$b$不是$a$的倍数，所以$b$关于模$a$的非负的最小剩余在集合$\{1,2,\cdots,a-1\}$里，设该非负的最小剩余为$t$,即$t\in\{1,2,\cdots,a-1\}$,且

\begin{equation}\label{eq:2233}

b\equiv t \mod a

\end{equation}

由引理1可知，存在$\{1,2,\cdots,a-1\}$里的唯一元素$n$,使得

\begin{equation}

tn\equiv 1\mod a

\end{equation}

结合\ref{eq:2233},再根据同余的性质可知

\begin{equation}

bn\equiv tn \equiv 1 \mod a

\end{equation}

即$bn+ak=1$,其中$k$是一个整数.$\Box$

 

 

注:如要再进一步把弱Bachet定理推广成Bachet定理，同时避免用到欧几里德算法，实在已经非本人能力所及了.就此打住吧.