Exercice sur PGCD

[Turn]

Bonjour bonjour voilà mon exo :

I) 1) Soient x,a,p,q quatres entiers naturels non nuls tels que p et q soient premiers entre eux :

Démontrer que :
x congru à a modulo p et x congru à a modulo q x congru à a modulo pq.

2) Résoudre dans Z l'équation 3x congru à 1 modulo 14.

3) Résoudre dans Z l'équation 5x congru à 8 modulo 17.

4) Déduire des questions précédentes les solutions dans Z du système
3x congru à 1 modulo 14
5x congru à 8 modulo 17

II) 1) Calculer le PGCD de 4^5-1 et 4^6-1.

Soit u la suite numérique définie par : U(o)=0, U(1)=1 et pour tout entier naturel n, U(n+2) = 5(n+1) - 4U(n).

2) Calculer U2, U3 et U4.

3)a) Montrer par récurrence que la suite u vérifie, pour tout entier naturel, U(n+1) = 4U(n) + 1.

b) Démontrer que pour tout entier naturel n, U(n) est un entier naturel.

c) En déduire pour tout entier naturel n, le PGCD de U(n) et U(n+1)

[CENTER]------------------------------------------[/CENTER]

Pour la 1 j'ai dis qu'il existe K et K' tel que x-a=pK et x-a=qK' donc pK=qK' donc p|qK' or p et q sont premiers entre eux. donc d'après le théorème de Gauss, p|K' soit pq|K'q soit pq|x-a soit x congru à a modulo pq.
Ai - je raison ou faut faire autrement ??

Pour la 2 j'ai résolu 3x-14b = 1 après j'ai trouvé x = 5K+1 mais je sais que c'est faut donc je voudrais savoir comment faire pareil pour la 3 et 4.

Pour la 2ème partie le pgcd j'ai trouvé 3 et après j'ai calculer U2, U3 et U4.

Après par récurrence j'ai dis que U1=1 et que U1=U(0+1)= 4U(0)+1=1 et donc on a bien u(n+1)= 4Un+1. Après on suppose que u(n+1)= 4Un+1 et on démontre que U(n+2) = 5(n+1) - 4U(n).
U(n+1) = 4Un + 1 soit 5U(n+1) = 20 Un + 5 soit U(n+2) = 16Un + 5
Or U(n+1) = 4Un+1 donc 5U(n+1) = 20Un + 5 donc 5U(n+1) - 4 Un = 16 Un + 5 = U(n+2)

C'est bon ???

Ensuite pour le reste je n'arrive pas meme si je sais que le pgcd = 1 mais faut le déduire de la 3)b) que j'arrive pas à faire ..

Merci d'avance pour votre aide !! :zen:

[becirj]

Bonsoir
Pour la question 1 d'accord
2. Il faut effectivement résoudre 3x-14b=1
Il faut commencer par trouver une solution évidente : on a x=5 et b=1.
L'équation équivaut à

14 divise 3(x -5) et 14 est premier avec 3 donc 14 divise x-5.
Par conséquent x=14k+5

[becirj]

La démonstration de la récurrence est un peu confuse : on ne démontre pas que car c'est la définition de la suite, mais de cette définition et de l'hypothèse de récurrence, on déduit que
D'autre part,
On a donc

b) Une récurrence toute simple :
est un entier naturel ;
Supposons que, au rang n , est un entier naturel.
Alors est un entier naturel soit est un entier naturel.

c) et théorème de Bézout.

[Turn]

Pour la b) faut montrer que U(n) est un entier naturel et toi tu supposes que U(n) en est un et tu conclus que U(n+1) est un entier naturel mais on répond pas à la question là ??

Pour la partie I, j'ai compris mais pour la 3eme sa fait 5x-17c=8 donc on arrive à (5x-17c)/8=1 !! On peut résoudre cela mais sa va faire un peu lourd nan ??


Pour la question c tu me dis d'utiliser Bezout d'accord mais la question commence par en déduire donc faut pa utiliser la question d'avant ???

[becirj]

b) C'est une démonstration par récurrence : il y a l'amorce et la justification que la propriété est héréditaire.

2.c) Même méthode que pour la question b)
Il faut résoudre 5x-8=17 c
5x-17c=8 a une solution évidente x=5 et c=1. On se ramène à
5x-17c=5x5-17x1
5(x-5)=17(c-1)
17 divise 5(x-5) et 17 est premier avec 5 donc 17 divise x-5.
On a donc pour solutions : x=17k+5 avec

Le "en déduire" concerne à la fois les questions a et b.
le fait d'avoir des entiers justifie que l'on en cherche le PGCD.
La relation montre par application du théorème de Bézout qu'il s'agit de nombres premiers entre eux.

[Turn]

Hum je croyais qu'on pouvais appliquer la méthode que quand c'était égal à 1 pour la 3 de la partie I mais en faite nan bon ba c'est cool alors merci :++: !

Sinon pour le reste, merci ! :++:

[Turn]

Pour la question 4 de la partie I je voudrais savoir si il faut passer de 3x congru à 1 modulo 14 à 5x congru à 8 modulo 14 ???

[becirj]

Bonsoir

C'est un système que tu dois résoudre. D'après les questions précédentes on doit avoir à la fois :
J'ai utilisé car il faut donner des valeurs différentes à l'entier k pour vérifier simultanément les 2 égalités.

On doit avoir soit
17 divise et 17 est premier avec 14 donc 17 divise , on a donc .
En reportant dans l'expression de x :

les solutions du système sont les entiers de la forme : 238 k +5 avec k élément de .

[Turn]

Ptin en faite c'est tout con :mur: :mur: chui vraiment dans une mauvaise posture pour le bac et l'exercice de spécialité !! :--: :--: :cry: :cry: !!

Merci quand on voit la solution c'est tout de suite plus facile ^^ !! Merci !

[becirj]

Pas de découragement, on retrouve toujours un peu le même type de raisonnement. Tu as encore le temps de t'entraîner avant le Bac.

Bon courage.