Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

PGCD de deux nombres

Posté par
Aldebarran
15-04-21 à 08:13

Bonjour,
Voici un autre exercice sur le PGCD de deux nombres. J'ai besoin de revoir mes réponses, en particulier pour la 2.b. et la 4.
Voici l'énoncé :

Soit (u_n) la suite définie pour tout entier naturel n par u(0)=14 et u(n+1)=5u_n + 6.
1.a. Calculer u_1 et u_2.
b. Pour tout entier naturel n, que peut-on conjecturer pour le PGCD de u_n et u(n+1) ?
2. Démontrer par récurrence que pour tout entier naturel n, u_n est divisible par 2.
3.a. Soit n un entier relatif. Démontrer que n≡0[3] ⇔ 5n≡0[3].
b. Démontrer par récurrence, et à l'aide du résultat précédent, que pour tout entier naturel n, u_n n'est pas divisible par 3.
4. A l'aide des résultats précédents, démontrer la conjecture faite à la première question.

Voici mes réponses :

1.a. u_1 = 5u_0 + 6 = 5*14 + 6 = 76
u_2 = 5u_1 + 6 = 5*76 + 6 = 386

b. D(u_0) = {1 ; 2 ; 7 ; 14} or 14 ∤ u_1 et 7 ∤ u_1 donc on peut conjecturer que PGCD(u_n ; u(n+1)) = 1 ou 2.

2. Pour tout n ∈ ℕ, on note P(n) la propriété u_n≡0[2]
Initialisation : pour n = 0, u_0 = 14 et 14≡0[2] donc P(0) est vraie.
Hérédité : On suppose qu'il existe un nombre n ∈ ℕ tel que P(n) soit vraie.
u_n≡0[2] d'après l'hypothèse de récurrence
5u_n≡5*0[2]
5u_n + 6≡5*0 + 0[2] car 6≡0[2]
5u_n + 6≡0[2]
u(n+1)≡0[2] ainsi P(n+1) est vraie.
Conclusion : P(0) est vraie et la propriété est héréditaire donc P(n) est vraie pour tout n ∈ ℕ.

3.a. Si n≡0[3] alors 5n≡5*0[3] donc 5n≡0[3]

b. Pour tout n ∈ ℕ, on note Q(n) la propriété u_n≡0[3]
Initialisation : pour n = 0, u_0 = 14 et 14 ≠ 0[3] donc u_0 ≠ 0[3] donc Q_0 est fausse.
Ainsi la propriété est fausse.

4. D'après 2. u_n≡0[2] or 1≠0[2] et 2≡0[2] donc PGCD(u_n ; u(n+1)) = 2
Pour celle-ci je n'ai pas utilisé le fait que u_n ≠ 0[3] alors que c'était demandé dans la consigne...

J'espère que quelqu'un saura m'indiquer où j'ai pu me tromper, merci !

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 09:04

salut

2/ c'est bien compliqué de travailler avec des congruences :

si u_n est pair alors 5u_n est pair et en ajoutant 6 (qui est pair) c'est fini (toute combinaison de deux multiples de 2 est multiple de 2)

3b/ : insuffisant : utilise la relation de récurrence

de même cette relation de récurrence u(n + 1) = 5u_n + 6 équivaut à u(n + 1) - 5u_n = 6

donc toujours avec la propriété de base : si d divise a et b alors il divise toute combinaison linéaire de a et b tu en déduis que le pgcd de u(n + 1) et u_n divise 6

...

Posté par
Aldebarran
re : PGCD de deux nombres 15-04-21 à 09:40

2. D'accord, mais comment le rédiger dans un raisonnement par récurrence ?
Ce que j'ai fait est faux ?

3.b. Mais pourtant si l'initialisation est fausse, alors la propriété est fausse ;

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 09:45

ce n'est pas faux mais c'est lourd de travailler avec des congruences alors qu'en français c'est plié en deux lignes ...

ce n'est pas parce que la propriété est fausse au rang 0 qu'elle ne sera pas vraie par la suite ...

une propriété peut être héréditaire bien que fausse ...

et la propriété à montrer est : u_n n'est pas multiple de 3 !!

qui est vraie au rang 0

Posté par
Aldebarran
re : PGCD de deux nombres 15-04-21 à 10:05

3.b. Je ne vois pas comment je peux le mettre dans un raisonnement par récurrence...

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 10:16

soit P(n) la proposition "u_n n'est pas multiple d e3"

u_0 = 14 donc P(0) est vraie

u_{n + 1} = 5u_n + 6  donc  u_{n + 1} \equiv 5u_n
puis utiliser 3a/ ... et l'hypothèse de récurrence ...

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 10:17

carpediem @ 15-04-2021 à 10:16

soit P(n) la proposition "u_n n'est pas multiple d e3"

u_0 = 14 donc P(0) est vraie

u_{n + 1} = 5u_n + 6  donc  u_{n + 1} \equiv 5u_n  \red [3]
puis utiliser 3a/ ... et l'hypothèse de récurrence ...

Posté par
Aldebarran
re : PGCD de deux nombres 15-04-21 à 11:50

Je tombe sur u_n+1≡0[3]... Comment je dois utiliser le 3.a. ?

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 12:57

déjà pour 3a/ tu n'as montré qu'un sens et pas l'équivalence ... je te laisse réfléchir

en admettant 3a/ : n \equiv 0  [3] \iff 5n \equiv 0 [3] est donc équivalant à n \not \equiv 0  [3] \iff 5n \not \equiv 0  [3]

Posté par
Aldebarran
re : PGCD de deux nombres 15-04-21 à 18:58

Je n'arrive pas à voir où je dois arriver avec cette méthode ;
si la propriété est définie sur ℕ et que l'on trouve un contre-exemple, alors cette propriété devrait être fausse...

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 19:05

la propriété à démontrer est : u_n n'est pas multiple de 3 !!

et cette propriété est vraie au rang 0 puisque u_0 = 14

il faut maintenant montrer l'hérédité en utilisant 3a/ ...

Posté par
Aldebarran
re : PGCD de deux nombres 15-04-21 à 19:27

Peut-on dire que :
u_n  ≠  0[3]
5u_n ≠ 0[3] d'après 3.a.
5u_n ≠ 0[3]
u(n+1) ≠ 0[3] ainsi P(n+1) est vraie.

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 21:16

c'est l'idée générale ... à rédiger convenablement ?

carpediem @ 15-04-2021 à 10:17

carpediem @ 15-04-2021 à 10:16

soit P(n) la proposition "u_n n'est pas multiple de 3"

u_0 = 14 donc P(0) est vraie

u_{n + 1} = 5u_n + 6  donc  u_{n + 1} \equiv 5u_n  \red [3]
puis utiliser 3a/ ... et l'hypothèse de récurrence ...

Posté par
Aldebarran
re : PGCD de deux nombres 15-04-21 à 21:34

• u(n+1) = 5u_n + 6 donc u(n+1) ≡ 5u_n [3]
• u_n ≠ 0[3] d'après l'hypothèse de récurrence
    5u_n ≠ 0[3] d'après 3.a.
Ainsi u(n+1) ≠ 0[3] donc P(n+1) est vraie.

Posté par
carpediem
re : PGCD de deux nombres 15-04-21 à 22:00

et bien voila ... qui est mieux ...

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 08:54

Merci pour votre aide !
Pour la 4. ma réponse est-elle à revoir ?

Posté par
Sylvieg Moderateur
re : PGCD de deux nombres 16-04-21 à 09:06

Bonjour,
Je répond en l'absence de carpediem qui pourra compléter quand il reviendra.
Tu sais que 2 divise un et un+1.
Ça ne suffit pas pour en déduire que le PGCD de un et un+1 est égal à 2.

2 divise 2020 et 2030 alors que le PGCD de 2020 et 2030 n'est pas égal à 2.

Il faut utiliser 3)b) et la relation de récurrence entre un et un+1.

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 10:14

Faut-il commencer ainsi :
2/u_n d'après 2, et 3 ne divise pas u_n d'après 3.b.
u(n+1) = 5u_n + 6
2/5u_n et D(5) = {1 ; 5} donc D(5u_n)={1 ; 2 ; 5}
D(6) = {1 ; 2 ; 3 ; 6}
→ le seul diviseur commun de 5u_n et 6 est 2
ainsi PGCD(u_n ; u(n+1)) = 2

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 10:24

