Caractérisation du pgcd
dans Arithmétique
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.
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.
Réponses
-
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. -
Je comprends...je m'y appliquerai. Peut-être pourriez vous répondre à ma question ?
-
Tu n'as pas vu mon message ?
-
@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. -
@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. -
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. -
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. -
L'initialisation n'est pas nécessaire en récurrence forte ?
-
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 2
2 Invités