線性同餘方程維基百科,自由的 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} 個解。