que c'est alambiqué !!

carpediem @ 15-04-2021 à 09:04

de même cette relation de récurrence u(n + 1) = 5u_n + 6 équivaut à u(n + 1) - 5u_n = 6

donc toujours avec la propriété de base : si d divise a et b alors il divise toute combinaison linéaire de a et b tu en déduis que le pgcd de u(n + 1) et u_n divise 6
donc le pgcd de u_n et u(n + 1) appartient à l'ensemble ... ?

or ...

donc ...

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 10:41

PGCD(u_n ; u(n+1)) appartient à {1 ; 2 ; 3 ; 6}
or 3 ne divise pas u_n d'après 3.b.
et 2 divise u_n d'après 2.
donc PGCD(u_n ; u(n+1)) = 2

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 10:45

Aldebarran @ 16-04-2021 à 10:41

PGCD(u_n ; u(n+1)) appartient à {1 ; 2 ; 3 ; 6}
or 3 ne divise pas u_n d'après 3.b. donc 6 non plus !! (et pourquoi ?)
et 2 divise u_n d'après 2.
donc PGCD(u_n ; u(n+1)) = 2

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 10:49

PGCD(u_n ; u(n+1)) appartient à {1 ; 2 ; 3 ; 6}
or d'après 3.b, 3 ne divise pas u_n, donc 6 ne divise pas u_n non plus (car 6 est un multiple de 3).
et d'après 2., 2 divise u_n
donc PGCD(u_n ; u(n+1)) = 2

Oups j'y avais pensé, mais je ne l'ai pas écrit...

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 10:51

voila c'est mieux car c'est complet !!

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 11:01

Si je rédige :
u_n+1 = 5u_n + 6 ⇔ u_n+1 - 5u_n = 6
(faut-il énoncer la propriété ?)
On en déduit que le PGCD(u_n , u(n+1)) divise 6
donc PGCD(u_n ; u(n+1)) appartient à {1 ; 2 ; 3 ; 6}
or d'après 3.b, 3 ne divise pas u_n, donc 6 ne divise pas u_n non plus (car 6 est un multiple de 3).
et d'après 2., 2 divise u_n
donc PGCD(u_n ; u(n+1)) = 2

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 12:02

oui c'est préférable et une ligne c'est pas grand chose pour être très "propre" !! (donc précis)

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 12:08

D'accord, je rajoute :
si d divise a et b alors il divise toute combinaison linéaire de a et b
et puis j'écris :
on en déduit que le PGCD(u_n , u(n+1)) divise 6

Vous m'aviez indiqué que la réponse au 3.a. était incomplète, que dois-je ajouter ?

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 12:43

je ne vois pas de quoi tu parles ...

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 12:48

Au message du 15-04-21 à 12:57, vous aviez précisé que je n'avais fait qu'un sens de la démonstration

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 13:04

oui tu n'as montré que le sens : si n = 0  [5]alors 5n = 0  [5]

il faut montrer l'autre sens ...

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 13:17

L'autre sens, c'est ce qu'on a utilisé au 3.b. ?

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 13:36

ça n'a rien à voir !!

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 14:53

Il faut montrer que si 5n = 0[3] alors n = 0[3] ?

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 15:06

oui ...

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 16:59

Et bien 5≡2[3] et 5n≡0[3] donc 5n≡2*0[3] donc n≡0[3]

Est-ce possible de faire la démonstration en une fois avec un tableau de congruences ?

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 17:08

voila enfin

tout comme tu es passé de n = 0   [3] à 5n = 0  [3] en multipliant par 5

il suffit de multiplier par 2 pour passer de 5n = 0 [3] à n = 0  [3]

puisque 2 * 5 = 1  [3]

je te déconseille un tableau de congruence pour travailler les propriétés sur les congruences et de plus qui est inutile ici ...

Posté par
Aldebarran
re : PGCD de deux nombres 16-04-21 à 18:12

D'accord ; puis-je rédiger rédiger ainsi :
Si on a n≡0[3] alors 5n≡5*0[3] donc 5n≡0[3]
Si on a 5n≡0[3] alors 5n≡2*0[3] (car 5≡2[3]) donc n≡0[3]

Posté par
carpediem
re : PGCD de deux nombres 16-04-21 à 18:34

