Ficha de revisão: Principes fondamentaux de l'arithmétique

📋 Plan du Cours

1. Divisibilité dans Z
2. Congruence dans Z
3. PGCD et PPCM
4. Nombres premiers
5. Algorithme d’Euclide
6. Nombres premiers entre eux
7. Décomposition en premiers
8. Critère divisibilité par 3
9. Critère divisibilité par 11

📖 1. Divisibilité dans Z

🔑 Notions clés & Définitions

• Théorème de la division euclidienne dans Z (PTSI, 2025) : Pour tout a ∈ Z∗ et b ∈ Z, il existe un couple unique (q, r) ∈ Z × N tel que b = aq + r, avec 0 ≤ r < |a|.
• Définition de quotient et reste de la division euclidienne (PTSI, 2025) : Le quotient q est le nombre entier obtenu lors de la division de b par a, et le reste r est la différence b − aq, vérifiant la condition 0 ≤ r < |a|.
• Définition de divisibilité (PTSI, 2025) : a divise b (noté a|b) si il existe un entier k ∈ Z tel que b = ka.
• Propriétés de la relation de divisibilité (PTSI, 2025) :
  • Si a|b et b ≠ 0, alors |a| ≤ |b|.
  • Si a|b et b|c, alors a|c.
  • Si a|b et b|a, alors a = b ou a = −b.
• Lien entre divisibilité et division euclidienne (PTSI, 2025) : a divise b si et seulement si le reste de la division euclidienne de b par a est nul.

📖 2. Congruence dans Z

🔑 Notions clés & Définitions

• Congruence modulo n : Soit n ∈ Z et (a, b) ∈ Z². On dit que a et b sont congrus modulo n, noté a ≡ b[n], si il existe k ∈ Z tel que b = a + kn. Cela signifie que la différence b − a est divisible par n, c’est-à-dire que n divise b − a.

• Propriété de réflexivité (dans la congruence) : Pour tout a ∈ Z, a ≡ a[n]. Cela indique que chaque entier est congru à lui-même modulo n.

• Propriété de transitivité : Si a ≡ b[n] et b ≡ c[n], alors a ≡ c[n]. Cela montre que la relation de congruence est une relation d’équivalence.

• Propriété de symétrie : Si a ≡ b[n], alors b ≡ a[n]. La relation est symétrique, ce qui signifie que la congruence est une relation d’équivalence.

• Caractérisation par le reste de division euclidienne : a ≡ b[n] si et seulement si le reste de la division euclidienne de a et b par n est le même. Autrement dit, a et b ont le même reste lorsqu’on les divise par n.

📝 Points essentiels

• La congruence modulo n est une relation d’équivalence sur Z, vérifiant réflexivité, symétrie et transitivité, ce qui permet de partitionner Z en classes de congruence (voir proposition I.5).
• La propriété fondamentale est que a ≡ b[n] ⇔ n divise (b − a). Cela relie directement la congruence à la divisibilité.
• La caractérisation par le reste de division euclidienne indique que deux entiers sont congrus modulo n si leurs restes dans la division par n sont égaux.
• Les propriétés algébriques importantes incluent :
  • a ≡ a[n] (réflexivité)
  • a ≡ b[n] ⇒ b ≡ a[n] (symétrie)
  • Si a ≡ b[n] et b ≡ c[n], alors a ≡ c[n] (transitivité)
  • a ≡ b[n] ⇒ (∀k ∈ Z, a + k ≡ b + k[n]) (ajout d’une constante)
  • a ≡ b[n] ⇒ (∀k ∈ Z, ka ≡ kb[n]) (produit par une constante)
  • Si a ≡ a′[n] et b ≡ b′[n], alors a + b ≡ a′ + b′[n] (somme)
  • Si a ≡ a′[n] et b ≡ b′[n], alors ab ≡ a′b′[n] (produit)
  • a ≡ b[n] ⇒ (∀k ∈ N, ak ≡ bk[n]) (élévation à une puissance)

💡 À retenir

La congruence modulo n est une relation d’équivalence qui relie deux entiers par leur reste commun lors de la division par n, permettant de simplifier de nombreux calculs en arithmétique.

📖 3. PGCD et PPCM

🔑 Notions clés & Définitions

• PPCM (Plus Petit Commun Multiple) : Enoncé dans Théorème II.2, c’est le plus petit entier naturel qui est multiple commun de deux entiers a et b. Il est noté a ∨ b ou PPCM(a, b). Il existe un unique tel multiple, et il vérifie que tout autre multiple commun de a et b est un multiple de ce PPCM.

• PGCD (Plus Grand Commun Diviseur) : Selon Théorème II.3, c’est le plus grand entier naturel qui divise deux entiers a et b. Noté a ∧ b ou PGCD(a, b). Il existe un unique tel diviseur, et il est caractérisé par le fait que tout diviseur commun de a et b divise le PGCD.

• Théorème d’existence et d’unicité du PGCD et PPCM : Établi dans Théorème II.2 et II.3, il affirme que pour tout couple d’entiers a et b, il existe un unique PGCD δ et un unique PPCM m, tels que :

  • δ divise a et b, et tout diviseur commun de a et b divise δ.
  • a ∨ b est le plus petit multiple commun de a et b, et a ∧ b est le plus grand diviseur commun.

• Lien entre PGCD et PPCM : La relation fondamentale, démontrée dans Proposition II.7, stipule que :
  $a \times b = \text{PPCM}(a, b) \times \text{PGCD}(a, b)$
  Autrement dit, le produit de deux entiers est égal au produit de leur PPCM et de leur PGCD.

• Structure des sous-groupes de Z : Selon Théorème II.1, tout sous-groupe de Z est de la forme mZ, où m est un entier naturel. Cette structure est utilisée pour définir et caractériser le PGCD et le PPCM, notamment en montrant que l’ensemble des multiples communs à a et b est un sous-groupe de Z, donc de la forme mZ, avec m étant le PGCD.

📖 4. Nombres premiers

🔑 Notions clés & Définitions

• Nombre premier : Un entier naturel n ≥ 2 dont les seuls diviseurs positifs sont 1 et n. (Proposition III.1)
• Propriétés fondamentales des nombres premiers : Un nombre n ≥ 2 est premier si et seulement si, pour tout p, q ∈ N, n = pq ⇒ p = 1 ou p = n, q = 1 ou q = n. (Proposition III.1)
• Rôle dans la décomposition en facteurs premiers : Tout entier n ≥ 2 peut s’écrire de manière unique (à l’ordre près) comme un produit de nombres premiers, avec des exposants naturels non nuls. (Théorème III.4)

📝 Points essentiels

• La définition de nombre premier repose sur la restriction aux diviseurs positifs : n ≥ 2, seuls 1 et n divisent n.
• La propriété clé est que tout nombre n ≥ 2 possède au moins un diviseur premier (Théorème III.2), et qu'il existe une infinité de nombres premiers (Théorème III.3).
• La décomposition en facteurs premiers est une propriété d’unicité : chaque entier n ≥ 2 s’écrit comme un produit de nombres premiers distincts, élevés à des puissances naturelles, de façon unique sauf ordre (Théorème III.4).
• La méthode du crible d’Erathostène permet d’identifier tous les nombres premiers inférieurs à N.

💡 À retenir

Les nombres premiers sont les "briques" fondamentales de l’arithmétique, car tout entier supérieur ou égal à 2 peut être décomposé de façon unique en produit de premiers, ce qui constitue un pilier de la théorie des nombres.

📖 5. Algorithme d’Euclide

🔑 Notions clés & Définitions

Algorithme d’Euclide (proposé par Euclide dans ses Éléments) : méthode itérative permettant de calculer le PGCD de deux entiers relatifs a et b (avec b ≠ 0) en utilisant la division euclidienne. Il repose sur la propriété que le PGCD de a et b est égal au PGCD de b et du reste r de la division de a par b.

Justification de l’algorithme : la propriété fondamentale selon laquelle le PGCD de deux nombres a et b est le même que celui de b et du reste r (a = bq + r), ce qui permet de réduire progressivement le problème jusqu’à obtenir un reste nul, dont le diviseur commun est le PGCD.

Preuve de l’algorithme : repose sur la propriété que les diviseurs communs de a et b sont exactement ceux de b et r (démontrée dans la proposition II.8), assurant que le PGCD ne change pas lors de chaque étape de division, garantissant la convergence vers le PGCD au bout d’un nombre fini d’itérations.

📝 Points essentiels

