Exercices de PGCD et nombres premiers en maths Terminale (page 2)

42. $Une identité de Bézout à contrôler$

On considère les entiers

a = 7

b = 10

. Vérifier que

7 \times 53 + 10 \times (- 37) = 1

, puis conclure, à l'aide du théorème de Bézout, que

7

10

sont premiers entre eux.

Corrigé réservé aux abonnésVoir le corrigé

43. $Le nombre 157 est-il premier ?$

Le nombre

157

est-il premier ? Justifier en testant la divisibilité par les nombres premiers pertinents.

Voir le corrigé

Pour étudier la primalité de

157

, il suffit de tester les nombres premiers inférieurs ou égaux à

157

. Or

1 2^{2} = 144 < 157 < 169 = 1 3^{2}

, donc

157 < 13

: il suffit de tester

2

3

5

7

11

157

est impair, donc non divisible par

2

. La somme de ses chiffres vaut

1 + 5 + 7 = 13

, non divisible par

3

, donc

157

n'est pas divisible par

3

. Il ne se termine ni par

0

ni par

5

, donc non divisible par

5

. Ensuite

157 = 7 \times 22 + 3

: non divisible par

7

. Enfin

157 = 11 \times 14 + 3

: non divisible par

11

. Aucun nombre premier inférieur ou égal à

157

ne divise

157

, donc

157

est un nombre premier.

44. $Reste de 8 puissance 10 par le petit théorème de Fermat$

Le nombre

11

est premier et

8

n'est pas divisible par

11

. Déterminer, sans poser de grandes puissances, le reste de la division euclidienne de

8^{10}

par

11

Corrigé réservé aux abonnésVoir le corrigé

45. $PGCD de 352 et 165$

Déterminer le PGCD de

352

165

, puis indiquer si ces deux entiers sont premiers entre eux.

Corrigé réservé aux abonnésVoir le corrigé

46. $Le nombre 451 est-il premier ?$

Étudier la primalité du nombre

451

Corrigé réservé aux abonnésVoir le corrigé

47. $Euclide complet sur 697 et 492$

Déterminer le PGCD de

697

492

par l'algorithme d'Euclide, en rédigeant toutes les étapes, puis indiquer si la fraction

\frac{697}{492}

est irréductible. Si elle ne l'est pas, la simplifier.

Corrigé réservé aux abonnésVoir le corrigé

48. $Un couple de Bézout pour 437 et 361$

Calculer le PGCD de

437

361

par l'algorithme d'Euclide, puis déterminer, en remontant les divisions successives, un couple d'entiers

(u, v)

tel que

437 u + 361 v = 19

Corrigé réservé aux abonnésVoir le corrigé

49. $4n plus 3 et 7n plus 5 premiers entre eux$

Démontrer que pour tout entier naturel

n

, les entiers

4 n + 3

7 n + 5

sont premiers entre eux.

Corrigé réservé aux abonnésVoir le corrigé

50. $Un fournisseur et le théorème de Gauss$

Un fournisseur livre les cahiers d'une classe par cartons complets de

14

: le nombre total de cahiers livrés est un multiple de

14

. Chaque élève de la classe reçoit exactement

9

cahiers, si bien que le nombre total de cahiers vaut

9 n

, où

n

désigne le nombre d'élèves. Montrer que le nombre d'élèves est divisible par

14

Corrigé réservé aux abonnésVoir le corrigé

51. $PGCD et PPCM de 540 et 504 par décomposition$

Décomposer

540

504

en produits de facteurs premiers, puis en déduire leur PGCD et leur PPCM.

Corrigé réservé aux abonnésVoir le corrigé

52. $Résoudre 7x plus 4y égale 53 dans Z$

Résoudre dans

Z^{2}

l'équation diophantienne

7 x + 4 y = 53

, d'inconnues les entiers

x

y

Corrigé réservé aux abonnésVoir le corrigé

53. $Inverse de 17 modulo 39$

Démontrer que

17

39

sont premiers entre eux, déterminer l'inverse de

17

modulo

39

