Pateysoft

Expression de la conjecture de Fermat avec l'indicatrice d'Euler

Ludovic PATEY — 2009-04-14T21:11:37Z

Les démonstrations sont à venir.

Considérations générales

Un nombre de Fermat est de la forme . Fermat a conjecturé à tort que tous les nombres de cette forme étaient premiers. Une nouvelle conjecture propose qu'il y aie un nombre fini de nombres de Fermat.

La fonction indicatrice d'Euler associe à un entier le nombre d'entiers premiers avec lui et qui lui sont inférieurs.

Nous allons maintenant nous intéresser aux solutions impaires des équations de la forme , n étant donné et allons voir que l'existence de solutions est équivalent à la conjecture sur les nombres de Fermat.

Lemme 1 : Soit un antécédent impair à une puissance de 2 par la fonction indicatrice d'euler. Alors est un produit de nombres premiers impairs distincts. Autrement dit

Il est tout d'abord évident que si est impair, tous ses diviseurs sont impairs.

Soit un nombre premier impair divisant et la plus grande puissance tel que divise . Alors avec .

Donc

Or . Si était supérieur à 1, alors diviserait donc ne serait plus une puissance de 2.

Il s'ensuit que est un nombre impairs sans carrés, donc un produit de nombres premiers impairs distincts.

Lemme 2 : Soit un antécédent impair à une puissance de 2 par la fonction indicatrice d'euler. Alors est un produit de nombres premiers de Fermat. Autrement dit

Tout d'abord, montrons que tous les nombres premiers diviseurs de sont de la forme . En effet, en cas contraire, il existerait un nombre impair tel que .

Alors , donc diviserait . Il s'ensuivait que ne serait plus une puissance de 2. Ainsi, tout diviseur premier de est de la forme .

Il a été démontré par Fermat que si est premier, alors est une puissance de 2. En effet, dans le cas contraire, 3 diviserait .

Nous obtenons donc le résultat du lemme.

Lemme 3 : Soit 2k+1 un antécédent impair à par la fonction indicatrice d'euler. Soit la représentation binaire de n. Alors k est unique et n'existe que si tout i, est premier.

Soit un produit de nombres premiers de Fermat.

Alors .

Comme est un produit de facteurs premiers distincts, alors les sont distincts 2 à 2.

Nous avons donc , qui est la décomposition unique en puissances de 2 distinctes de . Autrement dit, pour obtenir , il est nécessaire et suffisant que chacun des soit présent, donc que chacun des soient des nombres premiers de Fermat.

Le résultat du lemme est alors immédiat.

Théoreme 4 : La conjecture sur les nombres premiers de Fermat est vraie si et seulement si l'équation n'a pas de solution à partir d'une certaine valeur de n. Plus précisément, seuls les 5 premiers nombres de Fermat sont premiers si et seulement si l'équation n'a de solutions que si n est strictement inférieur à 32.

Si les nombres premiers de Fermat sont en nombre fini, il ressort du lemme précédent qu'il y a une nombre fini de sommes de la forme , donc un nombre fini de . Si l'on prend le maximal solution de l'équation, il n'y a plus de solution à partir de . La réciproque est également vraie.

Si seuls les 5 premiers nombres de Fermat sont premiers, alors le maximal est .

Factorisation d'un nombre semi-premier à partir du totient d'Euler

Ludovic PATEY — 2009-01-05T11:13:47Z

Introduction

Les nombres semi-premiers sont utilisés notamment dans des systèmes de chiffrement comme RSA. Nous allons ici développer une manière simple pour factoriser ces nombres en connaissant la valeur de leur indicatrice d'euler.

Rappel

Soient et deux nombres premiers, et l'indicatrice d'Euler,

Factorisation

Soient et .

Soit . Alors, . En effet, .

Il suffit donc de résoudre l'équation du second degré. Les racines sont

Ainsi, et .

Conjecture d'Agoh-Giuga

