Citation Envoyé par Médiat Voir le message
Le reste de la division par 2 du carré d'un nombre premier > 2 est toujours 1, même chose pour la division par 3, 4 et 6 ; dans la division par 5 les restes 1 et 4 sont possibles, dans la division par 7 les restes 1, 2 et 4 sont possibles (tout cela est trivial à démontrer).
Le plus petit nombre plus grand que 1 étant 2, j'ai choisi celui-là c'est à dire un nombre premier n = 7k + 3.
C'est intéressant, je me suis dit voila un nouveau crible pour déterminer si un nombre est premier mais malheureusement la réciproque n'est pas vrai (il n'y a pas beaucoup de contre exemple):
77 n'est pas premier
772=5929
5929 = 2964*2+1
5929 = 1976*3+1
5929 = 1482*4+1
5929 = 1185*5+4

En revanche, on peut tester la règle sur un nombre et ci celli-ci n'est pas vérifiée le nombre n'est pas premier. Le nombre d'itération à l'air très faible comparé aux autres algorithmes, le problème c'est qu'il faut élever le nombre au carré et pour les grands nombres ca peut géner...