Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.
Tu es hors ligne : les chapitres enregistrés fonctionnent toujours.
Toutes les leçons du thème, de la première année à la dernière, prêtes pour le papier. Les séries d'exercices sont notées A, B, C… et corrigées à la fin.
Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.
Nombres et calculs
Arithmétique
PseudoDate
Scanne pour ouvrir en ligneenglish.sedifier.com/fr/branch/n/ari/print/
1. Divisibilité et division euclidienne
Échauffement
Trois questions rapides sur des leçons déjà vues.
Un rectangle a pour sommets (−3;6), (5;6), (5;−3) et (−3;−3).
Sa largeur (côté horizontal) : ?
Sa hauteur (côté vertical) : ?
Son périmètre : ?
Ce rectangle est la base d'un prisme droit de hauteur 4. Son volume :
La distance du sommet (−3;6) à l'axe des ordonnées est ∣−3∣ :
On empile des prismes de hauteur 4 et de hauteur 5 en deux tours. La plus petite hauteur commune :
Quel est le PGCD de 10 et 14 ?
Quel est le PPCM de 4 et 14 ?
Découvrir
Lequel de ces nombres divise 12 ?
3
24
L'idée clé
Dans Z, on parle de multiples et de diviseurs.
adiviseb s'il existe un entier k tel que b=ka. Si a divise b et c, alors a divise ub+vc.
Division euclidienne de a par b≥1 : il existe un unique couple (q;r) tel que a=bq+r et 0≤r<b.
Exemple corrigé
Effectue la division euclidienne de −17 par 5.
−17=5×(−4)+3
On cherche un reste positif.
q=−4, r=3
0 ≤ 3 < 5 : c'est bon.
À toi, guidé
À toi : quel est le reste de la division de 23 par 4 ?
3
23 = 4 × 5 + 3.
Entraînement ★
Quel est le reste de la division euclidienne de 14 par 3 ?
Quel est le reste de la division euclidienne de 293 par 11 ?
Quel est le reste de la division euclidienne de 10 par 3 ?
Attention !
Entraînement ★★
Quel est le reste de la division euclidienne de −10 par 4 ?
Quel est le reste de la division euclidienne de −15 par 4 ?
On sait que 9 divise x et y. Quel nombre 9 divise-t-il toujours ?
7x+4y
x+1
yx
Quel est le quotient de la division euclidienne de 22 par 5 ?
Bilan
Trois questions pour vérifier que c'est acquis.
Quel est le reste de la division euclidienne de 14 par 3 ?
Quel est le reste de la division euclidienne de 293 par 11 ?
Quel est le reste de la division euclidienne de 10 par 3 ?
Fiche résumé
Division euclidienne
a=bq+r, avec 0≤r<b.
a∣b signifie b=ka.
Attention : le reste n'est jamais négatif.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Le reste de la division euclidienne de x par 11 est 1. Quel est le reste de la division de 3x par 11 ?
2. Congruences
Échauffement
Trois questions rapides sur des leçons déjà vues.
Quel est le reste de la division euclidienne de 14 par 3 ?
Quel est le reste de la division euclidienne de −10 par 4 ?
On sait que 9 divise x et y. Quel nombre 9 divise-t-il toujours ?
7x+4y
x+1
yx
Découvrir
Il est 22 h. Quelle heure sera-t-il dans 5 heures ?
3 h
27 h
L'idée clé
Deux entiers sont congrus s'ils ont le même reste.
a≡b[n] signifie que n divise a−b.
On peut additionner, multiplier et élever à une puissance : si a≡b[n] et c≡d[n], alors a+c≡b+d, ac≡bd et ak≡bk[n].
Exemple corrigé
Quel est le reste de la division de 7100 par 5 ?
7≡2[5]
On réduit.
24≡1[5]
2⁴ = 16 ≡ 1.
7100≡(24)25≡1[5]
100 = 4 × 25.
À toi, guidé
À toi : réduis 38 modulo 7.
3
38 = 7 × 5 + 3.
Entraînement ★
Quel est le plus petit entier positif x tel que 21≡x[5] ?
Quel est le plus petit entier positif x tel que 399≡x[15] ?
Quel est le plus petit entier positif x tel que 16≡x[3] ?
Attention !
Entraînement ★★
Quel est le reste de la division de 28 par 5 ?
Quel est le reste de la division de 2160 par 5 ?
On sait que x≡2[9] et y≡1[9]. Quel est le reste de x+y modulo 9 ?
Quel est le reste de la division de 102 par 11 ?
Bilan
Trois questions pour vérifier que c'est acquis.
Quel est le plus petit entier positif x tel que 21≡x[5] ?
Quel est le plus petit entier positif x tel que 399≡x[15] ?
Quel est le plus petit entier positif x tel que 16≡x[3] ?
Fiche résumé
Congruences
a≡b[n]⟺n∣a−b.
On additionne, on multiplie, on élève à une puissance.
Attention : on ne divise pas dans une congruence.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Quel est le chiffre des unités de 717 ?
3. PGCD et algorithme d'Euclide
Échauffement
Trois questions rapides sur des leçons déjà vues.
Quel est le reste de la division euclidienne de 14 par 3 ?
Quel est le reste de la division euclidienne de −10 par 4 ?
On sait que 9 divise x et y. Quel nombre 9 divise-t-il toujours ?
7x+4y
x+1
yx
Découvrir
Quel est le plus grand diviseur commun à 12 et 18 ?
6
36
L'idée clé
L'algorithme d'Euclide répète des divisions euclidiennes.
PGCD(a;b)=PGCD(b;r), où r est le reste de la division de a par b. Le PGCD est le dernier reste non nul.
a et b sont premiers entre eux si PGCD(a;b)=1.
Exemple corrigé
Calcule PGCD(252;105).
PGCD(105;42)
252 = 105 × 2 + 42.
PGCD(42;21)
105 = 42 × 2 + 21.
21
42 = 21 × 2 + 0.
À toi, guidé
À toi : calcule PGCD(35;14).
7
35 = 14 × 2 + 7, 14 = 7 × 2.
Entraînement ★
Calcule PGCD(21;24).
Calcule PGCD(350;400).
Calcule PGCD(14;16).
Attention !
Entraînement ★★
Les nombres 5 et 6 sont-ils premiers entre eux ?
Oui, toujours
Seulement s'ils sont premiers
Non
Les nombres 2 et 3 sont-ils premiers entre eux ?
Oui, toujours
Seulement s'ils sont premiers
Non
Calcule PGCD(12;4).
Dans l'algorithme d'Euclide pour 17 et 7, on remplace le couple par (7 ; r). Que vaut r ?
Bilan
Trois questions pour vérifier que c'est acquis.
Calcule PGCD(21;24).
Calcule PGCD(350;400).
Calcule PGCD(14;16).
Fiche résumé
PGCD
PGCD(a;b)=PGCD(b;r).
Dernier reste non nul.
Attention : ne confonds pas avec le dernier quotient.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Calcule PGCD(108;162).
4. Théorème de Bézout
Échauffement
Trois questions rapides sur des leçons déjà vues.
Calcule PGCD(21;24).
Les nombres 5 et 6 sont-ils premiers entre eux ?
Oui, toujours
Seulement s'ils sont premiers
Non
Calcule PGCD(12;4).
Découvrir
On a 3×2+5×(−1)=1. Que peut-on dire de 3 et 5 ?
Ils sont premiers entre eux
Ils ont 2 pour diviseur commun
L'idée clé
Le théorème relie PGCD et combinaisons linéaires.
Bézout :a et b sont premiers entre eux si et seulement s'il existe des entiers u et v tels que au+bv=1.
Plus généralement, il existe u et v tels que au+bv=PGCD(a;b).
Exemple corrigé
Trouve un couple (u;v) tel que 7u+3v=1.
7=3×2+1
Euclide.
1=7×1+3×(−2)
On isole 1.
(u;v)=(1;−2)
On lit.
À toi, guidé
À toi : avec 5u+2v=1 et u=1, que vaut v ?
−2
5 + 2v = 1.
Entraînement ★
On a 7×1+3×v=1. Que vaut v ?
On a 77×1+38×v=1. Que vaut v ?
On a 9×1+4×v=1. Que vaut v ?
Attention !
Entraînement ★★
Existe-t-il des entiers u et v tels que 12u+24v=1 ?
Non, car le PGCD n'est pas 1
Oui, toujours
Oui, avec u=v=1
Existe-t-il des entiers u et v tels que 10u+20v=1 ?
Non, car le PGCD n'est pas 1
Oui, toujours
Oui, avec u=v=1
Avec u=1 et v=−2, que vaut (5)u+2v ?
Selon le théorème de Bézout, que signifie l'existence d'entiers u, v tels que au+bv=1 ?
a et b sont premiers entre eux
a divise b
a et b sont des nombres premiers
Bilan
Trois questions pour vérifier que c'est acquis.
On a 7×1+3×v=1. Que vaut v ?
On a 77×1+38×v=1. Que vaut v ?
On a 9×1+4×v=1. Que vaut v ?
Fiche résumé
Bézout
au+bv=1⟺PGCD(a;b)=1.
On remonte l'algorithme d'Euclide.
Attention : le couple (u;v) n'est pas unique.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
On cherche u et v entiers tels que 13u+8v=1. Avec l'algorithme d'Euclide, on trouve u=−3. Que vaut v ?
5. Théorème de Gauss
Échauffement
Trois questions rapides sur des leçons déjà vues.
On a 7×1+3×v=1. Que vaut v ?
Existe-t-il des entiers u et v tels que 12u+24v=1 ?
Non, car le PGCD n'est pas 1
Oui, toujours
Oui, avec u=v=1
Avec u=1 et v=−2, que vaut (5)u+2v ?
Découvrir
3 divise 5x. Peut-on affirmer que 3 divise x ?
Oui, car 3 et 5 sont premiers entre eux
Non, jamais
L'idée clé
Ce théorème sert à résoudre des équations en entiers.
Gauss : si a divise bc et si a et b sont premiers entre eux, alors a divise c.
Exemple corrigé
On sait que 7x=4y, avec x et y entiers. Que dire de y ?
7∣4y
7 divise 4y.
7∣y
7 et 4 sont premiers entre eux.
À toi, guidé
À toi : 5 divise 3n. Lequel divise n ?
5
5 et 3 sont premiers entre eux.
Entraînement ★
On sait que 5 divise 11n, avec n entier. Quel est le plus petit entier n>0 possible ?
On sait que 7 divise 8n, avec n entier. Quel est le plus petit entier n>0 possible ?
On sait que 3 divise 8n, avec n entier. Quel est le plus petit entier n>0 possible ?
Attention !
Entraînement ★★
Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « a divise bc » ?
a et b sont premiers entre eux
a est pair
b et c sont égaux
Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « a divise bc » ?
a et b sont premiers entre eux
a est pair
b et c sont égaux
7 divise 9n, et 7 et 9 sont premiers entre eux. Quel est le plus petit entier n>0 possible ?
6 divise 4×3. Peut-on en conclure que 6 divise 4 ou 3 ?
Non : 6 n'est premier ni avec 4 ni avec 3
Oui : par le théorème de Gauss
Oui : 6 divise toujours un facteur
Bilan
Trois questions pour vérifier que c'est acquis.
On sait que 5 divise 11n, avec n entier. Quel est le plus petit entier n>0 possible ?
On sait que 7 divise 8n, avec n entier. Quel est le plus petit entier n>0 possible ?
On sait que 3 divise 8n, avec n entier. Quel est le plus petit entier n>0 possible ?
Fiche résumé
Gauss
Si a∣bc et PGCD(a;b)=1, alors a∣c.
Base des équations diophantiennes.
Attention : vérifie toujours « premiers entre eux ».
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
12 divise 8n. Quel est le plus petit entier n>0 possible ?
6. Nombres premiers et décomposition
Échauffement
Trois questions rapides sur des leçons déjà vues.
Quel est le reste de la division euclidienne de 14 par 3 ?
Quel est le reste de la division euclidienne de −10 par 4 ?
On sait que 9 divise x et y. Quel nombre 9 divise-t-il toujours ?
7x+4y
x+1
yx
Découvrir
Lequel de ces nombres est premier ?
13
9
L'idée clé
Un nombre premier a exactement deux diviseurs positifs.
Tout entier n≥2 se décompose de façon unique en produit de facteurs premiers.
L'ensemble des nombres premiers est infini. Pour tester si n est premier, il suffit d'essayer les premiers p tels que p2≤n.
Exemple corrigé
Décompose 360.
360=23×45
On divise par 2.
45=32×5
On divise par 3.
360=23×32×5
Décomposition.
À toi, guidé
À toi : quel est le plus petit nombre premier ?
2
1 n'est pas premier.
Entraînement ★
Combien de diviseurs positifs le nombre 21×32 a-t-il ?
Combien de diviseurs positifs le nombre 27×38 a-t-il ?
Combien de diviseurs positifs le nombre 21×31 a-t-il ?
Attention !
Entraînement ★★
Lequel de ces nombres est premier ?
101
91
1
Lequel de ces nombres est premier ?
101
91
1
On écrit 432 sous la forme 2x×3y. Que vaut x ?
Le nombre 1 est-il premier ?
Non : un nombre premier a exactement deux diviseurs
Oui : il n'est divisible que par lui-même
Oui : tout nombre impair est premier
Bilan
Trois questions pour vérifier que c'est acquis.
Combien de diviseurs positifs le nombre 21×32 a-t-il ?
Combien de diviseurs positifs le nombre 27×38 a-t-il ?
Combien de diviseurs positifs le nombre 21×31 a-t-il ?
Fiche résumé
Nombres premiers
Exactement deux diviseurs positifs.
Décomposition unique.
Attention : 1 n'est pas premier.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Combien de diviseurs positifs le nombre 21×32×51 a-t-il ?
7. Petit théorème de Fermat
Échauffement
Trois questions rapides sur des leçons déjà vues.
Quel est le plus petit entier positif x tel que 21≡x[5] ?
Quel est le reste de la division de 28 par 5 ?
On sait que x≡2[9] et y≡1[9]. Quel est le reste de x+y modulo 9 ?
Découvrir
Calcule 26 modulo 7.
1
0
L'idée clé
Ce théorème simplifie les grandes puissances.
Petit théorème de Fermat : si p est premier et si p ne divise pas a, alors ap−1≡1[p].
Pour tout entier a : ap≡a[p].
Exemple corrigé
Trouve le reste de la division de 3100 par 11.
310≡1[11]
Fermat : 3¹⁰ ≡ 1.
3100≡1[11]
100 = 10 × 10.
À toi, guidé
À toi : quel est le reste de la division de 46 par 7 ?
1
7 est premier et ne divise pas 4.
Entraînement ★
Quel est le reste de la division de 512 par 7 ?
Quel est le reste de la division de 4270 par 7 ?
Quel est le reste de la division de 412 par 7 ?
Attention !
Entraînement ★★
Quel est le reste de la division de 811 par 11 ?
Quel est le reste de la division de 711 par 11 ?
D'après le petit théorème de Fermat, quel est le reste de 412 modulo 13 ?
1
4
0
Quel est le reste de la division de 57 par 7 ?
Bilan
Trois questions pour vérifier que c'est acquis.
Quel est le reste de la division de 512 par 7 ?
Quel est le reste de la division de 4270 par 7 ?
Quel est le reste de la division de 412 par 7 ?
Fiche résumé
Fermat
ap−1≡1[p], pour p premier ne divisant pas a.
ap≡a[p].
Attention : vérifie que p est premier.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Quel est le reste de la division de 32026 par 7 ?
8. Congruence ax ≡ b, inverse modulo n et chiffrement
Échauffement
Trois questions rapides sur des leçons déjà vues.
Quel est le plus petit entier positif x tel que 21≡x[5] ?
Quel est le reste de la division de 28 par 5 ?
On sait que x≡2[9] et y≡1[9]. Quel est le reste de x+y modulo 9 ?
Découvrir
On veut résoudre 3x≡1[7]. Quelle valeur de x convient ?
5
31
L'idée clé
On ne divise pas : on multiplie par un inverse.
Si a et n sont premiers entre eux, il existe un inversea′ de a modulo n : aa′≡1[n]. Alors ax≡b[n]⟺x≡a′b[n].
Chiffrement affine : on code x par y≡ax+b[26] ; pour déchiffrer, on utilise l'inverse de a modulo 26.
Exemple corrigé
Résous 3x≡4[7].
5×3≡1[7]
L'inverse de 3 est 5.
x≡20[7]
On multiplie par 5.
x≡6[7]
On réduit.
À toi, guidé
À toi : quel est l'inverse de 2 modulo 5 ?
3
2 × 3 = 6 ≡ 1.
Entraînement ★
Résous 3x≡12[7] : donne la solution x entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous 3x≡9[7] : donne la solution x entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous 3x≡6[7] : donne la solution x entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Attention !
Entraînement ★★
Avec le chiffrement y≡3x+1[26], quel nombre y code x=3 ?
Avec le chiffrement y≡3x+1[26], quel nombre y code x=8 ?
Quel est l'inverse de 2 modulo 5 ?
Résous 2x≡10[11] : donne x entre 0 et 10.
Bilan
Trois questions pour vérifier que c'est acquis.
Résous 3x≡12[7] : donne la solution x entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous 3x≡9[7] : donne la solution x entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous 3x≡6[7] : donne la solution x entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Fiche résumé
Inverse modulo n
Il existe si PGCD(a;n)=1.
ax≡b⟺x≡a′b[n].
Attention : on multiplie, on ne divise pas.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Quel est l'inverse de 3 modulo 11, entre 0 et 10 ?
9. Équations diophantiennes
Échauffement
Trois questions rapides sur des leçons déjà vues.
On sait que 5 divise 11n, avec n entier. Quel est le plus petit entier n>0 possible ?
Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « a divise bc » ?
a et b sont premiers entre eux
a est pair
b et c sont égaux
7 divise 9n, et 7 et 9 sont premiers entre eux. Quel est le plus petit entier n>0 possible ?
Découvrir
L'équation 3x+6y=1 a-t-elle des solutions entières ?
Non
Oui
L'idée clé
ax+by=c a des solutions si et seulement si PGCD(a;b) divise c.
On trouve une solution particulière (x0;y0), puis on utilise Gauss. Si a et b sont premiers entre eux, les solutions sont x=x0+bk, y=y0−ak, k∈Z.
Exemple corrigé
Résous 3x+5y=1.
(x0;y0)=(2;−1)
Solution particulière.
3(x−2)=5(−1−y)
On soustrait.
x=2+5k et y=−1−3k
Gauss.
À toi, guidé
À toi : pour 2x+3y=1, on a la solution (2;−1). Combien vaut x pour k=1 dans x=2+3k ?
5
2 + 3.
Entraînement ★
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut x pour k=2 ?
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut x pour k=24 ?
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut x pour k=1 ?
Attention !
Entraînement ★★
L'équation 8x+16y=9 a-t-elle des solutions entières ?
Non
Oui, une seule
Oui, une infinité
L'équation 4x+8y=5 a-t-elle des solutions entières ?
Non
Oui, une seule
Oui, une infinité
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut y pour k=2 ?
Une équation ax+by=c a une solution entière. Combien en a-t-elle en tout ?
Une infinité
Une seule
Deux
Bilan
Trois questions pour vérifier que c'est acquis.
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut x pour k=2 ?
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut x pour k=24 ?
Les solutions de 3x+5y=1 sont x=2+5k, y=−1−3k. Que vaut x pour k=1 ?
Fiche résumé
Équations diophantiennes
Existence : PGCD(a;b)∣c.
Solution particulière, puis Gauss.
Attention : il y a une infinité de solutions.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Combien de couples d'entiers positifs ou nuls (x;y) vérifient 3x+5y=75 ?
10. Compter les diviseurs
Découvrir
12=22×3 a pour diviseurs 1, 2, 3, 4, 6, 12 : six diviseurs. Peut-on trouver ce nombre sans les écrire ?
Oui : (2+1)(1+1)=6
Oui : 2+1=3
L'idée clé
Compter les diviseurs.
Si n=p1a1×p2a2×⋯×pkak (décomposition en facteurs premiers), le nombre de diviseurs positifs de n est
(a1+1)(a2+1)⋯(ak+1).
Exemple corrigé
Nombre de diviseurs de 360=23×32×5.
(3+1)(2+1)(1+1)
Exposants 3, 2, 1.
=24 diviseurs
On multiplie.
À toi, guidé
À toi : nombre de diviseurs de 25 ?
6
5+1.
Entraînement ★
Combien de diviseurs positifs a 26×32 ?
Combien de diviseurs positifs a 24×33 ?
Combien de diviseurs positifs a 23×35 ?
Entraînement ★★
Combien de diviseurs positifs a n=25×52×72 ?
Combien de diviseurs positifs a n=22×52×71 ?
Bilan
Deux questions pour vérifier.
Combien de diviseurs positifs a 26×32 ?
Combien de diviseurs positifs a 24×33 ?
Fiche résumé
Nombre de diviseurs
(a1+1)(a2+1)⋯
Un carré parfait a un nombre impair de diviseurs.
On a choisi 360 degrés pour le tour complet en partie parce que 360 a beaucoup de diviseurs.
11. Histoire de l'arithmétique : Euclide, Fermat et Gauss
Découvrir
Le livre VII des Éléments d'Euclide (vers 300 av. J.-C.) contient une méthode pour trouver le PGCD de deux nombres. Laquelle ?
Les divisions successives : l'algorithme d'Euclide
Écrire tous les diviseurs et comparer
L'idée clé
De l'algorithme d'Euclide aux congruences.
Étape 1Euclidevers 300 av. J.-C.Portrait imaginéAuteur inconnu. Domaine publicVers 300 av. J.-C. : le livre VII des Éléments et l'algorithme d'Euclide.
Étape 2Pierre de Fermatvers 1607 – 1665Rolland Lefebvre. Domaine public1640 : correspondance de Fermat et Frenicle sur les nombres.
Étape 3Carl Friedrich Gauss1777–1855Gottlieb Biermann / After Christian Albrecht Jensen, 1840. Domaine publicÉté 1801 : Gauss publie les Disquisitiones arithmeticae.
Le livre VII des Éléments d'Euclide est une introduction à la théorie des nombres et contient l'algorithme d'Euclide. Fermat (1601–1665) échange des problèmes de nombres avec Frenicle de Bessy, notamment en 1640. À l'été 1801, Gauss publie les Disquisitiones arithmeticae (« Recherches arithmétiques »), qui fondent la théorie moderne des nombres.
Exemple corrigé
PGCD de 252 et 198 par l'algorithme d'Euclide.
54=1×36+18, 36=2×18+0
252=1×198+54, 198=3×54+36.
PGCD=18
Dernier reste non nul.
Entraînement ★
Quel livre Gauss publie-t-il à l'été 1801 ?
Les Disquisitiones arithmeticae
Les Éléments
La Géométrie
Première étape de l'algorithme d'Euclide : quel est le reste de la division euclidienne de 252 par 15 ?
Première étape de l'algorithme d'Euclide : quel est le reste de la division euclidienne de 122 par 17 ?
Avec la notation de Gauss : x≡2(mod8) et y≡2(mod8). Quel est le reste de x+y modulo 8 ?
Fiche résumé
L'arithmétique aujourd'hui
Cryptographie : les paiements en ligne reposent sur les nombres premiers et les congruences.
Codes correcteurs : numéros ISBN, IBAN et cartes bancaires ont une clé de contrôle.
Calendriers : les jours de la semaine se calculent modulo 7.
Sources : biographies d'Euclide, de Fermat et de Gauss sur MacTutor (voir « Sources et crédits »).
Corrigé: Arithmétique
1. Divisibilité et division euclidienne
A
a) 8 b) 9 c) 34 d) 288 e) 3 f) 20
2
28
B
2
7
1
C
2
1
D
7x+4y
E
4
F
2
7
1
G
3
2. Congruences
A
2
2
7x+4y
B
1
9
1
C
1
1
D
3
E
1
F
1
9
1
G
7
3. PGCD et algorithme d'Euclide
A
2
2
7x+4y
B
3
50
2
C
Oui, toujours
Oui, toujours
D
4
E
3
F
3
50
2
G
54
4. Théorème de Bézout
A
3
Oui, toujours
4
B
−2
−2
−2
C
Non, car le PGCD n'est pas 1
Non, car le PGCD n'est pas 1
D
1
E
a et b sont premiers entre eux
F
−2
−2
−2
G
5
5. Théorème de Gauss
A
−2
Non, car le PGCD n'est pas 1
1
B
5
7
3
C
a et b sont premiers entre eux
a et b sont premiers entre eux
D
7
E
Non : 6 n'est premier ni avec 4 ni avec 3
F
5
7
3
G
3
6. Nombres premiers et décomposition
A
2
2
7x+4y
B
6
72
4
C
101
101
D
4
E
Non : un nombre premier a exactement deux diviseurs
F
6
72
4
G
12
7. Petit théorème de Fermat
A
1
1
3
B
1
1
1
C
8
7
D
1
E
5
F
1
1
1
G
4
8. Congruence ax ≡ b, inverse modulo n et chiffrement
A
1
1
3
B
4
3
2
C
10
25
D
3
E
5
F
4
3
2
G
4
9. Équations diophantiennes
A
5
a et b sont premiers entre eux
7
B
12
122
7
C
Non
Non
D
−7
E
Une infinité
F
12
122
7
G
6
10. Compter les diviseurs
A
21
20
24
B
54
18
C
21
20
11. Histoire de l'arithmétique : Euclide, Fermat et Gauss