Ludovic PATEY — 2008-06-23T19:44:46Z

Enoncé de la conjecture

D'après Takashi Agoh et Giuseppe Giuga, un nombre est premier si et seulement si

Nombres de Carmichaël

Il est montré que tout nombre composé vérifiant la congruence (1) est un nombre de Carmichaël.

Soit un nombre de Carmichaël. Il a les propriétés suivantes :

est sans carré et pour chaque diviseur premier ,\ divise .

Quelques résultats

Proposition 5 : Soit un nombre ne vérifiant pas la conjecture, alors il peut s'écrire de la forme avec un nombre premier et un nombre premier avec .

Alors, est un nombre de Carmichaël ( voir la proposition 4 de l'article de 1995 d'Agoh ). Les nombres de Carmichaël sont des nombres sans carré. Il s'ensuit immédiatement que peut s'écrire sous la forme avec un nombre premier et premier avec .

Proposition 6 :

Démonstration

D'après les propriétés des nombres de Carmichaël,

Donc la relation de congruence est également vérifiée modulo :

De plus, comme vérifie la congruence (1)

Et la relation de congruence est également vérifiée modulo :

Parmi les nombres entre 1 et , il y en a divisibles par et premiers avec . En effet, les nombres divisibles par sont de la forme avec un entier naturel entre 1 et .

Comme , alors , donc .

Si divise , alors ( car )
Si est premier avec , alors d'après le théorème de Gauss, , donc .

En sommant les restes, nous obtenons

Donc d'après (2)

Ainsi

Donc

Proposition 7 :

Démonstration

Comme est un nombre de Carmichaël, . D'après le lemme précédent, . Ainsi, .

Proposition 8 : Il n'existe aucun contre-exemple de Carmichaël ne possédant que 3 facteurs premiers.

Démonstration

Raisonnons par l'absurde. Si avec p, q et r de nombres premiers. Les nombres de Carmichaël étant sans-carré, . Prenons . D'après la proposition précédente

Or . Donc nous obtenons une absurdité.

Rendre les méthodes insensibles à la casse

Ludovic PATEY — 2008-06-09T08:27:48Z

Introduction

PHP est un sensible à la casse, c'est à dire qu'une méthode avec une majuscule sera différente d'une méthode avec une minuscule. Ainsi, le code suivant retournera une erreur :

<?php class MaClasse { public function maMethode() { echo "Hello World"; } } $objet = new MaClasse(); // Code générant une erreur à cause de la majuscule $objet->MaMethode(); ?>

Les fonctions et méthodes à utiliser

Pour obtenir notre résultat, nous allons avoir recours à une méthode magique et quelques fonctions que nous allons détailler :

La méthode __call()

Cette méthode est appelée lorsque nous faisons appel à une méthode qui n'existe pas. Elle prends le nom de la méthode appelée en paramètre, ainsi qu'un tableau des arguments.

La fonction get_class_methods()

Cette fonction retourne un tableau des méthodes de l'objet passé en paramètre ou du nom de la classe.

La fonction call_user_func_array()

Cette fonction très puissante permet d'exécuter une méthode ou une fonction de manière dynamique en lui passant en paramètre le nom de la fonction et un tableau de paramètres.

Rendre l'appel des méthodes insensible à la casse

Il suffit de combiner les fonction introduites précédemment pour obtenir le résultat voulu :

