système, congruences

steven17 · December 2007

Bonjour, je révise mes partiels et j'ai quelques problèmes pour résoudre ce genre de système:

x = 3 (mod 5)
x = 8 (mod 13)

Si quelqu'un pouvait m'expliquer comment faire ça serait sympa

Merci d'avance.

GreginUK · December 2007

Salut,

tu prends la première équation, et tu écris ce que ça veut dire en termes d'égalité entre entiers. La première équation s'écrit ici:

$x=3+5\lambda,\lambda\in\mathbb{Z}$.

Ensuite, tu reportes dans la deuxième, et tu résouds en $\lambda$. On a donc

$5\lambda=5 \mod 13$.

Puisque $5$ est inversible, en multipliant par son inverse mod 13, on trouve

$\lambda=1 mod 13$. (ici on n'a pas besoin de calculer l'inverse de 5 mod 13 explicitement, mais en général, on ne peut pas l'éviter)

Donc $\lambda=1+13m, m\in\mathbb{Z}$. Ainsi, $x=8+65m, m\in\mathbb{Z}$.

gb · December 2007

Le système est équivalent à l'existence de $p$ et $q$ entiers tels que $x = 3+5p$ et $x = 8+13q$.
On est donc ramené à résoudre $3+5p=8+13q$.
5 et 13 sont premiers entre eux, un peu d'algorithme d'Euclide, ou une bonne intuition, founissent $8 \times 5 - 3 \times 13 = 1$.
On est face à $5p - 13q = 5 = 40 \times 5 - 15 \times 13$ soit $5(p-40) = 13(q-15)$, et le lemme de Gauss assure que $p-40$ est divisible par 13.
On recolle les morceaux : il existe $k$ entier tel que $x = 3 + 5p = 3 + 5(13k+40) = 65k+203$.

Avec un peu d'habitude, on peut voir immédiatement que le système se met sous la forme
$$\left\{ \begin{array}{l} x-8 \equiv -5 \equiv 0 \pmod{5} \\ x-8 \equiv 0 \pmod{13} \end{array} \right.$$
ce qui équivaut à $x-8$ est multiple du ppcm de 5 et 13, soit 65, et par suite il existe $k$ entier tel que $x = 8 + 65k$.

Pour la relation de Bezout entre 5 et 13, je viens de m'apercevoir qu'il y a plus simple avec $26 - 25 = 1$...

borde · December 2007

Sinon, puisque tu parles de partiels, on en déduit que tu es au moins en Bac + 1, et puisque $5$ et $13$ sont premiers entre eux (puisque premiers distincts), le théorème chinois s'applique et donne immédiatement : $$x \equiv 13 \times 3 \times \alpha_1 + 5 \times 8 \times \alpha_2 \pmod {5 \times 13},$$ où les $\alpha_i$ sont solutions des congruences $13 \alpha_1 \equiv 1 \pmod 5$ et $5 \alpha_2 \equiv 1 \pmod {13}$. On trouve assez rapidement que $\alpha_1 = 2$ et $\alpha_2=8$ conviennent, de sorte que les solutions sont : $$x \equiv 8 \pmod {65}.$$

Borde.

système, congruences

Réponses

Bonjour!

Catégories

In this Discussion