par l'algorithme d'Euclide étendu, puis résoudre la congruence

17 x \equiv 8 [39]

Corrigé réservé aux abonnésVoir le corrigé

54. $Nombres premiers entre 100 et 131$

En utilisant le crible d'Ératosthène, déterminer tous les nombres premiers compris entre

100

131

. Expliquer pourquoi il suffit d'éliminer les multiples des nombres premiers inférieurs ou égaux à

11

Corrigé réservé aux abonnésVoir le corrigé

55. $9n plus 4 et 12n plus 5 premiers entre eux$

Pour tout entier naturel

n

, les entiers

9 n + 4

12 n + 5

sont-ils premiers entre eux ? Justifier.

Corrigé réservé aux abonnésVoir le corrigé

56. $Résoudre une congruence modulo 26$

Résoudre la congruence

14 x \equiv 6 [26]

Corrigé réservé aux abonnésVoir le corrigé

57. $Résolution complète de 57x plus 40y égale 3$

Résoudre complètement dans

Z^{2}

l'équation diophantienne

57 x + 40 y = 3

: on étudiera l'existence de solutions, on déterminera une solution particulière par l'algorithme d'Euclide étendu, puis on déterminera l'ensemble des solutions.

Corrigé réservé aux abonnésVoir le corrigé

58. $Un code de colis et une clé modulo 13$

Un entrepôt code chaque colis par un nombre de six chiffres

N

qui doit vérifier

N \equiv 2 [13]

. Sur une étiquette endommagée, le code se compose d'un premier chiffre

5

, d'un deuxième chiffre inconnu

x

, puis des quatre chiffres

2839

. Déterminer le chiffre

x

pour que le code soit valide, puis écrire le code complet.

Corrigé réservé aux abonnésVoir le corrigé

59. $Chiffrement affine, de la clé au déchiffrement$

Un message en lettres majuscules est chiffré lettre par lettre : chaque lettre est d'abord codée par son rang

x

dans l'alphabet (

A = 0

B = 1

, ...,

Z = 25

), puis remplacée par la lettre de rang

y

tel que

y \equiv 7 x + 3 [26]

. Justifier que ce chiffrement est inversible, déterminer la fonction de déchiffrement, puis chiffrer le mot CRYPTE.

Corrigé réservé aux abonnésVoir le corrigé

60. $Reste de 3 puissance 421 modulo 17$

Déterminer le reste de la division euclidienne de

3^{421}

par

17

Corrigé réservé aux abonnésVoir le corrigé

61. $Le cinquième nombre de Fermat n'est pas premier$

Pour tout entier

n ⩾ 0

, on pose

F_{n} = 2^{2^{n}} + 1

(nombres de Fermat). On a

F_{0} = 3

F_{1} = 5

F_{2} = 17

F_{3} = 257

F_{4} = 65537

, tous premiers. Fermat conjecturait que tous les

F_{n}

sont premiers ; Euler a montré que

641

divise

F_{5}

Q1-Vérifier que

641 = 5 \times 2^{7} + 1

et que

641 = 5^{4} + 2^{4}

Q2-

Corrigé réservé aux abonnésVoir le corrigé

62. $Divisible par 16 et par 27 : le corollaire de Gauss$

Le nombre

N

de bonbons d'un sac géant est divisible par

16

et par

27

Q1-Montrer que

16

27

sont premiers entre eux, en exhibant une identité de Bézout.

Q2-Montrer que

N

est divisible par

432

Q3-Sachant que le sac contient entre

400

500

bonbons, déterminer

N

Corrigé réservé aux abonnésVoir le corrigé

63. $Deux congruences à modules 7 et 11$

Déterminer tous les entiers

x

vérifiant simultanément

x \equiv 3 [7]

x \equiv 5 [11]

. On écrira d'abord une identité de Bézout entre

7

11

, puis on construira une solution explicite.

Corrigé réservé aux abonnésVoir le corrigé

64. $Racines rationnelles d'un polynôme de degré 3$

On considère le polynôme

