Théorème des restes chinois
-
-
Puisque $p \land q=1$, d'après le théorème de Bachet-Bézout, il existe des entiers $\alpha$ et $\beta$ tels que :
\[ \alpha p + \beta q = 1 \implies \begin{cases} \alpha p \equiv 1 \pmod q \\ \beta q \equiv 1 \pmod p \end{cases} \]
Soit $x$ une solution du système. La congruence $x \equiv a \pmod p$ implique qu'il existe un entier $k \in \mathbb{Z}$ tel que $x = a + kp$.
En substituant dans la deuxième congruence : \begin{align*} x &\equiv b \pmod q \\ a + kp &\equiv b \pmod q \\ kp &\equiv b - a \pmod q \end{align*} En multipliant les deux membres par $\alpha$ (sachant que $\alpha p \equiv 1 \pmod q$) : \begin{align*} \alpha kp &\equiv \alpha(b-a) \pmod q \\ k &\equiv \alpha(b-a) \pmod q \end{align*} Il existe donc un entier $m \in \mathbb{Z}$ tel que $k = \alpha(b-a) + mq$.
En remplaçant $k$ dans l'expression de $x$ : \begin{align*} x &= a + (\alpha(b-a) + mq)p \\ x &= a + \alpha(b-a)p + mpq \end{align*} Une solution particulière s'obtient en posant $m=0$, ce qui donne : \[ x_0 = a + \alpha(b-a)p \] -
Soient $x$ et $y$ deux solutions du système $(S)$. On a :
\[ \begin{cases} x \equiv a \pmod p \\ y \equiv a \pmod p \end{cases} \implies x - y \equiv 0 \pmod p \]
\[ \begin{cases} x \equiv b \pmod q \\ y \equiv b \pmod q \end{cases} \implies x - y \equiv 0 \pmod q \]
Cela signifie que la différence $(x-y)$ est divisible par $p$ et par $q$.
Puisque $p \land q = 1$, leur PPCM est $pq$. L'entier $(x-y)$ est donc divisible par $pq$, d'où : \[ x \equiv y \pmod{pq} \] - Soit $x_0$ une solution particulière de $(S)$. Toute solution $x$ de $(S)$ doit vérifier : \[ x \equiv x_0 \pmod{pq} \] Par conséquent, l'ensemble des solutions du système modulaire $(S)$ est : \[ S = \{ x_0 + mpq \mid m \in \mathbb{Z} \} \]
-
Puisque $p \land q=1$, d'après le théorème de Bachet-Bézout, il existe des entiers $\alpha$ et $\beta$ tels que :
\[ \alpha p + \beta q = 1 \implies \begin{cases} \alpha p \equiv 1 \pmod q \\ \beta q \equiv 1 \pmod p \end{cases} \]
Soit $x$ une solution du système. La congruence $x \equiv a \pmod p$ implique qu'il existe un entier $k \in \mathbb{Z}$ tel que $x = a + kp$.
-
Application :
Premier système $(S_1)$ : \[ \begin{cases} x \equiv 4 \pmod 6 \\ x \equiv 2 \pmod{11} \end{cases} \] On a bien $6 \land 11 = 1$. Cherchons une solution particulière $x_0$ : \begin{align*} x &\equiv 4 \pmod 6 \implies x = 4 + 6m \\ x &\equiv 2 \pmod{11} \implies 4 + 6m \equiv 2 \pmod{11} \\ 6m &\equiv -2 \pmod{11} \\ 6m &\equiv 9 \pmod{11} \end{align*} En multipliant par $2$ (puisque $12 \equiv 1 \pmod{11}$) : \[ m \equiv 18 \equiv 7 \pmod{11} \] Une solution particulière est obtenue pour $m=7$ : \[ x_0 = 4 + 6(7) = 46 \] L'ensemble des solutions de $(S_1)$ (sachant que $6 \times 11 = 66$) est donc : \[ S_1 = \{ 46 + 66k \mid k \in \mathbb{Z} \} \]
Deuxième système $(S_2)$ : \[ \begin{cases} x \equiv 3 \pmod n \\ x \equiv 5 \pmod{n+1} \end{cases} \] On a $n \land (n+1) = 1$. Cherchons une solution particulière $x_0$ : \begin{align*} x &= 3 + an \\ x &= 5 + b(n+1) \end{align*} En égalisant ces deux expressions : \begin{align*} 3 + an &= 5 + bn + b \\ (a-b)n &= 2 + b \end{align*} Une solution particulière s'obtient de manière évidente en posant : \[ \begin{cases} a - b = 0 \\ 2 + b = 0 \end{cases} \implies a = b = -2 \] On en déduit la solution particulière : \[ x_0 = 3 + (-2)n = 3 - 2n \] L'ensemble des solutions du système est donc : \[ S_2 = \{ 3 - 2n + kn(n+1) \mid k \in \mathbb{Z} \} \]