Partage
  • Partager sur Facebook
  • Partager sur Twitter

PGCD qui génère des nombres premiers

    2 mai 2019 à 20:16:58

    Bonsoir,

    J'ai le PGCD suivant qui me pose "problème", en fait j'aimerais démontrer la conjecture suivante :

    ---

    Soit phi(n) l'indicatrice d'Euler et appelons R le résultat du PGCD suivant.

    $$PGCD(1+\phi(n)!,n!)$$

    Si R est différent de 1 et R < n alors R est un nombre premier.

    ---

    J'ai pu vérifier pour de nombreux cas mais ça reste à l'état de conjecture. Pour ceux que ça intéresse voici un code Python pour tester (mais il est très lent à cause des factorielles) :

    from math import *
    from fractions import Fraction
    import fractions
    
    def phi(n):
        amount = 0        
        for k in range(1, n + 1):
            if fractions.gcd(n, k) == 1:
                amount += 1
        return amount
    
    def gcd(a, b):
            while b:
            a, b = b, a%b
        return a
    
    for i in range(2, 10000): # teste tous les entiers jusqu'à 10 000
            print(i,gcd(1+factorial(phi(i)),factorial(i)))

    Je vous remercie par avance, si vous avez même une petite idée ou une piste pour démarrer.

    -
    Edité par Craw 2 mai 2019 à 20:17:25

    • Partager sur Facebook
    • Partager sur Twitter
    Jeu du carré rouge modifié, quel niveau atteindrez-vous ? http://squared.22web.org
      3 mai 2019 à 0:28:53

      Tu es toujours sur la même logique. Tu as un nombre k (ici k=Phi(n)) ; Par construction, k est relativement grand. Tu calcules k! ; qu'on va noter kf.

      Kf est très grand par construction. Et kf est multiple de plein de nombres !

      Puis tu envisages kf+1 : forcément, les seuls diviseurs de kf+1, s'il a des diviseurs, sont plus grands que k. Et tu cherches des configurations où PGCD(kf+1,n) serait de la forme ab avec a et b tous les 2 premiers, tous les 2 entre phi(n) et n et tels que ab soit inférieur à n.

      C'est clair que ce cas est très rare. Trouver 2 nombres premiers entre phi(n) et n, tels que le produit de ces 2 nombres premiers soit inférieur à n, c'est rare.  En plus, il faut que le pgcd des 2 nombres considérés soit égal au produit de ces 2 nombres ab. Donc oui, tu vas avoir énormément de mal à trouver un contre exemple.

      Mais je pense que si tu remplaçais fact(phi(n))+1 par fact(phi(n))-1, tu arriverais aux mêmes conclusions. Sauf peut-être quelques cas triviaux.

      En gros, ta démarche, c'est : je prends un nombre n. J'élimine plein de nombres entre 1 et n, j'élimine en particulier plein de nombres composés, et s'il reste des nombres, je mets une condition très drastique, et s'il en reste encore, oh surprise, il ne reste que des nombres premiers.

      • Partager sur Facebook
      • Partager sur Twitter
        3 mai 2019 à 3:51:12

        edit : message inutile

        -
        Edité par edouard22 3 mai 2019 à 4:58:57

        • Partager sur Facebook
        • Partager sur Twitter

        Le souci des apparences ne vous inspire que méfiance, et le mur affiche son indifférence. L’histoire proposée est à la fois profonde et muette.

          3 mai 2019 à 11:53:15

          Merci pour cette réponse détaillée. Du coup ça explique aussi le comportement d'un autre PGCD que j'avais déjà posté.
          • Partager sur Facebook
          • Partager sur Twitter
          Jeu du carré rouge modifié, quel niveau atteindrez-vous ? http://squared.22web.org
            3 mai 2019 à 13:56:04

            sauf erreur de ma part, une preuve de ta conjecture :p 

            On peut remarquer que si un nombre premier \(p\) divise \(n! +1\), il est nécessairement supérieur à \(n\) sinon il diviserait \(n!\) don aussi \((n!+1)-n!=1\)   ce qui est absurde.

            Donc ici un nombre premier diviseur de \(\varphi(n)!+1\) est nécessairement supérieur à \(\varphi(n)\). Dans la  décomposition en facteurs premiers  de \(\varphi(n)!+1=p_1p_2 ... p_k\),  chaque facteur est donc supérieur à \(\varphi(n)\) 

             Si  PGCD (\(\varphi(n)!+1, n!)\) ne vaut pas 1, au moins un des \(p_i, i=1,...,k\) divise \(n!\)  . Si l'hypothèse  PGCD  inférieur à \(n\) est vérifiée sans être premier, il est nécessairement produit de au moins deux facteurs premiers  qui seront chacun nécessairement supérieurs à \(\varphi(n)\).

            Cette hypothèse d'un PGCD non premier inférieur à \(n\) sera donc fausse si \((\varphi(n))^2 > n\)

            A titre d'exemple, on peut voir que la décomposition en facteurs premiers de \(\varphi(n)!+1\) peut comprendre plusieurs facteurs inférieurs à \(n\)  

              \(18!+1= 19*23*29*61*67*123610951\)  alors que 18 est la valeur de la fonction d'Euler pour \(n=19,27,38,54\)

            Mais ce PGCD n'est certes pas premier mais évidemment supérieur à \(n\).

            En fait, la conjecture \((\varphi(n))^2 > n\) est vraie dés que \(n>6\) , selon   https://fr.wikipedia.org/wiki/Indicatrice_d%27Euler , paragraphe inégalités ;

            on peut donc conclure après avoir  vérifié que c'est vrai pour \(n \leq 6\) que tout PGCD différent de 1 inférieur à \(n\) est nécessairement premier.

            -
            Edité par Sennacherib 3 mai 2019 à 14:04:44

            • Partager sur Facebook
            • Partager sur Twitter
            tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
              3 mai 2019 à 15:24:51

              Merci bien pour la preuve, je vais la lire à tête reposée et si j'ai des questions je reviendrai. :)
              • Partager sur Facebook
              • Partager sur Twitter
              Jeu du carré rouge modifié, quel niveau atteindrez-vous ? http://squared.22web.org

              PGCD qui génère des nombres premiers

              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
              • Editeur
              • Markdown