PGCD
dans Arithmétique
Bonjour, je suis élève en terminale S (autant dire que je ne connais pas grand chose à l'arithmétique) et un exercice m'invite à trouver les différentes valeurs de :
Et là, je n'ai pas trouvé de méthode général pour montrer cette conjecture et je suis obligé de le montrer par une disjonction de cas un peu lourde...
Tout aide proposant à une réalisation plus élégante de ce problème me serait très utile.
Merci beaucoup
pgcd(2n+4;n+5), en fonction de n
On remarque que la valeur du pgcd varie selon celle de mod(n,6) (je ne sais pas où est le symbole de la congruence désolé)Et là, je n'ai pas trouvé de méthode général pour montrer cette conjecture et je suis obligé de le montrer par une disjonction de cas un peu lourde...
Tout aide proposant à une réalisation plus élégante de ce problème me serait très utile.
Merci beaucoup
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ensuite, avec ta calculette, fais afficher quelques valeurs de ce pgcd pour essayer de conjecturer quels entiers $n$ donnent $1$, $2$, $3$ ou $6$ pour ce pgcd, puis essaie de démontrer ces conjectures. Par exemple, il semble que $d=6$ si et seulement si $n=1+6k$ ($k \in \mathbb{N}$). À toi d'essayer de montrer ça.
Le PGDC de deux nombres est le même que celui de leur différence qui, dans ton cas, vaut...
A répéter deux fois.
Bonne suite.
si tu connais le fait que $pgcd(a;b)=pgcd(a-b,b)$ (petit exercice fort utile) alors tu devrais pourvoir montrer que $pgcd(2n+4;n+5)=pgcd(n-1;n+5)=pgcd(-6;n+5)$ et alors tu n'as pas plus qu'à faire la fin...
Si tu n'y arrives pas, le salut vient de la lecture des livres... par exemple !
Bon week-end.
Jean-éric
C'est à dire, puisqu'on sait que ce PGCD est soit, 1,2,3,6:
les cas 2,6 ne peuvent se produire que si $n$ est impair. (n est donc de la forme 2k+1 )
Les cas 1,3 ne peuvent se produire que si $n$ est pair. (n est donc de la forme 2k)
La disjonction des cas donne lieu a un arbre de possibilités.
Merci de vos aides
Trouver, pour tout $n$ entier, $pgcd(2n+4,n+5).$
Comme, pour tout $n$ entier, $2n+4$ et $n+5$ sont des entiers, alors $d(n) = pgcd(2n+4,n+5)$ existe.
Puisque $d(n) = pgcd(2n+4,n+5)$ alors $d(n)$ divise $2n+4$ et $d(n)$ divise $n+5$ ; $d(n)$ divise donc toute combinaison liénaire à coefficients entiers de $2n+4$ et $n+5$. En particulier, $d(n)$ divise $2(n+5) - (2n+4) = 6.$ On a donc démontré que, nécessairement, $d(n)$ divise $6.$ Les diviseurs positifs (*) de $6$ sont $1,2,3,6.$
(*) Est-ce une erreur de ne pas le préciser ?
On travaille module $6$ et on distingue les cas suivants, avec $m$ un entier :
- Soit $n=6m$, alors $2n+4 = 12m+4$ et $n+5=6m+5$ : parmi les diviseurs de $6$, seul $1$ divise ces quantités. On a donc $d(6m) = 1.$
- Soit $n=6m+1$, alors $2n+4 = 12m+6$ et $n+5=6m+6$ : parmi les diviseurs de $6$, $6$ divise ces quantités et est le plus grand. On a donc $d(6m+1) = 6.$
- Soit $n=6m+2$, alors $2n+4 = 12m+8$ et $n+5=6m+7$ : parmi les diviseurs de $6$, seul $1$ divise ces quantités. On a donc $d(6m+2) = 1.$
- Soit $n=6m+3$, alors $2n+4 = 12m+10$ et $n+5=6m+8$ : parmi les diviseurs de $6$, $2$ divise ces quantités et est le plus grand. On a donc $d(6m+3) = 2.$
- Soit $n=6m+4$, alors $2n+4 = 12m+12$ et $n+5=6m+9$ : parmi les diviseurs de $6$, $3$ divise ces quantités et est le plus grand. On a donc $d(6m+4) = 3.$
- Soit $n=6m+5$, alors $2n+4 = 12m+14$ et $n+5=6m+10$ : parmi les diviseurs de $6$, $2$ divise ces quantités et est le plus grand. On a donc $d(6m+5) = 2.$
On résume les résultats :
$pgcd(2n+4,n+5) = 1$ pour tout $n = 0, 2 \, [6]$,
$pgcd(2n+4,n+5) = 2$ pour tout $n = 3, 5 \, [6]$,
$pgcd(2n+4,n+5) = 3$ pour tout $n = 4 \, [6]$,
$pgcd(2n+4,n+5) = 6$ pour tout $n = 1 \, [6].$
Il est clair que si $n$ est impair ces deux nombres sont divisibles par $2$ et qu'ainsi leur PGCD est un multiple de $2$
Et Compte tenu du fait que ce PGCD est un des nombres 1,2,3,6 alors si $n$ est impair ce PGCD est 2 ou 6.
Si $n=2k+1$ alors $2n+4=2(2k+1)+4=4k+6$ et $n+5=2k+6$
Pour que $4k+6$ soit divisible $3$ il faut et il suffit que $4k$ soit divisible par $3$.
Or, $3$ est premier avec $4$ donc d'après le théorème de Gauss, $3$ divise $4k$ implique $3$ divise $k$.
Pour que $2k+6$ soit divisible par $3$ il faut et il suffit que $2k$ soit divisible par $3$
Or, $2$ est premier avec $2$ donc d'après le théorème de Gauss, $3$ divise $2k$ implique $3$ divise $k$.
Ainsi, $PGCD(2n+4,n+5)=6$ si et seulement si $n=6l+1$
Ainsi, $PGCD(2n+4,n+5)=2$ si et seulement si $n=6l+3$ ou $n=6l+5$
Si $n$ est pair le PGCD de $2n+4$ et $n+5$ est un des nombres $1,3$
Si $n$ est pair alors $n=2k$ et donc $2n+4=4(k+1)$, $n+5=2k+5=2(k+1)+3$
Pour que $4(k+1)$ soit divisible par $3$ puisque $3$ est premier avec $4$, d'après le théorème de Gauss, $3$ doit diviser $k+1$.
Si $k+1=3l$ alors $n=2k=2(k+1)-2=6l-2=6l+4-6=6(l-1)+4$
Ainsi, $PGCD(2n+4,n+5)=3$ si et seulement si $n=6u+4$.
Et donc,
$PGCD(2n+4,n+5)=1$ si et seulement si $n=6u+2$ ou $n=6u$.
On retrouve les résultats déjà donnés par YvesM.
dans Z et en exploitant (a, b) = (a, b + ma), on a :
(2n+4, n+5) = (n+5, -6)
En posant n = 6m + k, avec k dans [0, 5], on a :
(n+5, -6) = (6m+k+5, -6) = (-6, k+5)
Soit
(-6, 5) = 1 pour k = 0,
(-6, 6) = 6 pour k = 1,
(-6, 7) = 1 pour k = 2,
(-6, 8) = 2 pour k = 3,
(-6, 9) = 3 pour k = 4,
(-6, 10) = 2 pour k = 5.