arithmétique

Bonsoir , je bloque dans cet exercice . merci pour votre aide
I)a,b,p,q désignent des entiers naturels non nuls .
1) supposons que a=9p+4q et b=2p+q . Montrer que PGCD(a,b)=PGCD(p,q)
2) en déduire que 9p+4 et 2p+1 sont premiers entre eux.
3)déterminer le PGCD des entiers naturels 9p+4 et 2p-1 en fonction des valeurs de p
II) montrer par récurrence que pour tt entier naturel non nul n ,
5^n-(2^n+3^n) est divisible par 6

pour 1) a=4b+p donc PGCD(a,b)=PGCD(b,p)=PGCD(2p+q,p) mais comment continuer pour dire que c'est = PGCD(p,q)?
2) q=1 PGCD(9p+4,2p+q)=PGCD(p,1)=1
3) et II) je sèche complètement . merci

Bonsoir,

On a les propriétés suivantes:
Pour tout x, y entier non nul, PGCD(x,y)=PGCD(x-y,y)
Pour tout x, y entier non nul, PGCD(x,y)=PGCD(x,y)

Du coup, tu peux conclure à partir de ton raisonnement pour la 1).

La 2) est correcte de mon point de vue.

Pour la 3) comme pour la II), je n'ai pas d'idée à l'instant t. Le II) me paraît déconnecté du I) ce qui ne semble pas logique mais bon, il y a peut-être un moyen de faire le lien.

PGCD(a,b)=PGCD(b,p)=PGCD(2p+q,p)=PGCD(p+q,p)=PGCD(p,q)donc c'est bon merci
pour II) notre prof nous a dit qu'il est déconnecté de I

Ok ça marche.

Du coup, connais-tu la notion de congruence ?

non pas encore !

Arf! Mince, c'est dommage car du coup, cela se démontrait sans récurrence pour le II) en utilisant la congruence modulo 6 dans le cas dune puissance paire puis le cas d'une puissance impaire.
Il va falloir que je cherche un autre angle d'attaque du coup.

Je double poste, en fait, c'est plus simple que prévu avec la récurrence.

L'initialisation est évidente (on pose n=1, et on trouve que l'expression vaut 0 ce qui est bien divisible par 0).

Ensuite, on suppose qu'il existe un entier n tel que: 6 divise 5ⁿ - (2ⁿ+3ⁿ)

Montrons que: 6 divise 5ⁿ⁺¹ - (2ⁿ⁺¹+3ⁿ⁺¹)

1) Comment écrire autrement l'hypothèse: 6 divise 5ⁿ - (2ⁿ+3ⁿ) ? Reviens à la définition de "un entier est divisible par un autre".

2) Ecrire une égalité de 5ⁿ⁺¹ en fonction de l'hypothèse de récurrence.

3) En déduire une égalité pour 5ⁿ⁺¹ - (2ⁿ⁺¹+3ⁿ⁺¹) utilisant l'hyposthèse de récurrence.

4) Par des factorisation bien choisies, conclure que 6 divise 5ⁿ⁺¹ - (2ⁿ⁺¹+3ⁿ⁺¹)

5) Terminer la rédaction de la récurrence.

Bon courage et n'hésite pas à poser tes questions!

pour 1 ) 5^n - (2^n+3^n) = 6k , k entier naturel
2) Ecrire une égalité de 5^(n+1) en fonction de l'hypothèse de récurrence. comment ça se fait !!

Ok pour la 1),

Tu as donc une identité que tu peux manipuler à loisir sans changer la véracité de l'égalité en soi. Il est donc aisé d'isoler 5ⁿ pour ensuite exprimer 5ⁿ⁺¹.

5^(n+1)=5^n*5=5(6k+(2^n)+(3^n))=30k+5*(2^n)+5*(3^n)
30k+5*(2^n)+5*(3^n)-2^(n+1)-3^(n+1)=
30k+3*2^n+2*3^n c'est bon donc   merci pour votre aide

mais je dois préciser pour I) qu'on pas vu la prop : Pour tout x, y entier non nul, PGCD(x,y)=PGCD(x-y,y)
cependant je pense qu'on doit utiliser la propriété d’Euclide une autre fois ( si a=bq+r alors
PGCD(a,b)=PGCD(b,r) ) mais comment ?

Bonsoir,

Nickel pour le II).

Pour l'autre question, PGCD(x,y)=PGCD(x-y,y) est une évidence:

Soit d=PGCD(x,y).

Donc d divise x et d divise y. Il existe k et q tels que: x=k*d et y=q*d
D'où, d divise x-y car x-y=d*(k-d) (en supposant x>y ce qui permet de supposer que k>d par comparaison des quotient).

Donc d divise le PGCD(x-y,y)=D

Inversement, D divise x-y et y donc il existe k' et q' tels que x-y = k'*D et y=q'*D
Donc: (par addition des deux équations): x = (k'+q')*D
D'où: D divisie x et D divise y

