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

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.

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

sauf erreur de ma part, une preuve de ta conjecture  

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