P (x) = 2 x^{3} - 3 x^{2} - 3 x + 2

, à coefficients entiers.

Q1-Montrer que si une fraction irréductible

\frac{p}{q}

est racine de

P

, alors

p

divise

2

q

divise

2

Q2-Lister toutes les racines rationnelles candidates, puis déterminer les racines rationnelles de

P

Q3-Factoriser

P

en produit de facteurs du premier degré à coefficients rationnels.

Corrigé réservé aux abonnésVoir le corrigé

65. $Trois solutions pour une congruence modulo 123$

Résoudre la congruence

51 x \equiv 87 [123]

Corrigé réservé aux abonnésVoir le corrigé

66. $Un nombre de Mersenne composé$

Le nombre

23

est premier. On se demande si le nombre de Mersenne

2^{23} - 1 = 8388607

est premier.

Q1-Calculer

2^{10}

, puis

2^{20}

, puis

2^{23}

modulo

47

Q2-En déduire que

47

divise

2^{23} - 1

, puis conclure sur la primalité de

2^{23} - 1

Q3-L'affirmation « si

p

est premier alors

2^{p} - 1

est premier » est-elle vraie ? Justifier.

Corrigé réservé aux abonnésVoir le corrigé

67. $Si un nombre premier divise un produit$

Démontrer la propriété suivante, utile entre autres pour la décomposition en facteurs premiers : si

p

est un nombre premier et si

p

divise un produit

ab

d'entiers, alors

p

divise

a

p

divise

b

Q1-Montrer que si

p

ne divise pas

a

, alors

p

a

sont premiers entre eux.

Q2-Conclure à l'aide du théorème de Gauss.

Corrigé réservé aux abonnésVoir le corrigé

68. $Carrés premiers entre eux$

Soient

a

b

deux entiers. Démontrer que

a

b

sont premiers entre eux si et seulement si

a^{2}

b^{2}

sont premiers entre eux.

Q1-Montrer que si un nombre premier

p

divise

a^{2}

, alors

p

divise

a

Q2-Montrer que si

a^{2}

b^{2}

ne sont pas premiers entre eux, alors

a

b

ne sont pas premiers entre eux. En déduire que si

a

b

sont premiers entre eux, alors

a^{2}

b^{2}

le sont aussi.

Q3-Réciproquement, montrer que si

a

b

ne sont pas premiers entre eux, alors

a^{2}

b^{2}

ne le sont pas non plus.

Corrigé réservé aux abonnésVoir le corrigé

69. $Un chiffrement de Hill et son déchiffrement$

On chiffre un message en lettres majuscules par paires de lettres, chaque lettre étant codée par son rang (

A = 0

B = 1

, ...,

Z = 25

). Le couple

(x, y)

est transformé en le couple

(x^{'}, y^{'})

tel que

x^{'} \equiv 2 x + 3 y [26]

y^{'} \equiv 7 x + 5 y [26]

, les rangs étant pris entre

0

25

Q1-Justifier que ce chiffrement est inversible en étudiant le déterminant de la matrice

(2735)

Q2-Chiffrer le mot CIBLES.

Q3-Déterminer la matrice de déchiffrement et vérifier son effet sur la première paire chiffrée.

Corrigé réservé aux abonnésVoir le corrigé

70. $Un petit système RSA avec 11 et 17$

Pour illustrer le système RSA, on choisit les nombres premiers

p = 11

q = 17

, et la clé publique d'exposant

e = 7

. On veut chiffrer le message

m = 12

Q1-Calculer

n = pq

φ = (p - 1) (q - 1)

, puis vérifier que

e = 7

convient comme exposant.

Q2-Déterminer l'exposant de déchiffrement

d

tel que

e d \equiv 1 [φ]

Q3-Chiffrer le message

m = 12

: calculer

c \equiv m^{e} [n]

avec

0 ⩽ c < n

Q4-Vérifier, à l'aide du petit théorème de Fermat, que

c^{d} \equiv m [n]

Corrigé réservé aux abonnésVoir le corrigé

71. $Une équation diophantienne à solution unique$

Pour une séance, un théâtre propose des places à plein tarif à

29

€ et des places à tarif réduit à

17

€. À la fin de la séance, la recette s'élève exactement à

223

€ et toutes les places vendues ont été payées (chaque place vendue est soit à plein tarif, soit à tarif réduit). Déterminer toutes les répartitions possibles du nombre de places vendues.

Corrigé réservé aux abonnésVoir le corrigé

72. $Une suite d'entiers et le PGCD de ses termes consécutifs$

Pour tout entier naturel

n

, on pose

a_{n} = 2 \times 4^{n} + 1

Q1-Calculer

a_{0}

a_{1}

a_{2}

Q2-Montrer que pour tout entier naturel

n

a_{n}

est divisible par

3

Q3-Montrer que pour tout entier naturel

n

, le PGCD de

a_{n}

a_{n + 1}

vaut

3

Q4-Décomposer

a_{4}

en produit de facteurs premiers, puis déterminer tous les termes de la suite qui sont des nombres premiers.

Corrigé réservé aux abonnésVoir le corrigé

73. $Pourquoi l'algorithme d'Euclide calcule le PGCD$

Soient

a

b

deux entiers avec

b > 0

, et soit

r

le reste de la division euclidienne de

a

par

b

a = b q + r

avec

0 ⩽ r < b

. Démontrer que le PGCD de

a

b

est égal au PGCD de

b

r

. En déduire une justification de l'algorithme d'Euclide : montrer que le dernier reste non nul obtenu par les divisions successives est bien le PGCD de

a

b

Corrigé réservé aux abonnésVoir le corrigé

74. $Deux congruences simultanées : le lemme chinois$

Soient

m

n

deux entiers supérieurs ou égaux à

2

, premiers entre eux, et

r_{1}

r_{2}

deux entiers. On considère le système de congruences

x \equiv r_{1} [m]

x \equiv r_{2} [n]

Q1-Justifier l'existence d'entiers

u

v

tels que

m u + n v = 1

, puis montrer que

x_{0} = r_{2} \times m u + r_{1} \times n v

est solution du système.

Corrigé réservé aux abonnésVoir le corrigé

75. $PGCD de 902 et 418 par l'algorithme d'Euclide$

Calculer le PGCD de

902

418

en détaillant toutes les divisions successives de l'algorithme d'Euclide.

Corrigé réservé aux abonnésVoir le corrigé

76. $432 et 175 sont-ils premiers entre eux ?$

Les entiers

432

175

sont-ils premiers entre eux ? Justifier à l'aide de l'algorithme d'Euclide.

Corrigé réservé aux abonnésVoir le corrigé

77. $Contrôler une identité de Bézout pour 52 et 36$

On considère les entiers

a = 52

b = 36

.
(

Q1-Calculer

52 \times (- 2) + 36 \times 3

Q2-Déterminer le PGCD de

52

36

par l'algorithme d'Euclide

Q3-La relation obtenue constitue-t-elle une identité de Bézout pour

52

36

Corrigé réservé aux abonnésVoir le corrigé

78. $Décomposer 3720 en facteurs premiers$

Décomposer

3720

en produit de facteurs premiers, en détaillant les divisions successives.

Corrigé réservé aux abonnésVoir le corrigé

79. $Le nombre 371 est-il premier ?$

Le nombre

371

est-il premier ? Justifier en bornant explicitement les essais de divisibilité.

Corrigé réservé aux abonnésVoir le corrigé

80. $Reste de 2 puissance 18 dans la division par 19$

Quel est le reste de la division euclidienne de

2^{18}

par

19

? Justifier à l'aide du petit théorème de Fermat.

Corrigé réservé aux abonnésVoir le corrigé

41.

42.Une identité de Bézout à contrôler

43.Le nombre 157 est-il premier ?

44.Reste de 8 puissance 10 par le petit théorème de Fermat

45.PGCD de 352 et 165

46.Le nombre 451 est-il premier ?

47.Euclide complet sur 697 et 492

48.Un couple de Bézout pour 437 et 361

49.4n plus 3 et 7n plus 5 premiers entre eux

50.Un fournisseur et le théorème de Gauss

51.PGCD et PPCM de 540 et 504 par décomposition

52.Résoudre 7x plus 4y égale 53 dans Z

53.Inverse de 17 modulo 39

54.Nombres premiers entre 100 et 131

55.9n plus 4 et 12n plus 5 premiers entre eux

56.Résoudre une congruence modulo 26

57.Résolution complète de 57x plus 40y égale 3

58.Un code de colis et une clé modulo 13

59.Chiffrement affine, de la clé au déchiffrement

60.Reste de 3 puissance 421 modulo 17

61.Le cinquième nombre de Fermat n'est pas premier

62.Divisible par 16 et par 27 : le corollaire de Gauss

63.Deux congruences à modules 7 et 11

64.Racines rationnelles d'un polynôme de degré 3

65.Trois solutions pour une congruence modulo 123

66.Un nombre de Mersenne composé

67.Si un nombre premier divise un produit

68.Carrés premiers entre eux

69.Un chiffrement de Hill et son déchiffrement

70.Un petit système RSA avec 11 et 17

71.Une équation diophantienne à solution unique

72.Une suite d'entiers et le PGCD de ses termes consécutifs

73.Pourquoi l'algorithme d'Euclide calcule le PGCD

74.Deux congruences simultanées : le lemme chinois

75.PGCD de 902 et 418 par l'algorithme d'Euclide

76.432 et 175 sont-ils premiers entre eux ?

77.Contrôler une identité de Bézout pour 52 et 36

78.Décomposer 3720 en facteurs premiers

79.Le nombre 371 est-il premier ?

80.Reste de 2 puissance 18 dans la division par 19

42. $Une identité de Bézout à contrôler$

43. $Le nombre 157 est-il premier ?$

44. $Reste de 8 puissance 10 par le petit théorème de Fermat$

45. $PGCD de 352 et 165$

46. $Le nombre 451 est-il premier ?$

47. $Euclide complet sur 697 et 492$

48. $Un couple de Bézout pour 437 et 361$

49. $4n plus 3 et 7n plus 5 premiers entre eux$

50. $Un fournisseur et le théorème de Gauss$

51. $PGCD et PPCM de 540 et 504 par décomposition$

52. $Résoudre 7x plus 4y égale 53 dans Z$

53. $Inverse de 17 modulo 39$

54. $Nombres premiers entre 100 et 131$

55. $9n plus 4 et 12n plus 5 premiers entre eux$

56. $Résoudre une congruence modulo 26$

57. $Résolution complète de 57x plus 40y égale 3$

58. $Un code de colis et une clé modulo 13$

59. $Chiffrement affine, de la clé au déchiffrement$

60. $Reste de 3 puissance 421 modulo 17$

61. $Le cinquième nombre de Fermat n'est pas premier$

62. $Divisible par 16 et par 27 : le corollaire de Gauss$

63. $Deux congruences à modules 7 et 11$

64. $Racines rationnelles d'un polynôme de degré 3$

65. $Trois solutions pour une congruence modulo 123$

66. $Un nombre de Mersenne composé$

67. $Si un nombre premier divise un produit$

68. $Carrés premiers entre eux$

69. $Un chiffrement de Hill et son déchiffrement$

70. $Un petit système RSA avec 11 et 17$

71. $Une équation diophantienne à solution unique$

72. $Une suite d'entiers et le PGCD de ses termes consécutifs$

73. $Pourquoi l'algorithme d'Euclide calcule le PGCD$

74. $Deux congruences simultanées : le lemme chinois$

75. $PGCD de 902 et 418 par l'algorithme d'Euclide$

76. $432 et 175 sont-ils premiers entre eux ?$

77. $Contrôler une identité de Bézout pour 52 et 36$

78. $Décomposer 3720 en facteurs premiers$

79. $Le nombre 371 est-il premier ?$

80. $Reste de 2 puissance 18 dans la division par 19$