Aldebarran @ 16-04-2021 à 18:12

D'accord ; puis-je rédiger rédiger ainsi :
Si on a n≡0[3] alors 5n≡5*0[3] donc 5n≡0[3]  peux-tu traduire quelle opération mathématique tu fais ?
Si on a 5n≡0[3] alors 5n≡2*0[3] (car 5≡2[3]) donc n≡0[3]  fais-tu la même chose ici ?

je t'invite à relire mon précédent post ...

Posté par
Aldebarran
re : PGCD de deux nombres 17-04-21 à 10:52

J'ai multiplié par 5, puis multiplié par 2... Mais je l'ai déjà écrit, faut-il quand même le rajouter sur chaque ligne ?

Posté par
carpediem
re : PGCD de deux nombres 17-04-21 à 11:09

non !!

tu as multiplié par 5 mais tu n'as pas multiplié par 2 !!

Posté par
Aldebarran
re : PGCD de deux nombres 17-04-21 à 18:53

Mais pour 5n≡2*0[3] il y a bien une multiplication par 2...

Posté par
carpediem
re : PGCD de deux nombres 17-04-21 à 19:04

certes ! mais bon écrire que 0 = 2 * 0 ça ne fait pas avancer le schmilblick !!

Posté par
Sylvieg Moderateur
re : PGCD de deux nombres 18-04-21 à 17:37

Bonjour,
Aldebarran semble s'être découragé

Il s'agit de démontrer \; n 0 \; [3] \; \; 5n 0 \; [3] .
Plusieurs méthodes sont possibles :

1) Par double implication et multiplication
a) Si \; n 0 \; [3] \; alors \; 5n 0 \; [3] \; car 50 = 0.
b) si \; 5n 0 \; [3] \; alors \; 25n 20 \; [3] .
Or \; 25 1 \; [3] \; ; donc \; n 0 \; [3] .
( Cf message de carpediem du 16 à 17h08. Mais il faut avoir l'idée de multiplier par 2 )

2) Encore par double implication, en traduisant les congruences par des divisibilités :
a) Si \; 3 divise n \; alors \; 3 divise 5n.
b) Si \; 3 divise 5n \; alors \; 3 divise n \;.
D'après Gauss, car 3 est premier avec 5.

3) Par disjonction des cas ( ce qui revient à un tableau de congruences modulo 3 ).
Trois cas :
Si \; n 0 \; [3] \; alors \; 5n 0 \; [3] .
Si \; n 1 \; [3] \; alors \; 5n 5 \; [3] \; ; donc \; 5n 2 \; [3] .
Si \; n 2 \; [3] \; alors \; 5n 10 \; [3] \; ; donc \; 5n 1 \; [3] .
Le seul cas où \; 5n 0 \; [3] \; est \; n 0 \; [3] .
L'équivalence est donc démontrée.

Posté par
carpediem
re : PGCD de deux nombres 18-04-21 à 19:42

il y a surtout qu'il n'applique pas proprement les règles sur les égalités vues au collège et rappelées lorsqu'on voit la congruence :

si a = b et c = d alors ac = bd

cas particulier : si a = b et c = c alors ac = bc

et ces règles sont toujours valables (et donc rappelées) avec des congruences

autre façon de le dire : on ne change pas une égalité en multipliant les deux membres de cette égalité par un même nombre

Aldebarran @ 16-04-2021 à 18:12

Si on a n≡0[3] alors 5n≡5*0[3] donc 5n≡0[3]  ici il y a bien multiplication des deux membres par 5
Si on a 5n≡0[3] alors 5n≡2*0[3] (car 5≡2[3]) donc n≡0[3] ici il n'y a pas multiplication des deux membres par 2
et pire que tout Aldebarran effectue une division sans la justifier

or jamais dans un cours sur les congruences on ne parle de division (du moins dans ce genre de situation)

pour en revenir à R par exemple :

2x = 3 \iff \dfrac 1 2 \times 2x = \dfrac 1 2 \times 3 \iff x = \dfrac 3 2

je ne divise pas par 2 (même si dans R je sais et surtout peux le faire) mais je multiplie par 1/2

et le résultat final est la division de 3 par 2 tout comme le produit en croix n'est que le résultat d'une opération mathématique très précise et valide



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !