Exercices : nombres premiers et petit théorème de Fermat

Exercice 1

Réponse : 97

91 = 7 × 13, 51 = 3 × 17, 87 = 3 × 29. Pour 97, aucun des premiers 2, 3, 5, 7 (car 11² > 97) ne le divise.

Exercice 2

Réponse : 10

2, 3, 5, 7, 11, 13, 17, 19, 23, 29 : il y en a 10.

Exercice 3

Réponse : 2³ × 3² × 5

360 = 8 × 45 = 2³ × 3² × 5. Les autres écritures contiennent des facteurs non premiers (10, 45, 6).

Exercice 4

Réponse : Vrai

C’est un théorème démontré par Euclide, avec le nombre p₁ × … × pₙ + 1.

Exercice 5

Réponse : 13

221 n’est divisible ni par 2, 3, 5, 7, ni par 11 ; 221 = 13 × 17.

Exercice 6

Réponse : 1

13 est premier et ne divise pas 3 : par Fermat, 3¹³⁻¹ ≡ 1 [13].

Exercice 7

Réponse : 2

Fermat : 2⁶ ≡ 1 [7].

1. 100 = 6 × 16 + 4
2. 2¹⁰⁰ ≡ 2⁴ = 16 [7]
3. 16 ≡ 2 [7]

Exercice 8

Réponse : Si p est premier et ne divise pas a, alors a^p−1 ≡ 1 [p]

La deuxième proposition est la réciproque, fausse (341). La troisième est fausse pour a = p.

Exercice 9

Réponse : 24

Un diviseur s’écrit 2^a × 3^b × 5^c avec 4 choix pour a, 3 pour b, 2 pour c : 4 × 3 × 2 = 24.

Exercice 10

Exemple de réponse : Raisonnons par l’absurde : supposons qu’il n’existe qu’un nombre fini de nombres premiers p₁, …, pₙ.
Soit N = p₁ × p₂ × … × pₙ + 1. Comme N ≥ 2, N admet un diviseur premier, qui est l’un des pₖ.
pₖ divise N et p₁ × … × pₙ, donc il divise leur différence, 1. C’est impossible car pₖ ≥ 2.
Il existe donc une infinité de nombres premiers.

C’est la démonstration d’Euclide, au programme. Attention : N n’est pas forcément premier lui-même.

• Raisonnement par l’absurde posé.
• Construction de N.
• Contradiction : un premier divise 1.