• La propriété clé : si a = bq + r, alors a et b ont le même PGCD que b et r (proposition II.8).
• L’algorithme consiste à effectuer des divisions successives :
  1. Diviser b par a pour obtenir un quotient q1 et un reste r1.
  2. Remplacer a par b, et b par r1, puis répéter l’opération.
  3. Continuer jusqu’à ce que le reste soit nul.
• Le dernier reste non nul est le PGCD de a et b.
• La méthode est efficace et garantit la terminaison en un nombre fini d’étapes.
• La propriété que le PGCD ne change pas lors de chaque étape est justifiée par la proposition II.8, qui établit l’égalité PGCD(a, b) = PGCD(b, r).

💡 À retenir

L’algorithme d’Euclide repose sur la propriété que le PGCD de deux nombres est invariant lors de la division euclidienne, permettant de réduire le problème jusqu’à obtenir le PGCD, qui est le dernier reste non nul.

📖 6. Nombres premiers entre eux

🔑 Notions clés & Définitions

• Entiers premiers entre eux : Deux entiers relatifs a et b sont dits premiers entre eux si leurs seuls diviseurs communs sont 1 et −1, ce qui équivaut à a ∧ b = 1, selon II.3.
• Identité de Bézout : Pour deux entiers a et b, ils sont premiers entre eux si et seulement s'il existe (u, v) ∈ Z² tels que au + bv = 1, selon II.4.
• Lemme de Gauss : Si a, b, c ∈ Z et si a ∧ b = 1, alors a | bc ⇒ a | c, selon II.5.
• Lien entre entiers premiers entre eux et divisibilité : Deux entiers a et b sont premiers entre eux si et seulement si leur PGCD est égal à 1, ce qui implique que leur seul diviseur commun positif est 1, selon II.3 et II.4.

📝 Points essentiels

• La propriété fondamentale est que deux entiers sont premiers entre eux si leur PGCD est 1, ce qui est aussi caractérisé par l’existence d’une combinaison linéaire de la forme au + bv = 1 (II.4).
• Le Lemme de Gauss montre que si a et b sont premiers entre eux, alors a divise le produit bc implique a divise c, ce qui est une propriété clé pour l’étude de la divisibilité et des nombres premiers.
• La décomposition en facteurs premiers repose sur la propriété que tout entier ≥ 2 possède au moins un diviseur premier, et que cette décomposition est unique (voir III.2 et III.4).
• La preuve que l’on peut toujours trouver deux entiers u et v tels que au + bv = 1 est une caractéristique essentielle pour démontrer que deux nombres premiers entre eux ont une certaine indépendance dans leur structure multiplicative.

💡 À retenir

Deux entiers sont premiers entre eux si leur PGCD est 1, ce qui équivaut à l’existence d’une combinaison linéaire de ces deux entiers égale à 1, selon l’identité de Bézout.

📖 7. Décomposition en premiers

🔑 Notions clés & Définitions

• Décomposition en facteurs premiers (théorème fondamental de l’arithmétique) : Toute entier naturel n ≥ 2 peut s’écrire de manière unique, à l’ordre près, comme un produit de nombres premiers p₁, p₂, ..., pᵣ, élevés à des puissances entières non nulles, c’est-à-dire :
  n = p₁^α₁ × p₂^α₂ × ... × pᵣ^αᵣ, avec pᵢ premiers distincts et αᵢ ≥ 1.
  (source : Chapitre 13, Arithmétique)

• Propriétés de la décomposition en nombres premiers :

  • Unicité : La décomposition en facteurs premiers est unique à l’ordre près.
  • Existence : Tout entier naturel n ≥ 2 possède une telle décomposition.
  • Divisibilité : La décomposition permet de déterminer facilement si un nombre divise un autre en comparant leurs facteurs premiers (voir utilisation pour PGCD et PPCM).
    (source : Chapitre 13, Arithmétique)

• Utilisation de la décomposition en premiers pour calculer PGCD et PPCM :

  • PGCD : Le plus grand commun diviseur de deux entiers peut se déterminer en prenant le minimum des exponents de chaque facteur premier dans leurs décompositions respectives.
  • PPCM : Le plus petit commun multiple se calcule en prenant le maximum des exponents de chaque facteur premier.
    (source : Chapitre 13, Arithmétique)

📝 Points essentiels

