Nombre premier

📌 Un entier naturel supérieur ou égal à 2 est un nombre premier lorsqu'il possède exactement deux diviseurs positifs : 1 et lui-même.

• Par exemple, $7$ est un nombre premier car ses seuls diviseurs positifs sont : $$1 \quad \text{et} \quad 7$$
• $12$ n'est pas un nombre premier car il possède plus de deux diviseurs : $$1,\ 2,\ 3,\ 4,\ 6,\ 12$$
• Attention : $1$ n'est pas un nombre premier car il ne possède qu'un seul diviseur positif : lui-même.
• Attention : $0$ n'est pas un nombre premier car il possède une infinité de diviseurs. En effet, tout entier non nul divise $0$ puisque $$0=n\times 0.$$
• $2$ est le seul nombre premier pair.
• Tous les autres nombres premiers sont impairs.

📌 Il est utile de connaître les nombres premiers inférieurs à 20.

📌 Pour savoir si un entier $a$ est un nombre premier, il suffit de compter ses diviseurs.

• Pour savoir si un entier $a$ est un nombre premier, on peut chercher tous ses diviseurs compris entre $1$ et $a$.
  
  • S'il possède exactement deux diviseurs (1 et $a$), alors $a$ est premier.
  • Sinon (s'il possède moins de deux ou plus de deux diviseurs), alors $a$ n'est pas premier.
• Heureusement, il n'est pas nécessaire de tester tous les diviseurs jusqu'à $a$.
  
  Il suffit de chercher si $a$ possède un diviseur compris entre $2$ et $\sqrt{a}$.
  • Si un tel diviseur existe, alors $a$ n'est pas premier.
  • Sinon, $a$ est premier.

  📺 REGARDE LE COURS EN VIDÉO 👇
• Il est important de connaître les critères de divisibilité, car ils permettent de savoir rapidement si un nombre est divisible sans effectuer la division.
  👉 Divisible par 2 : le chiffre des unités est $0,\ 2,\ 4,\ 6$ ou $8$.
  
  👉 Divisible par 3 : la somme des chiffres est divisible par $3$.
  
  👉 Divisible par 5 : le chiffre des unités est $0$ ou $5$.
  
  👉 Divisible par 9 : la somme des chiffres est divisible par $9$.
• Exemple : $47$ est-il premier ? $$\sqrt{47}\approx6,9$$ Il suffit donc de tester les entiers compris entre $2$ et $6,9$ : $$2,\ 3,\ 4,\ 5,\ 6.$$

  47 n'est pas divisible par :

  • 2 car il n'est pas pair.
  • 3 car $4+7=11$ et $11$ n'est pas divisible par $3$.
  • 4 puisque $47$ n'est déjà pas divisible par $2$.
  • 5 car $47$ ne se termine ni par $0$ ni par $5$.
  • 6 puisque $47$ n'est déjà pas divisible par $3$.
  
  

  Donc 47 est un nombre premier.

👉 Pour montrer qu'un entier n'est pas premier, il suffit de trouver un seul diviseur différent de $1$ et de lui-même.
• Exemple : $51$ est-il premier ?
  
  51 est divisible par 3 car la somme des chiffres de $51$ vaut : $$5+1=6.$$
  
  Ainsi, $51$ possède un autre diviseur que $1$ et lui-même.
  
  Donc $51$ n'est pas un nombre premier.
👉 Conclusion : pour savoir si un entier $a$ est premier, commence par tester les critères de divisibilité (par 2, 3, 5, 9, ...).

👉 Ils permettent souvent de conclure très rapidement qu'un nombre n'est pas premier, sans avoir à effectuer de divisions.

💻 Savoir écrire un programme en Python qui détermine si un entier est premier ou non est un exercice très formateur.

• En Python, l'opérateur % (modulo) permet de connaître le reste de la division euclidienne.
• Par exemple : $$17\ \%\ 5 =2$$ car $$17=3\times5+2.$$
• Pour savoir si un entier $a$ est divisible par un autre $b$, il suffit de vérifier que le reste est égal à 0, ce qui s'écrit en Python :
  
  if $a$%$b~==~0$ :
• Pour savoir si un entier $a$ est premier ou non, on peut trouver avec un programme Python tous les diviseurs de $a$ grâce à l'instruction modulo(%) et donc savoir combien il y en a et donc savoir si $a$ est premier ou pas.

• Attention : $1$ n'est pas un nombre premier.
• Attention : $2$ est un nombre premier, même s'il est pair.
• Pour montrer qu'un nombre est premier, il ne faut pas tester tous les nombres jusqu'à $n$. Il suffit de tester jusqu'à $\sqrt n$.
• Pour montrer qu'un nombre n'est pas premier, il suffit de trouver un seul diviseur autre que $1$ et lui-même.