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
112 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
il y a sept semaines
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.



Edité 1 fois. La dernière correction date de il y a sept semaines et a été effectuée par AD.


Re: Caractérisation du pgcd
il y a sept semaines
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
il y a sept semaines
@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
il y a sept semaines
Je comprends...je m'y appliquerai. Peut-être pourriez vous répondre à ma question ?
Re: Caractérisation du pgcd
il y a sept semaines
Tu n'as pas vu mon message ?
Re: Caractérisation du pgcd
il y a sept semaines
@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
il y a sept semaines
@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.



Edité 2 fois. La dernière correction date de il y a sept semaines et a été effectuée par GG.
Re: Caractérisation du pgcd
il y a sept semaines
@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.



Edité 1 fois. La dernière correction date de il y a sept semaines et a été effectuée par jp59.
Re: Caractérisation du pgcd
il y a sept semaines
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
il y a sept semaines
@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
il y a sept semaines
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
il y a sept semaines
L'initialisation n'est pas nécessaire en récurrence forte ?
Re: Caractérisation du pgcd
il y a sept semaines
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: 143 081, Messages: 1 412 082, Utilisateurs: 26 427.
Notre dernier utilisateur inscrit YunVln.


Ce forum
Discussions: 5 352, Messages: 65 048.

 

 
©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