• La décomposition en facteurs premiers est une propriété fondamentale qui garantit que tout entier ≥ 2 peut être exprimé de façon unique comme un produit de nombres premiers, ce qui facilite de nombreux calculs en arithmétique.
• La preuve de l’existence repose sur le crible d’Ératosthène, tandis que l’unicité s’appuie sur la propriété que deux décompositions différentes impliqueraient un diviseur premier commun non trivial, ce qui est impossible.
• La décomposition est essentielle pour déterminer le PGCD et le PPCM :
  • PGCD(a, b) = produit des premiers communs élevés aux minimums de leurs exponents.
  • PPCM(a, b) = produit des premiers communs élevés aux maximums de leurs exponents.
• La décomposition en premiers est également utilisée pour tester la divisibilité, factoriser, et analyser la structure des entiers.

💡 À retenir

La décomposition en facteurs premiers est la clé pour comprendre la structure des entiers et simplifier le calcul du PGCD et du PPCM, grâce à son unicité et à ses propriétés fondamentales.

📖 8. Critère divisibilité par 3

🔑 Notions clés & Définitions

• **Congruence dans Z (selon source ) : Soit n ∈ Z et a, b ∈ Z. On dit que a est congru à b modulo n, noté a ≡ b[n], si n divise b − a, c’est-à-dire si b − a = kn pour un certain k ∈ Z.
• Lien entre congruence modulo 3 et divisibilité (selon source ) : Un entier n est divisible par 3 si et seulement si n ≡ 0[3], c’est-à-dire si n est congru à 0 modulo 3.
• Utilisation de la somme des chiffres pour tester la divisibilité par 3 (selon source ) : La propriété que n est divisible par 3 si et seulement si la somme de ses chiffres dans son écriture décimale est congrue à 0 modulo 3, c’est-à-dire si cette somme est divisible par 3.
• Critère de divisibilité par 3 (selon source ) : Un entier naturel n est divisible par 3 si et seulement si la somme de ses chiffres dans la base 10 est divisible par 3, ce qui revient à dire que n ≡ somme des chiffres [3].

📝 Points essentiels

• La congruence modulo 3 permet de relier la divisibilité d’un nombre à une propriété arithmétique simple : la somme de ses chiffres.
• La propriété repose sur le fait que 10 ≡ 1[3], d’où la règle que la somme des chiffres d’un nombre est congrue à ce nombre modulo 3.
• La preuve de ce critère s’appuie sur la propriété que pour tout k ∈ N, 10^k ≡ 1[3], et que par la règle du produit par une constante, chaque chiffre multiplié par une puissance de 10 reste congru à lui-même modulo 3.
• La relation entre la congruence et la divisibilité est directe : n est divisible par 3 ⇔ n ≡ 0[3] ⇔ somme des chiffres de n ≡ 0[3].
• Ce critère permet une vérification rapide de la divisibilité sans effectuer la division complète, en utilisant uniquement la somme des chiffres.

💡 À retenir

La divisibilité par 3 d’un nombre est équivalente à la divisibilité de la somme de ses chiffres par 3, ce qui se traduit par la congruence n ≡ 0[3].

📖 9. Critère divisibilité par 11

🔑 Notions clés & Définitions

Critère de divisibilité par 11 : Méthode permettant de déterminer si un nombre est divisible par 11 en utilisant la congruence modulo 11, en se basant sur la différence entre la somme des chiffres en position paire et la somme des chiffres en position impaire.

Calcul des restes des puissances de 10 modulo 11 : Opération consistant à déterminer, pour tout entier k, le reste de 10^k lorsqu'il est divisé par 11, c'est-à-dire 10^k ≡ r [11], où r est le reste. Par exemple, 10^k modulo 11 suit une certaine périodicité.

Application du critère pour tester la divisibilité par 11 : Procédé utilisant la congruence modulo 11 pour vérifier si la différence entre la somme des chiffres en positions paires et impaires est divisible par 11, ce qui implique la divisibilité du nombre par 11.

📝 Points essentiels

• La méthode repose sur la congruence modulo 11, en particulier sur la relation 10 ≡ -1 [11], qui permet de simplifier le calcul des puissances de 10 modulo 11. (voir section 2).
• Le calcul des restes des puissances de 10 modulo 11 montre que 10^k ≡ (-1)^k [11], ce qui établit une périodicité de période 2.
• Pour tester la divisibilité d’un nombre par 11, on calcule la différence entre la somme des chiffres en position impaire et la somme des chiffres en position paire. Si cette différence est divisible par 11, alors le nombre l’est aussi.
• La démarche est illustrée par l'exemple de 2915, où l’on vérifie que la différence entre la somme des chiffres en positions impaires et paires est un multiple de 11.

