裴蜀定理说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为裴蜀等式):
\(若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。\)
它的一个重要推论是:a,b互质的充分必要条件是存在整数x,y,使得\(ax+by=1\).
裴蜀等式变体与模运算
\[bx +kn=1 \]- 以上方程在b和n互素时,x有整数解
- 在模运算中,定义\(x\)为\(b\)模\(n\)的逆,记作\(b^{-1}(mod \ n)=x(mod \ n)\)
\(若a|b则a=kb,否则a=kn+r,余数则为r\)
-
如果存在整数\(z\)使得$ 1/a \equiv z (mod \ n)$,则\(1 \equiv az(mod \ n)\),由同余定义可得
\(az+(-kn)=1\)
仅当\(a\)和\(n\)互素令这样的整数\(z\)存在 -
\(因此1/2(mod \ 7)有解,而1/2(mod \ 10)无解\)
-
\(5/2(mod \ 7) = 5*2^{-1}(mod \ 7)=5*4(mod \ 7) = 6(mod \ 7)\)
标签:基础,kn,整数,概念,ax,密码学,裴蜀,mod From: https://www.cnblogs.com/MiddleByPass/p/17136076.html