线性同余方程維基百科,自由的 encyclopedia 在数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次,即形如: a x ≡ b ( mod n ) ( 1 ) {\displaystyle ax\equiv b\ {\pmod {n}}\ \ \ \ (1)} 的方程。此方程有解当且仅当 b {\displaystyle b} 能够被 a {\displaystyle a} 与 n {\displaystyle n} 的最大公约数整除(记作 gcd ( a , n ) | b {\displaystyle \gcd(a,n)|b} )。这时,如果 x 0 {\displaystyle x_{0}} 是方程的一个解,那么所有的解可以表示为: { x 0 + k n d ∣ k ∈ Z } . {\displaystyle \{x_{0}+k{\frac {n}{d}}\mid k\in \mathbb {Z} \}.} 其中 d {\displaystyle d} 是 a {\displaystyle a} 与 n {\displaystyle n} 的最大公约数。在模 n {\displaystyle n} 的完全剩余系 { 0 , 1 , … , n − 1 } {\displaystyle \{0,1,\ldots ,n-1\}} 中,恰有 d {\displaystyle d} 个解。
在数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次,即形如: a x ≡ b ( mod n ) ( 1 ) {\displaystyle ax\equiv b\ {\pmod {n}}\ \ \ \ (1)} 的方程。此方程有解当且仅当 b {\displaystyle b} 能够被 a {\displaystyle a} 与 n {\displaystyle n} 的最大公约数整除(记作 gcd ( a , n ) | b {\displaystyle \gcd(a,n)|b} )。这时,如果 x 0 {\displaystyle x_{0}} 是方程的一个解,那么所有的解可以表示为: { x 0 + k n d ∣ k ∈ Z } . {\displaystyle \{x_{0}+k{\frac {n}{d}}\mid k\in \mathbb {Z} \}.} 其中 d {\displaystyle d} 是 a {\displaystyle a} 与 n {\displaystyle n} 的最大公约数。在模 n {\displaystyle n} 的完全剩余系 { 0 , 1 , … , n − 1 } {\displaystyle \{0,1,\ldots ,n-1\}} 中,恰有 d {\displaystyle d} 个解。