Nombres premiers

1. Déterminer le plus grand entier \(m\) tel que \(m^2 \le n\) (la partie entière de \(\sqrt{n}\)).
2. Lister tous les nombres premiers \(p\) tels que \(p \le m\), c'est-à-dire tels que \(p^2 \le n\).
3. Tester la divisibilité de \(n\) par chacun de ces nombres premiers.
   • Si aucun de ces nombres ne divise \(n\), alors \(n\) est premier.
   • Si au moins l'un d'entre eux divise \(n\), alors \(n\) est composé.

1. Rejeter d'abord les nombres inférieurs à 2 : ils ne sont pas premiers, et la boucle n'en dirait rien puisqu'elle ne fait aucun tour.
2. Parcourir les diviseurs possibles à partir de 2, tant que k \(\times\) k \(\leqslant\) n.
3. Sortir au premier diviseur trouvé : un seul suffit à répondre non, et finir la boucle coûterait des tours pour rien.
4. Répondre oui après la boucle, qui n'est atteinte que si aucun diviseur n'a été trouvé.

Fonction is_prime(n)
    Si n < 2 alors
        Renvoyer faux
    Fin Si
    k ← 2
    Tant que k × k ≤ n
        Si reste de n par k = 0 alors
            Renvoyer faux
        Fin Si
        k ← k + 1
    Fin Tant que
    Renvoyer vrai
Fin Fonction

• Le nombre premier \(p\) est premier avec un entier \(a\) si et seulement si \(p\) ne divise pas \(a\).
• Si \(p\) divise un produit de nombres premiers \(q_1 q_2 \cdots q_k\), alors \(p\) est égal à l'un d'entre eux.
• Le nombre premier \(p\) est premier avec deux entiers \(a\) et \(b\) si et seulement s'il est premier avec leur produit \(ab\).

1. Placer le nombre en haut de l'arbre de facteurs.
2. Vérifier si le nombre est premier.
   1. Si le nombre est premier : L'entourer : la branche est terminée.
   2. Si le nombre est composé : Le décomposer en deux facteurs plus petits. Écrire ces deux facteurs comme des branches en dessous du nombre. Répéter l'étape 2 pour chacun de ces nouveaux facteurs.
3. La factorisation en nombres premiers est le produit de tous les nombres premiers entourés dans l'arbre.

1. Essayer les nombres premiers dans l'ordre croissant : \(2\), \(3\), \(5\), \(7\), \(11\), et ainsi de suite, en partant du quotient \(n\).
2. Avant chaque essai, comparer le carré du nombre premier à essayer au quotient courant : dès que le carré dépasse le quotient, s'arrêter ; ce quotient, s'il est différent de \(1\), est premier, et c'est le dernier facteur.
3. Sinon, diviser : si la division tombe juste, écrire le nouveau quotient et essayer de nouveau le même nombre premier ; sinon, passer au nombre premier suivant.

• Les diviseurs positifs de \(n\) sont exactement les entiers \(p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}\), où \(\beta_1, \dots, \beta_k\) sont des entiers naturels tels que \(0 \le \beta_i \le \alpha_i\) pour tout \(i\).
• Le nombre de diviseurs positifs de \(n\) est \((\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)\).

1. Décomposer les deux nombres \(a\) et \(b\) en produits de facteurs premiers.
2. Identifier les facteurs premiers communs aux deux décompositions.
3. Pour chaque facteur premier commun, retenir la puissance avec le plus petit exposant présent dans les deux décompositions.
4. Le PGCD est le produit de ces facteurs premiers communs élevés à leurs plus petits exposants respectifs.

1. Écrire la décomposition en facteurs premiers de \(a\) et de \(b\).
2. Identifier tous les facteurs premiers apparaissant dans au moins une des décompositions.
3. Pour chacun de ces facteurs, retenir le plus grand exposant observé.
4. Le PPCM est le produit de ces facteurs élevés à leurs plus grands exposants respectifs.

• Pour réduire une puissance modulo \(p\) d'un entier naturel \(a\) que \(p\) ne divise pas : écrire la division euclidienne de l'exposant, un entier naturel \(n\), par \(p - 1\) : \(n = (p - 1)q + r\) avec \(0 \le r < p - 1\). Comme \(a^{p-1} \equiv 1 \pmod{p}\), $$a^n = \left(a^{p-1}\right)^q \times a^r \equiv a^r \pmod{p}.$$
• Pour montrer que \(p\) divise \(a^p - a\), ou une expression qui s'y ramène : utiliser \(a^p \equiv a \pmod{p}\), valable pour tout entier naturel \(a\), sans condition.
• Pour montrer la divisibilité par un produit de nombres premiers distincts \(p_1 p_2 \cdots p_k\) : montrer la divisibilité par chaque \(p_i\) séparément, puis assembler de proche en proche avec le premier corollaire du théorème de Gauss. Le nombre premier \(p_{i+1}\) ne divise pas le produit \(p_1 \cdots p_i\) : sinon, d'après la propriété « Nombres premiers et produits », il serait égal à l'un des nombres \(p_1, \dots, p_i\). Un nombre premier qui ne divise pas un entier est premier avec lui, donc \(p_1 \cdots p_i\) et \(p_{i+1}\) sont premiers entre eux.