Pgcd et nombre premiers

[loic]

Bonjour voila je bloc a cet exercice pourriez vous m'aider

Exercice:
On pose a=3304,b=2660 et delta=pgcd(a,b)
1)Calculer le pgcd(a,b), et déterminer deux entiers u et v vérifiant au=bv=delta
2)Si on divise 3312 et 2265 par un meme entier naturel n, on obtient respectivement 8 et 5 comme reste.
Calculer les valeurs possibles de n.



Pour la question 1, à l'aide de l'algorithme d'euclide je trouve pgcd(a,b)=28 donc delta=28
Mais je ne vois pas comment faire la suite.

[sos-math(21)]

Bonjour,
Je suis d'accord avec ton pgcd :
tu as obtenu les divisions successives :
3304=1*2660+644
2660=4*644+84
644=7*84+56
84=1*56+28
Il faut ensuite tout remonter en écrivant les égalités à l'envers :
on part de
28=84-56
= 84-644+7*84=8*84-644
=8*(2660-4*644)-644
=8*2660-32*644-644=8*2660-33*644
=8*2660-33*(3304-644)=8*2660-33*3304+33*2660=41*2660-33*3304 et cela marche u=-33 et v=41

[loic]

Merci pour cette aide
Pouvez vous m'indiquer comment démarrer pour la question 2 ?

[sos-math(21)]

Fais le lien avec la question précédente :
la division de 3312 par un nombre n avec un reste égal à 8 signifie 3312=n*q+8 ce qui donne 3304=n*q (en passant le 8 de l'autre côté) donc n est un diviseur de 3304.
Fais la même chose pour l'autre nombre et tu dois faire le lien avec la question précédente.

[loic]

je trouve pour l'autre nombre 2665=n*q+5 ce qui donne 2660=n*q donc n est un diviseur de 2

donc comme n divise 3304 et 2660 alors n peut etre égal au pgcd donc n peut etre égal a 28

Est ce correct

[loic]

j'ai trouvé que 2660=n*q donc n est un diviseur de 2660

Mais je ne vois pas quel lien utilisé a part dire que comme n est un diviseur de 3304 et de 2660 alors il peut etre egal au pgcd donc a 28

Merci de me dire si c'est correct.

[sos-math(21)]

En gros, c'est cela. Mais pour la conclusion, c'est plus précis
tu obtiens bien que n est un diviseur commun à 2660 et 3304.
Comme 28 est le plus grand des diviseurs, une des propriétés du PGCD dit que si on a un diviseur commun à deux entiers, alors il divise le pgcd de ces deux entiers.
Donc n est un diviseur de 28.
A toi de dresser la liste des diviseurs de 28.

[loic]

d'accord mais n ne peut pas etre egal a 1 ou 2 ou 14 or ils sont diviseur de 28

[sos-math(21)]

Certes il faudra prendre ceux qui sont supérieurs à 8 (car dans la division euclidienne, le reste est toujours inférieur au diviseur donc n>8 et n>5))
Il y a donc ...

[loic]

il y a donc 14 et 28

[sos-math(21)]

Cela me paraît honnête.
Reprends tout cela point par point et rédige ta réponse, cela te permettra de passer sur chaque étape et de contrôler ton travail.