Arithmétique et PGCD

[Théaurème]

Bonjour/ bonsoir à tous.
Je suis actuellement bloqué sur un exercice d'arithmétique dans Z. L'énoncé est le suivant : "Soit k un entier naturel, a=3k+4 et b=5k+3. Prouvez que les seuls diviseurs positifs possibles et communs à a et à b sont 1 et 11."
Je n'arrive pas à appliquer le théorème adapté, malgré mes manuels... Quelqu'un pourrait m'expliquer comment procéder ? Merci

[infernaleur]

Salut, on note d le diviseur commun à a et b
d divise donc 3k+4 et 5k+3
Ne vois-tu pas une propriété (ou théorème) que tu pourrais utiliser ici ?

[Théaurème]

Je pensais utiliser l'algotithme d'Euclide (Je pense que c'est celui-ci), selon lequel, quelque soit k élément de Z*, PGCD (ka,kb)=|k|PGCD (a,b). Mais je ne sais pas si celui-ci est appliquable, puisque ce sont dans l'énoncé deux additions

[infernaleur]

tu cherche trop compliquer c'est une propriété que tu as du voir au tout début de l'arithmétique.
d | 3k+4
d|5k+3
Je pense que les "k" te déranges, que peux tu faire pour les supprimer ?

[Ben314]

Salut,
Si un entier naturel d divise à la fois a et b alors il divise évidement a+b, a-b, a+2b, 5a-4b, et plus généralement tout ce qui s'écrit (modulo que les ? soient des entiers bien sûr).
Reste à trouver quoi prendre de malin comme coefficients.

[Théaurème]

Je devrais les soustraire l'un à l'autre ? Il n'y aurait plus de k
Seulement, j'arrive sur d|2k-1, et je ne vois pas comment en déduire que 11 et 1 sont les seules valeurs possibles de d

[infernaleur]

Voici la propriété que je te demandais d'utiliser :

si d divise a et b alors il divise toute combinaison linéaire de a et b.
Donc d divise au+bv où u et v sont des entiers relatifs.

Choisis les bons coefficients pour u et v afin de supprimer les k et tu pourra conclure .

[Théaurème]

Merci beaucoup !
Donc, pour la rédaction, je peux écrire :
(d|a et d|b) => d|ua+vb
On pose u=5 et v=-3
Donc, d|5 (3k+4)+(-3)(5k+3) <=> d|15k+20-15k-9 <=> d|11. 11 étant premier, d prend soit la valeur 1, soit la valeur 11.
?
Ça suffit à prouver que 11 et 1 sont les seuls possibles ?

[infernaleur]

Oui je te rappel que l'on a noté d un diviseur commun à a et b, et toi tu as montré que d vaut forcément 1 et 11
(cependant fait attention, on aurait pu aussi rajouter -1 et -11 comme diviseur commun mais ton énoncé précise que les diviseurs communs doivent être positifs, ce qui n'est pas toujours le cas dans les énoncés !)
Donc 1 et 11 sont bien les seuls possibles.

[Théaurème]

Merci
Donc, pour que je me souvienne comment procéder : c'est bien l'identité de Bézout ?

[infernaleur]

Non attention ^^
on appelle ce procédé "la combinaison linéaire " ( il existe peux être un autre nom je ne sais pas)

l'identité de Bézout dit que ;
Soient a et b deux entiers relatifs (différent de 0), on note d=PGCD(a,b).
il existe u,v des entiers relatifs tels que d=au+bv

[infernaleur]

En général tu as du voir le théorème de Bézout pour résoudre des équations diophantiennes (ax+by=c)

[Théaurème]

Oh, d'accord, je ne confonderai plus à l'avenir !
Merci pour votre aide

[infernaleur]

Au plaisir