nodjim a écrit:S(2) mod n = 0 ça se prouve assez facilement.
Attention aux nombres composés de Carmichael, qui donneront le même résultat. C'est à dire que ton test de primalité ne sera pas vrai à 100%.
nodjim a écrit:Je confirme pour 561: 187 au lieu de zéro. C'est très curieux car la démo est indépendante de la primalité du nombre testé, sauf que 2^n=2.
Donc je regarde pourquoi ça cloche. A noter tout de même que 187 est le 1/3 de 561, donc ces 2 nombres sont ressemblants. Dans ma démo, j'avais exclu 3 comme p premier, mais seulement lorsqu'il était seul, pas dans une décomposition. Quelque chose m'échappe mais je ne vois pas quoi pour l'instant.
En revanche, pour 341=11*31, qui est un composé non Carmichael, mais dont 2^341=2 mod 341, on a bien S(2)=0.
Le test de primalité n'est donc pas sûr à 100%
nodjim a écrit:L'explication pour 341:
En fait, c'est 2^phi(n)=1 modulo n, phi étant la fonction indicatrice d'Euler (cardinal des nombres premiers avec n).
phi(341)=300 car (31-1)(11-1).
Or le 1 n'arrive pas forcément à 2^300, il peut arriver avant, en fait il arrive sur un diviseur de 300. Ici, pour 341, le hasard a voulu que le cycle soit 10. Or 10, s'il est bien diviseur de 300, est aussi diviseur de 340. C'est la raison pour laquelle 2^340=1 mod 341.
Malheureusement, on ne connait pas les cycles des nombres, il faut tester. Aussi, le test risque bien de ne pas fonctionner pour une infinité de valeurs, même si elles sont peu fréquentes.
Robot a écrit:Si n=5, S(2)=2^5-2^4+2^3-2^2=32-16+8-4=20, donc pgcd(n,S(2))=5>1, donc 5 est composé ...
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :