Division euclidienne
-
Franck
Division euclidienne
Bonjour ! J'aimerai savoir combien de division euclidienne faut il écrire pour prouver que 1069 soit premier ? A première vu j'aurais dis 2 car un nombre premier est divisible par 1 et lui même mais j'ai un doute merci d'avance (:
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: Division euclidienne
Bonjour,
Une seule division ne suffit pas, il faudrait a priori le faire pour tous les entiers inférieurs ou égaux à \(\sqrt{1069}\approx 33\) : en effet si 1069 est divisible alors il s'écrit \(1069=m\times n\) et l'un des deux facteurs est nécessairement inférieur à la racine carrée de 1069.
Après, on peut gagner du temps avec les multiples :
on pose la division par 2 : elle ne tombe pas juste donc le nombre n'est pas divisible par 2 donc par aucun autre entier pair : on raye ces nombres
on pose la division par 5 : elle ne tombe pas juste donc le nombre n'est pas divisible par 3 donc par aucun autre multiple de 3 : on raye ces nombres
on pose la division par 7 : elle ne tombe pas juste donc le nombre n'est pas divisible par 5 donc par aucun autre multiple de 5 : on raye ces nombres
Et on continue avec les nombres non rayés, ce qui correspond aux nombres premiers.
Tout cela pour te dire que tout nombre entier se décompose comme produit de nombres premiers, donc il suffit de tester les divisions par les nombres premiers inférieurs à 33.
Bon courage
Une seule division ne suffit pas, il faudrait a priori le faire pour tous les entiers inférieurs ou égaux à \(\sqrt{1069}\approx 33\) : en effet si 1069 est divisible alors il s'écrit \(1069=m\times n\) et l'un des deux facteurs est nécessairement inférieur à la racine carrée de 1069.
Après, on peut gagner du temps avec les multiples :
on pose la division par 2 : elle ne tombe pas juste donc le nombre n'est pas divisible par 2 donc par aucun autre entier pair : on raye ces nombres
on pose la division par 5 : elle ne tombe pas juste donc le nombre n'est pas divisible par 3 donc par aucun autre multiple de 3 : on raye ces nombres
on pose la division par 7 : elle ne tombe pas juste donc le nombre n'est pas divisible par 5 donc par aucun autre multiple de 5 : on raye ces nombres
Et on continue avec les nombres non rayés, ce qui correspond aux nombres premiers.
Tout cela pour te dire que tout nombre entier se décompose comme produit de nombres premiers, donc il suffit de tester les divisions par les nombres premiers inférieurs à 33.
Bon courage