💡 À retenir

Le critère de divisibilité par 11 repose sur la congruence modulo 11, en particulier sur la périodicité de 10^k ≡ (-1)^k [11], permettant de simplifier le test en utilisant la différence entre la somme des chiffres en positions paires et impaires.

📊 Tableaux de Synthèse

Thème	Notions clés	Propriétés / Relations	Auteurs / Références
Divisibilité dans Z	Théorème division euclidienne (PTSI 2025) : ∀a∈Z*, ∀b∈Z, ∃! (q,r) ∈ Z×N, b=aq+r, 0≤r<	a
Congruence dans Z	a≡b[n] ⇔ n	b−a; relation d’équivalence; classes de congruence	a≡a[n]; a≡b[n] ⇒ b≡a[n]; a≡b[n] et b≡c[n] ⇒ a≡c[n]; propriétés de stabilité
PGCD et PPCM	PGCD (a∧b), PPCM (a∨b); relation fondamentale : a×b=PGCD×PPCM; sous-groupes de Z	PGCD et PPCM existent et sont uniques; sous-groupes de Z de la forme mZ	Théorèmes II.2, II.3, II.1
Nombres premiers	n≥2, divisibilité limitée à 1 et n; décomposition unique en premiers; infinité de premiers	Définition, théorème de décomposition, crible d’Erathostène	Proposition III.1, III.2, III.3, III.4
Algorithme d’Euclide	Méthode pour PGCD; propriétés de la division euclidienne; convergence garantie	PGCD(a,b)=PGCD(b,r); processus itératif basé sur a=bq+r	Euclide, Proposition II.8

⚠️ Pièges & Confusions Fréquentes

1. Confondre divisibilité (a|b) avec la congruence (a≡b[n]) : la première concerne la divisibilité, la seconde une relation d’équivalence basée sur le reste de division.
2. Oublier que le reste de la division euclidienne est toujours non négatif et inférieur à |a|.
3. Confondre PGCD et PPCM : le PGCD est un diviseur commun maximal, le PPCM un multiple commun minimal.
4. Négliger que la décomposition en premiers est unique sauf l’ordre des facteurs.
5. Se tromper dans le critère de divisibilité par 3 : somme des chiffres divisible par 3, pas la divisibilité par 11.
6. Confondre le critère de divisibilité par 11 (différence entre somme des chiffres en position paire et impaire divisible par 11) avec d’autres critères.
7. Mal appliquer l’algorithme d’Euclide en ne respectant pas l’ordre ou en oubliant la terminaison quand le reste devient zéro.

✅ Checklist Examen

1. Connaître la définition de la division euclidienne dans Z et ses propriétés fondamentales (PTSI 2025).
2. Savoir que a|b si et seulement si le reste de la division de b par a est nul.
3. Maîtriser la relation d’équivalence de la congruence modulo n, notamment que a≡b[n] ⇔ n|b−a.
4. Savoir que la relation de congruence est réflexive, symétrique et transitive, et qu’elle partitionne Z en classes.
5. Connaître la définition et la propriété du PGCD (Théorème II.3) et du PPCM (Théorème II.2).
6. Savoir que a×b=PGCD(a,b)×PPCM(a,b).
7. Connaître la définition d’un nombre premier (Proposition III.1) et la décomposition en facteurs premiers (Théorème III.4).
8. Savoir que tout entier ≥ 2 possède au moins un facteur premier (Théorème III.2) et que la décomposition en premiers est unique.
9. Maîtriser l’algorithme d’Euclide pour calculer le PGCD, notamment la propriété PGCD(a,b)=PGCD(b,r) (Proposition II.8).
10. Savoir que le critère de divisibilité par 3 repose sur la somme des chiffres, et par 11 sur la différence entre la somme des chiffres en position paire et impaire.
11. Connaître le critère de divisibilité par 11 : la différence entre la somme des chiffres en position paire et impaire est divisible par 11.
12. Vérifier la maîtrise du vocabulaire et des concepts clés : divisibilité, congruence, PGCD, PPCM, nombres premiers, décomposition, algorithme d’Euclide, critères de divisibilité.