• 补充一些关于线性同余的数论知识

    与数学相关
    服务器君一共花费 17.357 ms 进行了 2 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    补充点数学知识。

    关于同余

    同余表示两个整数除以正整数m时有相同余数的一种情况。比如 5 mod 3 = 2,8 mod 3 = 2,那么5、8模3同余

    定义:a和b为整数且m是正整数,如果有m|(a-b),即m是a-b的因子,则称a、b模m同余,记a≡b(mod m)

    定理1:令m为正整数。若a≡b(mod m),c≡d(mod m),那么a+c≡b+d(mod m),ac≡bd(mod m)。

    证明:因为a≡b(mod m),c≡d(mod m),所以有整数s和t使b=a+sm,d=c+tm。于是

    b+d=(a+sm)+(c+tm)=(a+c)+m(s+t)

    及bd=(a+sm)(c+tm)=ac+m(at+cs+stm)

    因此 a+c≡b+d(mod m),ac≡bd(mod m)

    比如 7≡2(mod 5),11≡1(mod 5),从定理1知

    18=7+11≡2+1=3(mod 5) 且 77=7 × 11≡2 × 1=2(mod 5)

    关于线性同余

    形如ax≡b(mod m)的同余式成为线性同余,x为变量。

    若有aλ≡1(mod m),则λ成为a模m的逆,且逆存在如下定理:

    在a和m互质且m>1时,比存在a的逆λ,且λ模m唯一。

    在性证明可以利用a和m互质(欧几里德算法逆过程)构造sa+tm≡1(mod m)即可。

    对于求解一个同余方程aλ≡1(mod m)的逆可以通过建立如下关系式:

    令 aλ+km = 1,k为整数,满足条件的λ即为逆

    方程逆不止一个,但模m相同。

    定理2:如果a和m为互素的整数,m>1,则存在a的模m的逆。而且这个逆模m是唯一的。(即有小于m的唯一正整数a¯,如果这样的a¯存在的话。这样的a¯称为a模m逆,且a的任何别的模m逆均和a¯模m同余。)

    证明:由定理1及gcd(a,m)=1知,有整数s和t使 sa+tm=1

    于是 sa+tm≡1(mod m)

    由于tm≡0(mod m),所以 sa≡1(mod m)

    结论是s为a的模m逆。

    比如:求3的模7逆。

    由于gcd(3,7)=1,定理说明存在3模7的逆。若用欧几里得算法求3和7的最大公约数,算法很快结束:7=2×3+1

    从这一等式看到 −2×3+1×7=1

    这说明-2是3模7的一个逆。(注意,模7同余于−2的每个整数也是3的逆,例如5,−9,12等。)

    例:求线性同余3x≡4(mod 7)的解。

    −2是3模7的逆。在同余式的两边同乘以−2得 −2×3x≡−2×4(mod 7)

    因为−6≡1(mod 7)且−8≡6(mod 7),所以若x是解,必有x≡−8≡6(mod 7)。于是由定理1,有 3x≡3×6≡18≡4(mod 7)

    这说明所有这种x满足问题中的同余式。结论是,同余方程的解是使x≡6(mod7)的整数。

    从有关线性同余系统的中国古典问题而得名的中国剩余定理,可以这样叙述:只要线性同余系统的模数两两互素,则该系统有解,而且以所有模数之乘积取模,解是唯一的。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [PHP程序设计] PHP中的Hash算法 3 个条目
  2. [计算机算法] TAOCP与算法 12 个条目
  3. [PHP程序设计] htaccess 设置技巧 6 个条目
  4. [JavaScript程序设计] jQuery与表单操作 2 个条目
  5. [运维管理] 防火墙原理与应用 5 个条目
  6. [运维管理] 路由器与交换机 4 个条目
  7. [数据库技术] MySQL常用自带函数 3 个条目
  8. [移动开发] Android加载器Loaders 5 个条目
  9. [数据结构] 散列表(哈希表) 13 个条目
  10. [计算机算法] 从双端队列引出的卡特兰数 3 个条目
  11. [Python程序设计] Django Web环境配置 2 个条目
  12. [Linux操作系统] 基本 Linux Shell 命令 2 个条目
窗口 -- [博客]