<?php class MaClasse { public function maMethode() { echo "Hello World"; } public function __call( $nom, $arguments ) { // Pour chaque méthode de la classe foreach( get_class_methods( $this ) as $methode ) { // Si la méthode est la même que celle appelée if( strtolower( $methode ) == strtolower( $nom ) ) { // Appeler la méthode dynamiquement return call_user_func_array( array( $this, $methode ), $arguments ); } } // Par défaut, lancer une erreur trigger_error( 'Méthode inconnue', E_USER_ERROR ); } } $objet = new MaClasse(); // Code ne générant pas d'erreur $objet->MaMethode(); ?>

Pour aller plus loin

Il est tout d'abord conseillé de créer une classe Caseless ne possédant que la méthode __call() et faire hériter toutes les classes de cette dernière.

Il est également possible d'imaginer une classe corrigeant les fautes de frappe grâce à la fonction levenshtein() qui retourne un entier représentant le nombre d'opérations à effectuer pour passer d'une chaîne à une autre.

Créer une grille de Sudoku

Ludovic PATEY — 2008-06-03T17:18:06Z

Introduction

Qu'est-ce qu'un sudoku ?

Un sudoku est un jeu populaire dont le but est de remplir une grille de 9x9 divisée en carrés de 3x3 avec des chiffres selon des contraintes très restrictives.

Voici un exemple de grille :

Chaque ligne, chaque colonne et chaque carré de 3x3 ne doit contenir qu'une occurrence de chaque nombre entre 1 et 9. Ainsi, dans la première ligne, il est impossible de placer un 6 dans une des cases vides car la ligne en possède déjà 1.

Les grilles de sudoku sont réparties en plusieurs niveaux, allant de débutant à diabolique, selon des critères très subjectifs et dont la difficulté de niveau peut varier fortement suivant le fournisseur de grille.

La création des sudoku

Avec la popularisation du jeu, il est devenu très rapidement nécessaire de trouver des algorithmes pour créer automatiquement des grilles afin de répondre à la demande toujours croissante. Voici une méthode assez générale, à partir de laquelle il est bien entendu possible d'ajouter ses propres subtilités pour rendre le jeu plus attractif.

Notre programme est scindé en 2 étapes : la génération de la grille complète, puis le retrait des chiffres. Cet ordre de création a été choisi pour plusieurs raisons : il est nécessaire de disposer de la grille de solution afin de satisfaire la curiosité d'éventuels joueurs qui n'arriveraient pas à la compléter. De plus, il n'est pas possible d'ôter aléatoirement des valeurs de la grille, sous risque de créer une grille possédant plusieurs solutions. La solution unique est une règle d'or de la création de sudoku, bien que parfois non respectée.

Afin d'éviter ce problème, nous allons baser nos algorithmes de retrait sur le principe fondamental suivant : « Ne retirer que les pièces qu'il est possible de retrouver de manière certaine par une réflexion implémentée sous forme algorithmique ».

Le niveau de difficulté est donc tout simplement géré par la complexité de l'algorithme qui doit vérifier qu'une pièce est retrouvable.

Le présent dossier n'a pas pour vocation de créer une application de sudoku mais uniquement d'orienter le lecteur vers une méthode algorithmique qu'il pourra affiner à sa guise. Ainsi, l'affichage de la grille n'est pas gérée, de même pour l'interaction avec le joueur. Les codes sources proposés sont programmés en PHP avec une syntaxe procédurale en prenant soin d'utiliser des fonctions simples afin de faciliter sa transcription dans d'autres langages.

Génération de la grille

Notre première étape consiste donc à générer la grille résultat. Comment trouver une grille respectant les contraintes du jeu, de manière certaine ? Eh bien il n'existe aucun algorithme ne permettant de la générer de manière directe. La solution employée par tous est donc l'utilisation d'un algorithme de backtracking.

Introduction au backtracking

Le bactracking ( retour sur trace en Français ), est un algorithme récursif optimisé pour la recherche de solutions avec contraintes, ce qui est précisément le cas de la génération d'une grille de sudoku. Voici un pseudo code général le représentant :

<?php function backtracking( variables ) { if( toutes les variables sont assignées ) { return variables ; } foreach( valeur ) { if( solution partielle respecte contraintes ) { solution = backtracking( variables + valeur ) ; if( solution ) { return solution; } } } // Si aucune valeur ne respecte les contraintes return false ; } ?>

La grande différence entre une recherche de toutes les solutions et la recherche par analyse combinatoire est que celle-ci coupe les branches dès qu'une solution partielle ne vérifie pas les contraintes imposées, et évite ainsi quantité de tests inutiles.

Application au cas du Sudoku

Dans notre cas, nous nous placer successivement à chaque case du jeu, et essayer de placer un numéro entre 1 à 9, différent des numéros qui sont dans la même ligne, dans la même colonne ou dans le même carré que la case. S'il ne reste aucun chiffre possible, alors il faut revenir en arrière ( d'où le nom retour sur trace ) et essayer d'autres numéros dans les cases précédentes.

Notre fonction va donc prendre en paramètre un une matrice 9x9 implémentée sous forme de tableau. Ce dernier sera vide lors du premier appel à la fonction, puis se remplira petit à petit à chaque appel de récurrence. La fonction retournera soit la matrice contenant la grille générée, soit false.

Le choix du numéro à placer doit être fait de manière aléatoire sans quoi toutes les grilles seraient similaires.

Voici un exemple d'algorithme de génération de grille :

<?php function creer_grille( $grille = array(), $position = 0 ) { // Si nous sommes arrivés à la fin, la grille est trouvée if( $position == 81 ) { return $grille; } // Calculer la ligne et la colonne $i = floor( $position / 9 ); $j = $position % 9; // Créer une liste des nombres de 1 à 9 $valeurs = range( 1, 9 ); // Retirer les valeurs déjà utilisées for( $k=0; $k<9; $k++ ) { // Oter de la liste les nombres de la ligne if( $v = $grille[ $i ][ $k ] ) { unset( $valeurs[ $v-1 ] ); } // Oter de la liste les nombres de la colonne if( $v = $grille[ $k ][ $j ] ) { unset( $valeurs[ $v-1 ] ); } // Oter de la liste les nombres du carré if( $v = $grille[ floor($i/3)*3 + floor($k/3) ][ floor($j/3)*3 + ($k%3) ] ) { unset( $valeurs[ $v-1 ] ); } } // Melanger le tableau shuffle( $valeurs ); // Essayer les valeurs restantes jusqu'à trouver la solution foreach( $valeurs as $v ) { $grille[$i][$j] = $v; $resultat = creer_grille( $grille, $position + 1 ); // Si on trouve la solution, on la retourne if( $resultat ) { return $resultat; } unset( $grille[$i][$j] ); } // Si nous arrivons à la fin de la boucle, aucune grille n'existe // avec les valeurs précédentes return false; } ?>

Nous disposons désormais d'une fonction retournant une matrice 9x9 contenant les valeurs de la grille. Il reste désormais à retirer des valeurs avec des algorithmes que nous allons détailler à la prochaine étape.

Retrait des valeurs

Dans cette partie, nous allons développer la fonction qui, à une grille donnée, va choisir des positions aléatoirement et regarder s'il est possible de les replacer sans ambigüité. Les fonctions de test seront explicitées dans la partie suivante.

Nous allons tester dans un ordre aléatoire successivement toutes les positions pour voir s'il est possible de les retirer. Il est évident que plus les valeurs sont retirées, plus il est difficile de retirer des valeurs car pour les retrouver, il faut faire appel à des réflexions plus complexes.

Le nombre de valeurs restantes sera donc fonction de la puissance de l'algorithme de retrait utilisé.

Cette fonction va contenir une petite subtilité : lorsqu'une position est testée, nous allons tester son image par la symétrie centrale de centre celui du carré 9x9, afin de garder une grille équilibrée au niveau du retrait des valeurs.

Voici donc une fonction qui va prendre en premier paramètre la grille complète de sudoku, puis en second paramètre un tableau de fonctions de retrait de valeurs, que nous décrirons ensuite.

<?php function retirer_valeurs( $grille, $tests = array() ) { // Créer une liste de toutes les positions $positions = range( 0, 80 ); // Tant que la liste des valeurs à tester n'est pas vide while( $positions ) { // Prendre une position au hasard $position = array_rand( $positions ); unset( $positions[ $position ] ); // Calculer la ligne et la colonne $i = floor( $position / 9 ); $j = $position % 9; // Pour chaque test de retrait foreach( $tests as $test ) { // S'il est possible de retirer la position if( $test( $grille, $i, $j ) ) { // Supprimer la valeur de la grille unset( $grille[ $i ][ $j ] ); break; } } // Calculer la ligne et la colonne opposées $position = 80 - $position; $i = floor( $position / 9 ); $j = $position % 9; unset( $positions[ $position - 1 ] ); // Pour chaque test de retrait foreach( $tests as $test ) { // S'il est possible de retirer la position if( $test( $grille, $i, $j ) ) { // Supprimer la valeur de la grille unset( $grille[ $i ][ $j ] ); break; } } } return $grille; } ?>

Algorithmes de retrait

Nous entrons dans le cœur de la création des sudoku. Les algorithmes utilisés dans cette partie dépendent en grande partie des créateurs de sudoku, chacun gardant jalousement ses secrets de fabrication. Afin de créer les algorithmes de retraits, il est nécessaire de se pencher sur les raisonnements que font un joueur afin de lui-même compléter la grille.

Beaucoup de raisonnements sont redondants, et il est donc important de différencier les techniques utilisées. Il est facile de voir si 2 raisonnements sont similaires aux taux de retrait de nombres de la grille finale.

Tous les algorithmes de retrait devront respecter la pseudo-signature suivante :

<?php bool est_retirable( Array[9][9] grille, int ligne, int colonne ) ?>

Premier raisonnement : les contraintes de placement

Principe

Le raisonnement au plus bas niveau que va effectuer le joueur va être de regarder s'il n'est pas possible de placer des valeurs en se contentant d'appliquer les règles du jeu : le nombre ne doit pas déjà être présent dans la ligne, dans la colonne et dans le carré de 3x3. L'ensemble des valeurs possibles restantes est égale à 1, alors il peut placer la valeur.

Dans l'exemple précédent, nous voyons qu'il ne reste plus qu'un 2 possible à l'emplacement coloré en jaune. Il n'y a donc pas d'ambigüité.

Implémentation

L'implémentation de ce raisonnement est extrêmement simple. Elle est d'ailleurs entièrement contenue dans la fonction de génération de la grille.

<?php function est_retirable_1( $grille, $i, $j ) { unset( $grille[$i][$j] ); // Créer une liste des nombres de 1 à 9 $valeurs = range( 1, 9 ); // Retirer les valeurs déjà utilisées for( $k=0; $k<9; $k++ ) { // Oter de la liste les nombres de la ligne if( $v = $grille[ $i ][ $k ] ) { unset( $valeurs[ $v-1 ] ); } // Oter de la liste les nombres de la colonne if( $v = $grille[ $k ][ $j ] ) { unset( $valeurs[ $v-1 ] ); } // Oter de la liste les nombres du carré if( $v = $grille[ $i + floor($k/3) ][ $j + ($k%3) ] ) { unset( $valeurs[ $v-1 ] ); } } // Retourne true s?il ne reste plus qu?une valeur return count($valeurs) == 1; } ?>

Second raisonnement : les contraintes distantes

Principe

Le premier raisonnement trouve rapidement ses limites. Il ne faut pas pour autant considérer que la valeur ne peut pas être retrouvée facilement. Prenons le cas suivant :

Etant donné un carré de 3x3 et une valeur, si toutes les cases vides du carré sauf une contiennent la valeur dans la même ligne ou la même colonne, alors cette valeur se situe forcément dans la dernière case vide.

Nous voyons que ce raisonnement n'est pas équivalent au précédent car le précédent ne permettait pas de trouver la valeur. En effet, il y restait 1,3,5,6.

Implémentation

L'implémentation du second raisonnement n'est pas non plus très compliquée. Connaissant les coordonnées de la valeur dont on veut tester la non-ambigüité, il suffit d'effectuer un test d'existence de la valeur dans la ligne et la colonne de toutes les autres cases vides du carré :

<?php function est_retirable_2( $grille, $i, $j ) { // Récupérer la valeur, puis la supprimer $valeur = $grille[$i][$j]; unset( $grille[$i][$j] ); // Pour chaque position du carré 3x3 for( $k=0; $k<9; $k++ ) { // Calculer les coordonnées courrantes $ligne = floor( $i/3 ) + floor( $k / 3 ); $colonne = floor( $j/3 ) + ( $k % 3 ); // Si nous sommes dans une case vide différente de la case étudiée if( $ligne != $i && $colonne != $j && !$grille[$ligne][$colonne] ) { // A chaque case de sa ligne ou de sa colonne for( $l=0; $l<9; $l++ ) { // Si nous trouvons la valeur if( $grille[$ligne][$k] == $valeur || $grille[$k][$colonne] == $valeur ) { // Sortir de la boucle break; } } // Si la boucle est terminée, alors une autre case vide // est ambigüe, donc la pièce n'est pas retirable return false; } } // Si toutes les cases vides ont été testées sans retourner false // alors aucune n'est ambigüe return true; } ?>

Exemple d'utilisation

Après avoir vu quelques exemples d'algorithmes de retraits, voici un code permettant de les appeler :

<?php // Créer une nouvelle grille $grille_complete = creer_grille(); // Lui retirer des valeurs $grille = retirer_valeurs( $grille_complete, array( 'est_retirable_1', ?est_retirable_2? ) ); // L'afficher echo '<table>'; for( $i=0; $i<9; $i++ ) { echo '<tr>'; for( $j=0; $j<9; $j++ ) { echo '<td>' . $grille[$i][$j] . '</td>'; } echo '</tr>'; } echo '</table>'; ?>

Pour aller plus loin

La grille affichée comportera encore beaucoup trop de valeurs, rendant la grille trop facile. Il est donc nécessaire de trouver d'autres raisonnements et les implémenter en PHP. Nous n'étudierons pas plus de raisonnements car ils deviennent de plus en plus lourds à formaliser, et d'autant plus à implémenter.

Voici cependant un principe qui fera faire un grand pas dans la complexité de la grille : Il suffit de créer un arbre des dépendances des valeurs retirées et dire « si toutes les valeurs de l'arbre de dépendance sont non-ambigües, alors considérer la valeur racine comme non-ambigüe ». A partir de ce principe, les algorithmes vont évoluer des tests de valeurs existantes à des tests de valeurs non-ambigües, ce qui va grandement augmenter le taux d'acceptation de retrait.

Conjecture de Carmichael sur la fonction indicatrice d'Euler

Ludovic PATEY — 2008-06-01T20:49:22Z

Présentation de l'indicatrice d'Euler

La fonction indicatrice d'Euler notée associe à tout entier naturel le nombre d'entiers inférieurs qui sont premiers avec lui.

La conjecture de Carmichael stipule que toute image par la fonction indicatrice d'Euler possède au moins 2 antécédents. Autrement dit

Quelques résultats

Nous allons vérifier la conjecture jusqu'à de grands nombres.

Proposition 9 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par .

Démonstration :

Pour tout nombre premier avec 2 ( donc impair ) n, .

Proposition 10 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par .

Démonstration :

Le plus petit nombre ne vérifiant pas la conjecture étant divisible par , il s'écrit de la forme . Si k est premier avec 3, alors .

Proposition 11 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par .

Démonstration :

Le plus petit nombre ne vérifiant pas la conjecture étant divisible par , il s'écrit de la forme . Si k est premier avec 7, alors .

Proposition 12 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par .

Démonstration :

Le plus petit nombre ne vérifiant pas la conjecture étant divisible par 4x9x49, il s'écrit de la forme . Si k est premier avec 43, alors .

Si divise n

Alors

Proposition 13 : S'il est divisible par , le plus petit nombre ne vérifiant pas la conjecture est divisible par .

En effet, toujours d'après le même principe

est premier, donc divise n
est premier, donc divise n
est premier, donc divise n

Proposition 14 : S'il est divisible par , le plus petit nombre ne vérifiant pas la conjecture est divisible par .

est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n

Un dernier pour la route :

Proposition 15 : S'il est divisible par , le plus petit nombre ne vérifiant pas la conjecture est divisible par et par .

= 3278561457979260561820783603203948493222867

Nous allons nous en arrêter là.

Si ne divise pas n

Alors

Proposition 16 : S'il n'est pas divisible par , le plus petit nombre ne vérifiant pas la conjecture est divisible par .

est premier, donc divise n
est premier, donc divise n

Proposition 17 : S'il n'est pas divisible par , le plus petit nombre ne vérifiant pas la conjecture est divisible par .

est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n
est premier, donc divise n

Conjecture d'Erdös sur la fonction indicatrice d'Euler

Ludovic PATEY — 2008-06-01T19:44:12Z

Présentation de l'indicatrice d'Euler

La fonction indicatrice d'Euler notée associe à tout entier naturel le nombre d'entiers inférieurs qui sont premiers avec lui.

D'après Erdös, pour tout entier naturel n, il existe des entiers naturels i et j tels que .

Démonstration sous l'hypothèse de Goldbach

Cette conjecture se démontre trivialement si la conjecture de Goldbach est vraie. Voici pour rappel son énoncé :

Tout nombre pair supérieur à 2 est somme de 2 nombres premiers.

Alors, pour tout nombre n, il existe 2 nombres premiers p et q tels que .

Alors, . La conjecture d'Erdös est alors démontrée.

Conjecture de Lehmer sur la fonction indicatrice d'Euler

Ludovic PATEY — 2008-06-01T16:22:40Z

Présentation de l'indicatrice d'Euler

La fonction indicatrice d'Euler notée associe à tout entier naturel le nombre d'entiers inférieurs qui sont premiers avec lui.

La conjecture de Lehmer stipule que tout entier naturel n est premier si et seulement si

Quelques résultats

Voici quelques résultats personnels sur la conjecture.

Proposition 18 : , si , alors n est impair.

Démonstration :

est pair, donc . Il s'ensuit que n est impair.

Proposition 19 : , si , alors n est un produit de nombre premiers distincts 2 à 2.

Démonstration :

Si n n'est pas un produit de nombre premiers distincts 2 à 2, alors il existe un nombre premier p tel que . Ainsi, , or , donc ce qui est impossible car p est premier.

Proposition 20 : , si , alors n est n'est pas un produit de 2 nombres premiers.

Démonstration :

Si n est un produit de 2 nombres premiers p et q, comme d'après la proposition précédente, , alors .

Donc

Or , donc et . Il s'ensuit que , ce qui est en contradiction avec les hypothèses.

Les premières propositions nous montrent que les nombres composés vérifiant la relation de congruence sont des nombres de Carmichaël. Il est d'ailleurs facile de le démontrer en remarquant que

Antécédents de 1 par F

Ludovic PATEY — 2008-05-31T14:59:10Z

Antécédents par f

Dans cette partie, nous allons nous pencher sur les antécédents de par .

La conjecture de Syracuse est équivalente à l'égalité suivante

Du fait de l'existence du cycle trivial, . Il en découle que . Nous obtenons donc la relation d'inclusion suivante :

Les antécédents de \1\ par f sont relativement simples à trouver : il s'agit des puissances de tels que est une puissance de 2 :

L'ensemble des tels quel 3 divise est l'ensemble des nombres pairs. En effet, , or , donc .

Nous obtenons donc l'égalité

Les antécédents de par sont, outre les antécédents par , l'ensemble des tels que .

Par des procédés de calcul similaires, nous obtenons

L'expression des antécédents de par devient très rapidement compliquée. Le nombre de sous-ensembles croît avec car le nombre de variables augmente.

Pour , notons

Avec les décrivant

Il est possible de généraliser l'égalité pour tout , mais nous ne le ferons pas car la formule générale est très peu lisible et n'apporte pas d'élément remarquable permettant d'espérer obtenir de nouveaux outils pour démontrer la conjecture.

Ces résultats ne sont pas tout à fait inutiles, car nous pouvons en déduire que les équations diophantiennes obtenues à partir des n'ont pas pour solution, car en cas contraire, l'ensemble des nombres de termes impairs de la suite de Syracuse serait majoré par .

Longueur minimale des cycles

Ludovic PATEY — 2008-05-31T14:41:04Z

Longueur minimale des cycles de Syracuse

Le but est de trouver une expression de tel que si tous les entiers naturels inférieurs à vérifient la conjecture de Syracuse, alors il n'existe pas de suite périodique non triviale de période .

Autrement dit, soit l'ensemble des entiers naturels impairs

Proposition 21 :

Soit une fonction de dans telle que

Le maximum de la fonction tel que la contrainte soit vérifiée est atteint pour

Démonstration :

L'expression (1) traduit simplement le fait que la fonction atteigne son maximum pour = .

L'expression (2) traduit le fait que l'accroissement de variable fait décroître moins rapidement la fonction que , elle même moins que ... jusqu'à .

Raisonnons par l'absurde.

S'il au moins différent de 1 tel que et le maximum est atteint pour le nuplet .

Alors, prenons et .

D'après (2),

Ainsi, le maximum n'était pas atteint pour ce nuplet, donc le nuplet pour lequel le maximum est atteint est .

Nous nommerons « fonction de la forme F1 » toute fonction vérifiant les conditions précédentes.

Proposition 22 :

Si la suite et périodique de période , alors vérifie l'égalité suivante :

Démonstration :

Reprenons l'égalité (3) de l'étude de la suite . vérifie l'égalité suivante :

En isolant , l'équation devient

Proposition 23 : Les variables sont des entiers naturels strictements positifs tels que

Démonstration :

Sachant que tous les termes de la suite sont impairs, est pair, donc les sont strictement positifs, donc minorés par 1.

étant positif, doit l'être également.

Ainsi,

Ou autrement dit

D'où le résultat de la proposition

Proposition 24 : Le terme atteint son maximum pour

Démonstration :

Etant donné que le nombre est fixé, si un des croît, croît également ainsi que .

D'autre part, si est supérieur à , fait décroître plus rapidement que .

En effet, d'après l'égalité (3) de l'étude de la suite , la partie montre clairement que sera présent dans tous les termes de la somme, dans termes, ...

Le maximum de la fonction est atteint pour les minimums tels que l'inégalité du lemme des contraintes soit vérifié, et les soient non nuls.

Nous nous trouvons avec une fonction de la forme F1, donc la proposition \reftheoreme-du-maximum peut s'appliquer. La contrainte est .

Ainsi, le maximum est atteint pour

Donc

Ainsi la valeur minimum de est

La valeur maximum que prends la fonction est donc atteinte en

Théoreme 25 :

Soit M(n) tel que

Alors

Démonstration :

Revenons à l'égalité de la proposition \reflemme-de-la-fonction :

Elle peut également s'écrire comme suit :

En remplaçant les par leurs valeurs pour obtenir le maximum de la fonction, nous obtenons

Nous pouvons simplifier le second terme. L'inégalité devient alors

Le membre gauche est égal à la somme des premiers termes d'une suite géométrique de premier terme et de raison

L'inégalité peut donc s'exprimer ainsi :

Et en la simplifiant, la formule devient

En mettant le tout en facteur commun

Donc en définissant

Remarque : Ce résultat peut être amélioré en prenant en compte le fait que le plus petit entier naturel appartenant à un cycle trivial a une durée de vol en altitude infinie.

Antécédents de 1 par F

Etude des antécédents de 1 par la fonction de Syracuse