Nombre Premier

[C8H10N4O2]

Bonsoir à tous ,

Je me souviens de ma scolarité de cet algorithme pour déterminer si un nombre est premier : s'il n'est multiple ni de 2, ni de 3, ni de 5, le diviser successivement par les nombres premiers suivants. Dès que le quotient trouvé est inférieur au diviseur, on s'arrête et on peut affirmer que le nombre est premier.

Ex : 127 n'est pas divisible par 2, ni par 3, ni par 5.  127= 7*18+1 et 18>7, donc on recommence ...jusqu'à 127 = 13*9 + 10 , et 9<13 donc on peut affirmer que 127 est premier.

Quelqu'un a-t-il une idée de la manière dont on justifie / démontre la validité de cet algorithme ?

[pzorba75]

Par la commutativité de la multiplication, tout simplement.

[C8H10N4O2]

Il y a 2 heures, pzorba75 a dit :

Par la commutativité de la multiplication, tout simplement.

Je ne comprends pas bien, par exemple en disant que 127 = 13*9 + 10 <=>  127 = 9*13 + 10 ?  

[Black Jack]

Salut,

 

Avec des mots.

si tu divises 127 par 3, 5 , 7 , ... et que ces divisions (par des nombres premiers successifs) ne donne aucune un résultat entier, c'est que 127 n'est pas divisible par 3, 5 , 7 ...

quand faut-il s'arrêter ?

V127 = 11,26...

Si on divise 127 par un nombre premier V127 = 11,26... (donc 13 , 17 , 19 ...), le résultat de la division est forcément inférieur à V127 = 11,26...

Et donc si 127 était divisible par un nombre premier > V127, il serait divisible par le résultat de la division qui serait un nombre entier < V127 ...
Mais l'algorithme a déjà essayé de diviser 127 par les nombres premier < V127 et donc si on n'a pas trouvé de diviseurs premiers < V127, il n'y a aura pas non plus de diviseurs premiers de 127 > V127
 

 

 

[C8H10N4O2]

il y a 16 minutes, Black Jack a dit :

Salut,

 

Avec des mots.

si tu divises 127 par 3, 5 , 7 , ... et que ces divisions (par des nombres premiers successifs) ne donne aucune un résultat entier, c'est que 127 n'est pas divisible par 3, 5 , 7 ...

quand faut-il s'arrêter ?

V127 = 11,26...

Si on divise 127 par un nombre premier V127 = 11,26... (donc 13 , 17 , 19 ...), le résultat de la division est forcément inférieur à V127 = 11,26...

Et donc si 127 était divisible par un nombre premier > V127, il serait divisible par le résultat de la division qui serait un nombre entier < V127 ...
Mais l'algorithme a déjà essayé de diviser 127 par les nombres premier < V127 et donc si on n'a pas trouvé de diviseurs premiers < V127, il n'y a aura pas non plus de diviseurs premiers de 127 > V127
 

 

 

J'ai compris, merci beaucoup !