Sur le pgcd et le ppcm

OShine
Modifié (June 2022) dans Arithmétique
Bonjour
Après les démonstrations lourdes et fastidieuses de mon livre de prépa, j'ai trouvé les raisonnements de ce livre d'arithmétique succincts, clairs et élégants sur ce livre, mais malheureusement cette propriété n'est pas démontrée.
Pour les valuations ça m'a l'air évident si on écrit les décompositions en facteurs premiers.
Pour le PGCD et le PPCM est-ce facile à montrer ?

Réponses

  • Merci mais il y a peut-être une méthode différente de celle du livre de prépa ?


  • raoul.S
    Modifié (June 2022)
    C'est effectivement facile à montrer. Fais-le.

    Pour le pgcd : 
    1) tu montres que $\prod_{p\in \mathcal{P}}p^{\min{v_p(a), v_p(b)}}$ est un diviseur commun de $a$ et $b$ ;
    2) montre que c'est le plus grand dans le sens suivant : si $d\mid a$ et $d\mid b$ alors $d\mid \prod_{p\in \mathcal{P}}p^{\min{v_p(a), v_p(b)}}$.
  • OShine
    Modifié (June 2022)
    Merci ! 
    Montrons que $\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) }$ est un diviseur commun à $a$ et $b$.
    On sait que $a=\displaystyle\prod_{p \in \mathcal P} p^{v_p(a)}$ et $b=\displaystyle\prod_{p \in \mathcal P} p^{v_p(b)}$. Deux cas se présentent : 
    • Si $v_p(a) \leq v_p (b)$ alors $\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } = \displaystyle\prod_{p \in \mathcal P} p^{ v_p(a) } =a$ donc $\boxed{\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } \mid a}$
    • Si $v_p(b) \leq v_p(a)$ alors  $\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } = \displaystyle\prod_{p \in \mathcal P} p^{ v_p(b) } =b$ donc $\boxed{\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } \mid b}$
    Supposons que :  $d \mid a $ et $d \mid b$ on peut écrire $d= \displaystyle\prod_{p \in \mathcal P } p^{v_p(d) }$ avec $0 \leq v_p(d) \leq v_p(a)$ et  $d= \displaystyle\prod_{p \in \mathcal P} p^{v_p(d)}$ avec $0 \leq v_p(d )\leq v_p(b)$
    Ainsi $\boxed{v_p(d) \leq \min (v_p (a),v_p(b)) }$ et les nombres premiers qui apparaissent dans la décompositions de $d$ sont des nombres qui appartiennent à l'ensemble des nombres premiers qui apparaissent dans la décomposition en facteurs premiers de $a$ et $b$.
    Distinguons deux cas : 
    • Si $v_p(a) \leq v_p (b)$ alors $\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } =a$ et d'après la remarque plus haut, $d \mid a$.
    • Si $v_p(b) \leq v_p (a)$ alors $\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } =b$ et d'après la remarque plus haut, $d \mid b$.
  • raoul.S
    Modifié (June 2022)

    🥶


    L'exercice suivant consiste à corriger ta preuve ci-dessus : on peut commencer par chercher l'erreur située à la quatrième ligne : 
    Si $v_p(a) \leq v_p (b)$ alors $\displaystyle\prod_{p \in \mathcal P} p^{ \min ( v_p (a),v_p(b) ) } = \prod_{p \in \mathcal P} p^{ v_p(a) } =a$.
  • lourrran
    Modifié (June 2022)
    Attention aux quantificateurs.
    Les 2 dernières lignes pourraient être : 
    Si pour tout p, etc etc
    Et malheureusement, les lignes au  dessus travaillent sur un p précis.

    C'est donc évidemment faux.  Essaie de voir ce que donne tout ça avec a=80 et b=250.
    Mais, tu t'es bien amusé, tu as fait du Latex.  Serais-tu un fétichiste du latex ?

    De manière générale, il y a un truc qui est TOUJOURS faux (sauf contre-exemples alambiqués, bâtis sur mesure pour te perturber)
    C'est quand on a  :  si $Relation(a,b,p)$ alors  $\Sigma_p = $...
    $p$ est une variable non-muette dans le prédicat n°1 alors que p est une variable muette dans le 2ème prédicat : ça ne peut pas être correct.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • OShine
    Modifié (June 2022)
    J'ai compris l'erreur, $v_p(a)  \leq v_p(b)$ dépend de l'entier $p$, donc ça ne fonctionne pas.

    On a $\forall p \in \mathcal P ,\  \min (v_p(a),v_p(b) ) \leq v_p (a)$ donc  $ \displaystyle\prod_{p \in \mathcal P} p^{\min (v_p(a),v_p(b) ) } \mid a$.

    Et $\forall p \in \mathcal P, \  \min (v_p(a),v_p(b) ) \leq v_p (b)$ donc  $ \displaystyle\prod_{p \in \mathcal P} p^{\min (v_p(a),v_p(b) ) } \mid b$.

    Donc $ \displaystyle\prod_{p \in \mathcal P} p^{\min (v_p(a),v_p(b) ) } \mid a$ et  $ \displaystyle\prod_{p \in \mathcal P} p^{\min (v_p(a),v_p(b) ) } \mid b$
  • gerard0
    Modifié (June 2022)
    [édit : Une grossière erreur, attribuez-la à l'âge (soixante ans après), ou à la chaleur et le mélange avec le ppcm]
    C'est amusant, on apprenait ça en cinquième autrefois, évidemment sans l'arsenal des notations algébriques; mais on apprenait qu'une fois trouvé les décompositions de deux nombres entiers, leur pgcd est le produit des facteurs premiers communs élevé à la plus grande petite puissance figurant dans l'un ou l'autre des deux entiers. Et on apprenait par cœur une phrase de ce genre.
  • Exact ! J'ai bien appris ça en 5e.
  • Moi quand j'étais petit c'était en quatrième (1958).
  • GaBuZoMeu
    Modifié (June 2022)
    leur pgcd est le produit des facteurs premiers communs élevé à la plus grande puissance figurant dans l'un ou l'autre des deux entiers.

    Bonsoir gerard0,
    Tu es sûr ? :)

  • @gerard0 : Pas terrible ton slogan de la classe de 5ème d'antan ;)
  • OShine
    Modifié (June 2022)
    Ça contredit ma formule encadrée en rouge  :#
  • C'est un truc assez lourd pour un truc trivial...
  • @Amédé je suis d'accord c'est pour ça que j'aime ce livre, il ne démontre pas les résultats triviaux qui sont lourds à rédiger et qui se comprennent facilement sur des exemples concrets.

    Par contre il démontre la formule de Legendre. 
  • Dans ton message https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2364126/#Comment_2364126, si tu mets ta belle formule pour $a$, et tu ajoutes : et de même pour $b$
    C'est aussi bien.
    Et ça fait des économies de latex. Faut préserver les ressources naturelles.

    Ouawwww , la formule de Legendre.  Le top niveau.
    Raoul S. t'avait proposé une démonstration en 2 étapes. La 2ème étape, tu comptes la faire, mais après avoir démontré la formule de Legendre, c'est ça ?


    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • gerard0
    Modifié (June 2022)
    Merci GBZM de m'avoir permis de rectifier !
    Il y a eu sans doute dans ma tête un mélange avec l'idée de mettre la plus grande puissance possible qui divise les deux (idée de l'explication qu'on nous donnait - on ne raisonnait pas en arithmétique à ce niveau).
    Cordialement.
  • @gerard0 : moi, il me semble bien que c'était en cm1/cm2 dans une école communale en Finistère. Suis-je devenu si vieux?
  • Beaucoup de bretons me disaient « ho ! la Bretagne, c’est pas La France !!! » jadis. 
  • @Dom : :) je crois qu'on a toujours pris du retard par rapport aux "réformes"(on est un peu loin...), un retard salutaire.
  • xax
    xax
    Modifié (August 2022)
    Pour ma part j'ai bénéficié des programmes qui ont accompagné la loi Haby (instaurant le collège unique) qui étaient d'un niveau assez élevé, on y voyait en 5ème le PPCM et le PGCD de plusieurs entiers naturels (on voyait aussi sommairement les classes d'un ensemble, les partitions, les relations d'équivalence). Probablement les meilleurs programmes jamais écrits, merci M. Haby !
    "J'appelle bourgeois quiconque pense bassement." Gustave Flaubert
  • OShine, trouve le PGCD et le PPCM de 60 et de 84 en utilisant la décomposition en facteurs premiers.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Jaymz
    Modifié (August 2022)
    C'est la définition que je donne aux 3ème (leur pgcd est le produit des facteurs premiers communs élevé à la plus grande [petite ?] puissance figurant dans l'un ou l'autre des deux entiers) car comme tout le monde le sait, le pgcd et le ppcm sont au programme de collège, hein @Dom :)
  • Bonjour, merci Jaymz de le rappeler et rappelons quand même que OShine, avec tout le respect que je lui dois, n'est ni représentatif des profs de maths ni représentatif des élèves, il a moins de capacité en maths que l'immense majorité des lycéens que je récupérè tous les ans alors que les miens n'ont même pas vocation à faire des maths.
    Ils savent tous que :
    - pour simplifier une fraction, on divise en haut et en bas par le pgcd
    - pour additionner deux fractions et donc mettre au même dénominateur, il faut trouver le ppcm
    Est-ce qu'ils connaissent tous les noms pgcd et ppcm ? Pas sûre, mais ça ne les empêche pas de savoir les trouver et la décomposition en facteurs premiers ne pose pas de problème.

    In mémoriam de tous les professeurs assassinés dans l'exercice de leurs fonctions en 2023, n'oublions jamais les noms de Agnes-Lassalle et Dominique-Bernard qui n'ont pas donné lieu aux mêmes réactions sur ce forum (et merci à GaBuZoMeu)
  • Dom
    Dom
    Modifié (August 2022)
    Haha Jaymz. 
    Mais ce n’est pas une provocation à côté de xax qui s’ennuie et qui trolle n disant que Haby a révolutionné l’École et l’Enseignement en France. 
    Pour revenir au sujet : c’est bien en 5e que j’ai vu aussi PPCM et PGCD et les petites décompositions d’entiers en produits de nombres premiers.
    Mon prof de maths de l’époque, je l’avais en Maths et en Physique. Et je l’ai eu en 5e et en 4e.
    Je pense que ça devait être un PEGC (même s’il me semble qu’ils ne pouvaient enseigner qu’en 6e et 5e au maximum…). 
  • Riemann_lapins_cretins
    Modifié (August 2022)
    OShine, sérieusement pour la formule de Legendre, tu n'as jamais réfléchi au fait que si par exemple on veut calculer $v_{2}(1000!)$, bah t'as la moitié des facteurs de $1000!$ qui est paire, que si on prend juste ces facteurs, il y en a la moitié qui est divisible encore par deux (donc ces facteurs sont divisibles par $2^{2}$), que parmi ceux-ci la moitié est encore divisible par deux (facteurs divisibles par $2^{3}$), et qu'au final le résultat donne : 
    $$v_{2}(1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1\qquad ?$$
    C'est une formule très simple à comprendre et démontrer, mais tu présentes ça comme une des preuves les plus difficiles et infaisables niveau spé. Cette formule, elle ne figurait pas dans mon cours, la première fois que je l'ai vue c'était dans un DS, et la question était de la montrer, sans étapes intermédiaires pour nous aider. Et ce n'est pas une question qui avait paru difficile à la classe.
    Encore une fois tu agis comme un profane en maths en croyant que, sous prétexte qu'une formule possède quelques symboles compliqués (des parties entières et une somme, wow), elle est incroyablement difficile et à la portée des génies. Bah non, ce n'est pas forcément le cas. Legendre c'est facile.
    Et à côté de ça des formules qui s'écrivent en un huitième de ligne sans symbole effrayant peuvent être très dures à démontrer (comme Cayley-Hamilton qui, sans qu'on nous donne la preuve par matrice compagnon, n'aurait pas été trouvée par une très large majorité des taupes de France, et bien plus parlant encore, le théorème de convergence dominée qui s'écrit tout simplement "limite intégrale = intégrale limite"), et pour prendre un exemple que tu manipules dans ta fonction, le théorème de Pythagore qui est tout sauf trivial et qui embêterait même des bons étudiants s'ils devaient improviser une preuve, en supposant qu'ils n'en connaissent aucune).
  • verdurin
    Modifié (August 2022)
    Bonsoir Dom.
    J'étais professeur en collège à cette époque.
    Les PEGC enseignaient de la sixième à la troisième. Au collège quoi. PEGC= Professeur d'Enseignement Général en Collège.
    Et je me souviens de l'époque où l'on a supprimé les notions de ppcm et pgcd en cinquième. La justification officielle était que l'on avait supprimé l'arithmétique en terminale C.
    Je l'avais regretté parce que les élèves de cinquième aimaient bien cette partie du programme (peut-être parce que j'aimais l'enseigner).
    édition : remplacer « les élèves » par « mes élèves ».
  • Au temps pour moi. J’avais entendu qu’un statut ne pouvait faire que 5e maximum et avais cru que c’était PEGC. Je me demande s’il existe autre chose du coup… 

  • Dom, je ne vois pas en quoi le fait d'avoir une certaine culture des programmes fait de moi un troll. Enfin bon, je ne peux pas te reprocher ton éducation, mais peut-être ta méconnaissance crasse de l'histoire somme toute récente de l’enseignement des mathématiques.

    René Haby a été probablement un des meilleurs ministres que nous ayons eu (1974 - 1978), et je trouve que les programmes concoctés sous son ministère sont d'une grande qualité. Il inaugure ce qui fut certainement l'âge d'or de l'enseignement des mathématiques en France (1974-1994), tant en qualité qu'en nombre d'élèves correctement formés (je rappelle que le nombre des très bon élèves en 4eme est passé selon Timss de 15% en 1995 à 2% en 2019).

    Je recommande pour s'en convaincre de parcourir les programmes et manuels de l’époque. Ci-joint (Mauguin 5eme programme 1977) le chapitre qui concerne le fil.
    "J'appelle bourgeois quiconque pense bassement." Gustave Flaubert
  • Dom
    Dom
    Modifié (August 2022)
    Je ne m’ennuie pas ou n’ai pas de temps à tuer en ce moment. 
    Bon courage xax. 
  • xax
    xax
    Modifié (August 2022)
    La consultation des ouvrages de Camille Lebossé et de Corentin Hémery confirme ce qu'écrivait Chaurien : dans les deux décennies précédentes on voyait le PPCM et le PGCD en 4eme. Les programmes Haby sont nettement plus riches d'un point de vue des concepts mathématiques développés.

    p.s. sur les PEGC. Dans les années 70 la proportion de certifiés et d'agrégés ne dépassait 20% des profs de maths, les PEGC étant plus nombreux ainsi que les maître-auxiliaires. Aujourd'hui il n'y a plus que quelques centaines de PEGC en activité, mais leur publication (PEGC le collège) existe toujours. Pour les nostalgiques ... 
    "J'appelle bourgeois quiconque pense bassement." Gustave Flaubert
  • nicolas.patrois
    Modifié (August 2022)
    Les PEGC étaient (sont ?) des instituteurs (catégorie B ) affectés en collège. Ils pouvaient enseigner deux voire trois disciplines (j’ai eu un qui enseignait la biologie, l’anglais et le dessin). Le truc qui ne plaisait pas au ministère, c’est qu’ils avaient droit de partir à la retraite (à taux plein) à 55 ans (comme les instituteurs). Leur grille indiciaire comportait une hors-classe (qui correspondait aux derniers échelons de la classe normale des certifiés) et une classe exceptionnelle (hors-classe des certifiés).
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Dom
    Dom
    Modifié (August 2022)
    Ha ! J’attends un bus 😀
    xax, tu n’as toujours pas répondu à l’argument suivant : une fois la loi Haby [collège unique] passée, il y a une certaine inertie dans le temps pour qu’on en cueille les fruits. Idem pour les programmes (je ne conteste pas qu’ils étaient bien faits !). Quel âge à celui qui découvre l’École pour la première fois et qui la découvre sous cette loi de 1975 ? Quand il sort de l’école, c’est quel âge ?
    Je ne lirai pas un document de plus de deux pages à ce sujet. Soit on en fait référence (à cette inertie), et je suis prêt à entendre ou lire… soit personne n’en parle et l’étude contient donc une énorme carence. 
    J’attends que « l’Historien Incontestable » apporte un argument à cette INERTIE !
    Remarque : tu devrais retirer ce que tu dis sur moi, « méconnaissance crasse de l’histoire de l’enseignement ». Ce n’est pas du tout un argument et c’est gratuit. Et si ça se trouve… tu as tort… réfléchis…
  • Haby était un si bon ministre que sa réforme a eu des résultats positifs avant même d'être votée. C'est ça le talent.

    Je me fous de savoir si ce qu'il a fait était bien ou pas.
    Ce que je sais, c'est que l'étude des PGCD et PPCM en collège, ça existait bien avant Haby. 



    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Ça ne rentre pas dans la fenêtre temporelle de son idéologie donc, lourrran, poubelle ! Tu ne sais rien. 
Connectez-vous ou Inscrivez-vous pour répondre.