Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
256 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Caractérisation du pgcd

Envoyé par jp59 
Caractérisation du pgcd
09 mai 2020, 21:23
Bonjour

Soient deux entiers naturels a et b. Notons D(a) l'ensemble des diviseurs de a.
On a D(a) inter D(b)=D(pgcd(a,b))
Pour prouver cette caractérisation, on utilise une récurrence forte sur b.

Je ne comprends pas cette preuve notamment dans l'hérédité, le rôle des lettres b et r.
Si l'hypothèse Hb est celle annoncée au début de la récurrence alors ne devrait-on pas avoir dans la récurrence D(a) inter D(r) = D(pgcd(a,r)) ?
Où est mon erreur ?
Merci.



Modifié 1 fois. Dernière modification le 09/05/2020 22:11 par AD.


Re: Caractérisation du pgcd
09 mai 2020, 22:20
avatar
Bonjour,

Avec 323 messages il est grand temps d’écrire lisiblement. Encadre par deux signes $ devant et derrière les formules. Passe ton curseur sur les formules des messages pour lire leur écriture.
Re: Caractérisation du pgcd
09 mai 2020, 22:30
@YvesM : Très franchement, ce genre d'écriture est lisible.

@jp59 : Bah on applique le "quel que soit $a$" de l'hypothèse de récurrence à l'entier $b$, aucun problème.
Re: Caractérisation du pgcd
09 mai 2020, 22:32
Je comprends...je m'y appliquerai. Peut-être pourriez vous répondre à ma question ?
Re: Caractérisation du pgcd
09 mai 2020, 22:40
Tu n'as pas vu mon message ?
Re: Caractérisation du pgcd
09 mai 2020, 23:12
@Poirot : je ne l'avais pas vu au moment où j'avais publié ce message. Merci pour votre réponse.
GG
Re: Caractérisation du pgcd
10 mai 2020, 07:50
@jp59, à noter que le pgcd de $a$ et $b$ est par définition la borne inférieure de $\{a, b\}$ pour la relation de divisibilité. Or dans n'importe que ensemble ordonné, dire que c est la borne inférieure de $a$ et $b$, c'est trivialement équivalent à dire que $\{ x \leqslant a \} \cap \{ x \leqslant b \} = \{ x \leqslant c \}$.

P.S. Non AD ! prière de ne pas faire des correction intempestives ! Merci.



Modifié 2 fois. Dernière modification le 11/05/2020 07:00 par GG.
Re: Caractérisation du pgcd
10 mai 2020, 20:45
@GG merci pour ce point de vue efficace!

@Poirot
La preuve de la photo me résiste toujours . Dans l'hypothèse de récurrence même si on a "quel que soit a", l'indice du H est bien b et non a. Or dans l'hérédité il est écrit Hr et le a n'apparaît pas au moment où l'hypothèse de récurrence est utilisée.



Modifié 1 fois. Dernière modification le 10/05/2020 20:45 par jp59.
Re: Caractérisation du pgcd
10 mai 2020, 20:53
Ce que certains appellent "récurrence complète":
Si H(0) est vrai
Si (quel que soit r<b, H(r)) implique H(b)
Alors H(b) est vrai pour tout entier naturel b.

Cordialement.
GG
Re: Caractérisation du pgcd
11 mai 2020, 06:56
@gerard0, comme martelé sur le forum par certains depuis des éons, pas besoin de l'hypothèse sur 0 ! smiling smiley
Re: Caractérisation du pgcd
11 mai 2020, 09:46
Bien sûr !

Mais la preuve donnée par Jp59 le fait. Je suis resté dans son cadre. Et comme je n'ai regardé que l'aspect logique, je n'ai pas regardé si on pouvait la faire fonctionner en supprimant le paragraphe "supposons b=0" et en commençant le suivant par "soit $b \in \mathbb N$.
D'ailleurs, quid de "la division euclidienne de a par b" quand b est nul ?

Donc le "pas besoin de l'hypothèse sur 0" n'est vrai que si la preuve générale traite aussi le cas 0.

Cordialement.
Re: Caractérisation du pgcd
11 mai 2020, 13:53
L'initialisation n'est pas nécessaire en récurrence forte ?
Re: Caractérisation du pgcd
11 mai 2020, 16:55
Non, si on peut bien prouver la propriété $\forall n\in\mathbb N\ (\forall p\in [1..n]\ P(p)\ ) \Rightarrow P(n)$; car cette propriété est automatiquement vraie pour n=0 (il n'y a pas de p<n).

Cordialement.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 150 602, Messages: 1 528 153, Utilisateurs: 28 082.
Notre dernier utilisateur inscrit Bouvier Denys.


Ce forum
Discussions: 5 654, Messages: 68 340.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page