Démontrer qu’un entier est premier
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Pour démontrer qu'un entier naturel $ n>1 $ est premier, on utilise la propriété suivante :
Si $ n $ n'est pas premier, alors il admet un diviseur premier $ p $ tel que $ p \leqslant \sqrt{n} $.
Il suffit donc de tester la divisibilité de $ n $ par tous les nombres premiers $ p $ vérifiant $ p \leqslant \sqrt{n} $ (c'est-à-dire $ p^{2} \leqslant n $) :
- Étape 1 : déterminer un majorant $ M $ de $ \sqrt{n} $ (par exemple $ \sqrt{120}<11 $).
- Étape 2 : lister les nombres premiers inférieurs ou égaux à $ M $.
- Étape 3 : vérifier qu'aucun d'entre eux ne divise $ n $ (en utilisant les critères de divisibilité ou la division euclidienne).
- Étape 4 : conclure que $ n $ est premier.
Remarque
Critères de divisibilité utiles :
- par $ 2 $ : le dernier chiffre est pair ;
- par $ 3 $ : la somme des chiffres est divisible par $ 3 $ ;
- par $ 5 $ : le dernier chiffre est $ 0 $ ou $ 5 $ ;
- par $ 11 $ : la somme alternée des chiffres est divisible par $ 11 $.
Pour les autres ($ 7 $, $ 13 $, $ 17 $...) : effectuer la division euclidienne.
Démontrer que 211 est premier
Étape 1 : on cherche un majorant de $ \sqrt{211} $.
Comme $ 14^{2}=196 $ et $ 15^{2}=225 $, on a $ 14<\sqrt{211}<15 $.
Il suffit donc de tester les nombres premiers inférieurs ou égaux à $ 14 $.
Étape 2 : les nombres premiers concernés sont : $ 2 $, $ 3 $, $ 5 $, $ 7 $, $ 11 $ et $ 13 $.
Étape 3 : on teste chacun d'eux.
- $ 211 $ est impair, donc non divisible par $ 2 $.
- Somme des chiffres : $ 2+1+1=4 $, non divisible par $ 3 $.
- Le dernier chiffre est $ 1 $, donc non divisible par $ 5 $.
- $ 211=7\times 30+1 $, non divisible par $ 7 $.
- Somme alternée : $ 2 - 1+1=2 $, non divisible par $ 11 $.
- $ 211=13\times 16+3 $, non divisible par $ 13 $.
Étape 4 : $ 211 $ n'a aucun diviseur premier inférieur ou égal à $ \sqrt{211} $, donc $ 211 $ est premier.
Étudier la primalité de 323
Étape 1 : $ 17^{2}=289 $ et $ 18^{2}=324 $, donc $ 17<\sqrt{323}<18 $.
Étape 2 : les nombres premiers à tester sont $ 2 $, $ 3 $, $ 5 $, $ 7 $, $ 11 $, $ 13 $ et $ 17 $.
Étape 3 : on teste rapidement.
- $ 323 $ est impair (pas divisible par $ 2 $), somme des chiffres $ 3+2+3=8 $ (pas par $ 3 $), dernier chiffre $ 3 $ (pas par $ 5 $).
- $ 323=7\times 46+1 $, non divisible par $ 7 $.
- Somme alternée $ 3 - 2+3=4 $, non divisible par $ 11 $.
- $ 323=13\times 24+11 $, non divisible par $ 13 $.
- $ 323=17\times 19 $ : on a trouvé un diviseur.
Étape 4 : $ 323 $ est divisible par $ 17 $, donc $ 323 $ n'est pas premier.
On a même $ 323=\color{red}{17\times 19}\color{black} $.
Attention
Ne pas confondre "tester $ p^{2} \leqslant n $" avec "tester $ p \leqslant \dfrac{n}{2} $" : la première condition limite la recherche aux diviseurs $ \leqslant \sqrt{n} $, ce qui est beaucoup plus rapide.
Tester $ \sqrt{n} $ et non $ n $ permet de réduire considérablement le nombre de divisions : pour $ n=211 $, on teste 6 nombres premiers au lieu de plus de 40.