Kala te souhaite la bienvenueKalaMaths

Nombres premiers et petit théorème de Fermat

🔴 Expert

Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.

S'abonner
Débloquer ce chapitre – 2,99 €

Cet achat est réservé à un adulte.

  1. 1

    On travaille modulo 7.
    a) Calculer successivement 3¹, 323^{2}, 333^{3}, 343^{4}, 3⁵, 3⁶ modulo 7 et en déduire l'ordre de 3 modulo 7.
    b) Justifier que 3 est une racine primitive modulo 7.
    c) Déterminer le reste de 3¹⁰⁰⁰ dans la division par 7.
    d) Résoudre 3x≡5[7]3^x \equiv 5 [7] d'inconnue l'entier naturel x.

    Reste de 3ⁿ modulo 7??????n123456× 3On passe d'une case à la suivante en multipliant par 3.
    Voir le corrigéoffert

    a) 31≡33^{1} \equiv 3 ; 32=9≡23^{2} = 9 \equiv 2 ; 33≡3×2=63^{3} \equiv 3\times 2 = 6 ; 34≡3×6=18≡43^{4} \equiv 3\times 6 = 18 \equiv 4 ; 35≡3×4=12≡53^{5} \equiv 3\times 4 = 12 \equiv 5 ; 36≡3×5=15≡1[7]3^{6} \equiv 3\times 5 = 15 \equiv 1 [7].
    La première puissance égale à 1 est la 6ᵉ : l'ordre de 3 modulo 7 est 6.
    b) Les restes obtenus 3, 2, 6, 4, 5, 1 sont exactement tous les restes non nuls modulo 7 (1 à 6). Comme 3 engendre tous ces restes, 3 est une racine primitive modulo 7.
    c) Comme 36≡1[7]3^{6} \equiv 1 [7], on réduit l'exposant modulo 6 : 1000=6×166+41000 = 6 \times 166 + 4. Donc 31000≡34≡4[7]3^{1000} \equiv 3^{4} \equiv 4 [7]. Le reste est 4.
    d) D'après le tableau, 35≡5[7]3^{5} \equiv 5 [7]. Comme les puissances de 3 sont périodiques de période 6, on a 3x≡5[7]3^x \equiv 5 [7] ⟺ x≡5[6]x \equiv 5 [6].

  2. 2

    Déterminer tous les couples d'entiers naturels (a ;
    b) avec a≤ba \le b tels que PGCD(a ;
    b) =6= 6 et PPCM(a ;
    b) =90= 90.
    a) Justifier la méthode utilisée.
    b) Donner tous les couples et vérifier.

    Voir le corrigéoffert

    a) Notons d=PGCD(a ; b)=6d = PGCD(a \,;\, b) = 6. On écrit a=6a′a = 6a' et b=6b′b = 6b' avec PGCD(a′ ; b′)=1PGCD(a' \,;\, b') = 1.
    On sait que a×b=PGCD×PPCMa \times b = PGCD \times PPCM, donc 36 a′b′=6×90=54036\,\text{a}'b' = 6 \times 90 = 540, d'où a′b′=15a'b' = 15.
    Ainsi il faut trouver les couples (a' ; b') d'entiers premiers entre eux, avec a′≤b′a' \le b' et a′b′=15a'b' = 15.
    b) Les factorisations de 15 en facteurs premiers entre eux, avec a′≤b′a' \le b' : (1 ; 15)(1 \,;\, 15) et (3 ; 5)(3 \,;\, 5). (Le couple (a′=1,b′=15)(a'=1, b'=15) et (a′=3,b′=5)(a'=3, b'=5) sont bien premiers entre eux.)
    Cela donne (a ; b)=(6 ; 90)(a \,;\, b) = (6 \,;\, 90) et (a ; b)=(18 ; 30)(a \,;\, b) = (18 \,;\, 30).
    Pour en être sûr : PGCD(6 ; 90)=6PGCD(6 \,;\, 90) = 6 et PPCM(6 ; 90)=90PPCM(6 \,;\, 90) = 90. ✓ PGCD(18 ; 30)=6PGCD(18 \,;\, 30) = 6 et PPCM(18 ; 30)=90PPCM(18 \,;\, 30) = 90.

    8 corrigés détaillés pas à pas restent à débloquer

    Chacun reprend l'énoncé, montre le calcul étape par étape et dit où se trouve le piège.

    Le pack de révision, gratuit

    L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.

    Si tu as moins de 15 ans, demande à un parent de remplir ce formulaire avec son adresse.

  3. 3

    On s'intéresse aux nombres de la forme 2n−12^{n} - 1. a) Montrer que si 2n−12^{n} - 1 est premier, alors n est premier. (On pourra utiliser l'identité 2ab−1=(2a−1)((2a)b−1+(2a)b−2+⋯+1)2^{ab} - 1 = (2^a - 1)((2^a)^{b-1} + (2^a)^{b-2} + \dots + 1).) b) La réciproque est-elle vraie ? On étudiera le cas n=11n = 11.

    🔒 Corrigé détailléVoir ce qu'il contient →
  4. 4

    On veut déterminer le reste de 2⁷⁰ dans la division par 77, sachant que 77=7×1177 = 7 \times 11.
    a) Déterminer le reste de 2⁷⁰ modulo 7.
    b) Déterminer le reste de 2⁷⁰ modulo 11.
    c) Déterminer le reste de 2⁷⁰ modulo 77.

    🔒 Corrigé détailléVoir ce qu'il contient →
  5. 5

    On veut montrer qu'il existe une infinité de nombres premiers congrus à 3 modulo 4.
    a) Montrer que tout entier N≥2N \ge 2 impair congru à 3 modulo 4 possède au moins un facteur premier congru à 3 modulo 4.
    b) On suppose qu'il n'existe qu'un nombre fini de tels premiers q1q_{1}, …, qmq_m (dont 3). En considérant N=4(q1×⋯×qm)−1N = 4(q_{1}\times \dots \times q_m) - 1, montrer qu'on aboutit à une contradiction.

    🔒 Corrigé détailléVoir ce qu'il contient →
  6. 6

    Le but est de démontrer que pour tout entier n, 30 divise n5−nn^{5} - n.
    a) Rappeler pourquoi, pour p premier et PGCD(a ; p)=1PGCD(a \,;\, p) = 1, on a ap≡a[p]a^p \equiv a [p], puis montrer que cette congruence reste vraie si p divise a.
    b) En déduire que n5−nn^{5} - n est divisible par 2, par 3 et par 5.
    c) Démontrer que 30 divise n5−nn^{5} - n pour tout entier n.

    🔒 Corrigé détailléVoir ce qu'il contient →
  7. 7

    On considère l'entier 2025.
    a) Décomposer 2025 en produit de facteurs premiers et donner son nombre de diviseurs.
    b) Combien de diviseurs de 2025 sont des carrés parfaits ?
    c) Combien de diviseurs de 2025 sont des multiples de 15 ?

    🔒 Corrigé détailléVoir ce qu'il contient →
  8. 8

    Soit p un nombre premier avec p>3p > 3. Démontrer que p2≡1[24]p^{2} \equiv 1 [24].
    a) Montrer que 8 divise p2−1p^{2} - 1.
    b) Montrer que 3 divise p2−1p^{2} - 1.
    c) Démontrer que p2≡1[24]p^{2} \equiv 1 [24].

    🔒 Corrigé détailléVoir ce qu'il contient →
  9. 9

    Chiffrement RSA complet avec p=5p = 5 et q=11q = 11. On pose n=p×qn = p\times q et on choisit e=3e = 3.
    a) Calculer n et φ(n)=(p−1)(q−1)\varphi (n) = (p-1)(q-1).
    b) Déterminer la clé privée d telle que 3d≡1[φ(n)]3d \equiv 1 [\varphi (n)].
    c) Chiffrer le message m=7m = 7.
    d) Déchiffrer le message chiffré et vérifier qu'on remonte bien à m=7m = 7 (on pourra travailler modulo 5 et modulo 11).

    🔒 Corrigé détailléVoir ce qu'il contient →
  10. 10

    On étudie l'entier 561.
    a) Décomposer 561 en produit de facteurs premiers.
    b) Soit a un entier premier avec 561. En raisonnant modulo 3, modulo 11 et modulo 17, montrer que a560≡1a^{560} \equiv 1 modulo chacun de ces trois nombres.
    c) Montrer que a560≡1[561]a^{560} \equiv 1 [561] pour tout a premier avec 561, bien que 561 ne soit pas premier.

    🔒 Corrigé détailléVoir ce qu'il contient →

Comment ça s'est passé ?

Retrouve tout dans Mon suivi.

Le pack de révision, gratuit

L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.

Si tu as moins de 15 ans, demande à un parent de remplir ce formulaire avec son adresse.

Partager avec ma classe

Les énoncés de cette page sont gratuits et s'ouvrent sans compte : l'adresse peut être donnée telle quelle, au tableau ou dans l'espace numérique de travail.