例 9 6.1一次同余式与中国剩余定理
6.1 一次同余式与中国剩余定理
一次同余式与中国剩余定理 好 一 次同余式 中国剩余定理
中国剩余定理 一次同余式与中国剩余定理 一次同余式
一次同余式 。定义 ■给定整数a,b和正整数n,当mod n≠0，则称x=b mod n为模 n的一次同余式，其中x为变量。 。一次同余式有解的定理 ■一次同余式ax三b mod ni有解，当且仅当gcd(a,n)b。如果这个 同余式有解，则共有gcd(a,)个不同的解。 ■如果x是满足c三b mod n的一个整数，那么满足x三xo mod n 的所有整数也能满足≡b mod n。也就是说，x的同余类都 满足心三b mod n。我们称x的同余类为同余式的一个解
定义 给定整数a, b和正整数n，当a mod n≠0，则称ax ≡ b mod n为模 n的一次同余式，其中x为变量。 一次同余式有解的定理 一次同余式ax ≡ b mod n有解，当且仅当gcd(a, n)|b。如果这个 同余式有解，则共有gcd(a, n)个不同的解。 如果x0是满足ax ≡ b mod n的一个整数，那么满足x ≡ x0 mod n 的所有整数也能满足ax ≡ b mod n 。也就是说，x0的同余类都 满足ax ≡ b mod n 。我们称x0的同余类为同余式的一个解。 一次同余式
一小 次同余式组 。在密码学中，有时候需要求解一次同余式组： x=b modn x≡b2modn2 x=b mod ng ■其中，当时，gcd(nn)-l。 ■我国古代的《孙子算经》中就提到了这种形式的问题：“今有物 不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物 几何”。 x=2mod3 等价于求解同余式组： x≡3mod5 x=2mod 7
在密码学中，有时候需要求解一次同余式组： 其中，当i≠j时，gcd(ni , nj )=1。 我国古代的《孙子算经》中就提到了这种形式的问题：“今有物 不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物 几何”。 一次同余式组 等价于求解同余式组： 1 1 2 2 mod mod mod k k x b n x b n x b n 2mod 3 3mod5 2mod 7 x x x
中国剩余定理 。定理 ■设n1,n2,,nw是两两互素的正整数，b1,b2,,b是任意k个整 数，则同余式组 x≡b mod n x≡b2modn2 x≡b,mod ng ■在模N=n12nk下有唯一解x三∑b,N,y,modN i=1 ■其中，N=NWny=N1 mod n,i=l,2,,ko
定理 设n1 , n2 , …, nk是两两互素的正整数，b1 , b2 , …, bk是任意k个整 数，则同余式组 在模N=n1n2…nk下有唯一解 其中，Ni =N/ni , yi≡Ni -1 mod ni , i=1, 2, …, k。 中国剩余定理 1 1 2 2 mod mod mod k k x b n x b n x b n 1 mod k i i i i x b N y N