Divisibilité et PGCD

[Patrick]

Bonjour,

J'ai besoin de votre expertise pour cet exercice qui me donne du mal.
Il est articulé autour des propriétés de la divisibilité et du PGCD.

Soit \((m,n)\in\mathbb{N}^2\), deux entiers naturels quelconques,
on considère les nombres :
\(A=11m+2n\) et \(B=18m+5n\)
1°) Démontrer l'équivalence : \(19|A\quad\Longleftrightarrow\quad 19|B\)
2°) On suppose \(m\wedge n=1\), montrer que \(A\) et \(B\)
ne peuvent avoir d'autre diviseur commun que \(1\) et \(19.\)
_______________________________________________

1°) \(19=55\times 11-18\times 2\) est le déterminant de ce petit système en \(n\) et \(m.\)
On en déduit immédiatement que : \(19|m\) et \(19|n\).
Maintenant j'utilise la règle de la distributivité de l'implication et, j'espère, sans se vautrer !?
\(\Big[(19|m\) et \(19|n)\Rightarrow 19|A\Big]\Rightarrow\Big[(19|m\) et \(19|n)\Rightarrow 19|B\Big]\text{ donc }(19|m\) et \(19|n)\Rightarrow(19|A\Rightarrow 19|B)\)
De la même façon : \((19|B\Rightarrow 19|A)\text{ donc }(19|A\quad\Longleftrightarrow\quad 19|B).\quad\) CQFD ?

2°) Montrer que \(A\) et \(B\) ne peuvent avoir d'autre diviseur commun que \(1\) et \(19\) (nb 1er) équivaut à dire que : \(A\wedge B=19.\)
Ce qui revient à démontrer que : \((m\wedge n=1)\quad\Longrightarrow\quad(A\wedge B=19)\ ?\)

J'attends vos réponses/conseils,
Merci @+

[sos-math(12)]

Bonsoir

Il me semble qu'il y a une erreur de raisonnement dès le début. En effet en utilisant une méthode par combinaison on obtient que \(m=\frac{5A-2B}{19}\). Ce qui ne signifie absolument pas que 19 divise m.

Bonne continuation.

[Patrick]

Merci pour ta réponse.

Il me semble qu'il y a une erreur de raisonnement dès le début. En effet en utilisant une méthode par combinaison on obtient que \(m=\frac{5A-2B}{19}\). Ce qui ne signifie absolument pas que 19 divise m.

Alors, j'étais vraiment loin de la solution...

1°) Ok, on trouve par combinaison/résolution suivant \(n\) et \(m\) :
\(\qquad 19n=-18A+11B\text{ et }19m=5A-2B.\)
- Rappels : \((\,d|a\text{ et }d|a-b\,)\Rightarrow d|b,\) et Th Gauss : \((\,d|ab\text{ et }d\wedge a=1\,)\Rightarrow d|b.\)
SI \(19|B\quad\Rightarrow\quad 19|(11B-19n)\quad\Rightarrow\quad 19|18A\quad\Rightarrow\quad 19|A,\)
SI \(19|A\quad\Rightarrow\quad 19|(5A-19m)\quad\Rightarrow\quad 19|2B\quad\Rightarrow\quad 19|B,\)
C'était pas évident, mais on a démontré que : \(19|A\quad\Longleftrightarrow\quad 19|B.\)

2°) Montrer que \(A\) et \(B\) ne peuvent avoir d'autre diviseur commun que \(1\) et \(19\) (nb 1er) équivaut à dire que : \(A\wedge B=19.\)
Ce qui revient à démontrer que : \((m\wedge n=1)\quad\Longrightarrow\quad(A\wedge B=19)\ ?\)

@+

[sos-math(12)]

Bonjour :

Bonne démarche pour le 1).
Et la remarque pour le 2) est pertinente. reste à la mettre en oeuvre.

Bonne continuation.

[Patrick]

Et la remarque pour le 2) est pertinente. reste à la mettre en oeuvre.

Ok merci, il faut bien démontrer : \((m\wedge n=1)\quad\Longrightarrow\quad(A\wedge B=19).\)

Si on pose : \(d=A\wedge B\), il est clair que l'on a :
\((d|A\text{ et }d|B)\quad\Longrightarrow\quad(d|19n\text{ et }d|19m).\)
De plus, si on remarque que : \(19\times(m\wedge n)=(19n\wedge 19m)=19,\)
Finalement, on en déduit que : \((A\wedge B=19)\ ?\)

Merci pour vos remarques,
@+

[sos-math(21)]

Bonjour,
As-tu vu le théorème de Bezout ? Avec le théorème de bezout c'est plus clair.
Sinon, on travaille comme tu l'as un peu fait :
si d=pgcd(A,B), alors d|A et d|B, donc d|5A-2B et d|19m
puis d|18A-2B donc d|19n donc d est un diviseur commun de 19m et 19n et d divise donc le pgcd de 19m et 19n, lequel est 19 (en effet le pgcd de 19m et 19n est le seul entier k tel que 19m=kp et 19n=kp', avec p et p' premiers entre eux, donc comme m et n sont premiers entre eux, par unicité, on a bien pgcd(19n;19m)=19) . donc d=1 ou bien d=19.
Reprends tout cela et surtout rédige bien tes réponses, en citant bien les propriétés utilisées (c'est important en arithmétique, car il y a plusieurs propriétés qui se ressemblent et on peut faire des amalgames)
Bon courage