Conclusion: D divise le PGCD(x,y)=d

Conclusion générale: D=d ce qui montre que PGCD(x,y)=PGCD(x-y,y)

Et c'est grâce à cette propriété qu'on démontre que PGCD(x,y)=PGCD(y,r) lorsque x=y*q+r.
Car justement, on utilise le fait que: PGCD(x,y)=PGCD(x-y,y)=...=PGCD(x-q*y,y)=PGCD(r,y)
Et PGCD(r,y)=PGCD(y,r) par symétrie de la fonction PGCD.

En espérant que tout ceci paraît plus clair ainsi.

Bon courage!

c'est bon néanmoins on a b=2p+q donc on a PGCD(b,p)=PGCD(p,q) ce qui donne directement le résultat !!
pour 3)
j'ai montré que le PGCD des entiers naturels 9p+4 et 2p-1 est soit 1 soit 17 ( c'est suivant les valeurs de p )
puis j'ai supposé que PGCD(9p+4;2p-1)=17 donc 2p-1=17k
ce qui implique que k est impair donc k=2m+1
2p-1=17(2m+1)
2p-1=34m+17
2p=34m+18
p=17m+9
mais puisqu'il s'agit d'un ensemble , on doit passer par des équivalences ..
je sais pas ce que je dois ajouter à cette démarche ??

Bonjour,

Lorsque tu écris cela:

Citation :

on a b=2p+q donc on a PGCD(b,p)=PGCD(p,q)

Tu n'utilises pas la propriété:
Si la division euclidienne de a par b donne l'égalité: a=bq+r alors PGCD(a,b)=PGCD(b,r)

mais bien la propriété:
Si a et b sont deux entiers tel que a>b,  PGCD(a,b)=PGCD(a-b,b)

En effet, dans l'écriture b=2p+q rien n'indique que 0<q<p ce qui permettrait d'affirmer qu'il s'agit de la division euclidienne de b par p.

Ensuite pour la 3),

Citation :

j'ai montré que le PGCD des entiers naturels 9p+4 et 2p-1 est soit 1 soit 17

Comment ?
Par test, j'arrive à la même conclusion que toi à savoir que le PGCD semblerait être 1 ou 17 mais de la à le démontrer, il faut procéder par une démarche empirique en supposant tous les cas possibles.

La démarche que tu entames ensuite est la bonne de mon point de vue. A savoir qu'il faut procéder par analyse synthèse. On suppose que le PGCD est 17 puis on trouve un ensemble de p possibles.
Ensuite, on vérifie que l'ensemble trouvé fonctionne (c'est à dire que le PGCD donne bien 17).

La difficulté résidera dans le fait de montrer que si p n'appartient pas à l'ensemble en question, alors le PGCD est égale à 1.
Un moyen d'y arriver serait de considérer les cas possible pour la forme de p à savoir:
p=17k+q
avec q allant de 0 à 16 et là, tu as tous les cas possible.
Avec un peu de temps et de calcul, je viens de montrer que pour q=0, le PGCD était bien 1.
Je pense que la démarche est viable mais un peu longue, il y a sans doute un autre moyen d'aboutir plus rapidement mais à l'instant t, je ne l'ai pas.

Bon courage!

-Si la (division euclidienne) de a par b donne l'égalité: a=bq+r alors PGCD(a,b)=PGCD(b,r)
lorsqu'on a démontré cette propriété on n'a pas utilisé le fait que 0<q<p
notre prof a précisé qu'il s'agit juste de la forme (a=bq+r et aucune autre condition ) , donc c'est pas une condition nécessaire le fait que 0<q<p .. on a utilisé 0<q<p juste pour comprendre l'algorithme d’Euclide
pour 3 )
d / 9p+4 et d/ 2p-1
donc d / 2(9p+4)-9(2p-1)
d/ 17
d=1 ou d=17
ensuite si p s'écrit sous cette forme, p=17m+9 , m entier naturel
alors PGCD(9p+4,2p-1)=17
j'ai vérifié cela avec 9p+4
9(17m+9)+4 = 17(9m+5) donc ça reste valable !!
et puisque le PGCD et soit 1 soit 17
donc PGCD(9p+4,2p-1)=17 si P=17m+9
et PGCD(9p+4,2p-1)=1 si p est différent de 17m+9

Excellent pour les valeurs du pgcd! Ma démarche était trop longue pour être viable.
Ayant les possibilités pour le pgcd, il ne reste plus qu'à montrer que cela fonctionne ce que tu as fais.

Sinon, ton prof a choisi une propriété intermédiaire mais je doute de l'intérêt d'un tel choix vu que sa démonstration reposera sur un raisonnement similaire voire même sur la propriété minimaliste de la soustraction. Surtout que cette propriété est donnée en 3 ème ce qui lui évite d'en donner une supplémentaire. Mais elle généralisé sans restreindre au cas de la division euclidienne ce qui permet d'avoir un cas général sans condition sur les nombre entier utilisés.

Excellent travail!