Fiche de révision : Arithmétique, matrices et déterminants

📋 Plan du Cours

1. Ensembles et opérations fondamentales
2. Applications entre ensembles
3. Divisibilité et division euclidienne
4. PGCD, PPCM et nombres premiers
5. Congruences et équations diophantiennes
6. Équations diophantiennes et congruences
7. Théorème chinois des restes
8. Anneaux modulo n et indicatrice d’Euler
9. Théorèmes de calcul modulo n
10. Principe et fonctionnement de RSA
11. Matrices et opérations fondamentales
12. Rang, équivalence et déterminants
13. Développement des déterminants
14. Propriétés des déterminants
15. Inverse et rang des matrices
16. Résolution des systèmes linéaires

📖 1. Ensembles et opérations fondamentales

🔑 Notions clés & Définitions

• Ensemble : Une collection d’objets bien déterminés dans laquelle les objets sont uniques.
• Inclusion : Lorsque tout élément de E est aussi élément de F, ce qui se note E ⊂ F.
• Opérations ensemblistes : Pour des ensembles E et F, l’intersection contient les éléments communs, la réunion contient les éléments de E ou de F, la différence E\F contient les éléments de E qui ne sont pas dans F, la différence symétrique contient les éléments appartenant à un seul des deux ensembles, et le complémentaire de A dans E contient les éléments de E qui ne sont pas dans A.
• Produit cartésien : L’ensemble des couples ordonnés (x,y) tels que x appartient à E et y appartient à F.

📝 Points essentiels

📌 Deux ensembles sont égaux s’ils ont les mêmes éléments, ce qui revient à établir leur double inclusion.

• Si un ensemble E possède n éléments, son ensemble des parties P(E) possède $2^n$ éléments.

💡 Astuce mémo

∩ sélectionne le commun, ∪ rassemble tout

📖 2. Applications entre ensembles

🔑 Notions clés & Définitions

• Application : Une relation de A vers B qui associe à chaque élément x de A un élément y de B, unique et bien déterminé, noté f(x).
• Injectivité : La propriété f(x)=f(x′) implique x=x′, c’est-à-dire que chaque élément de F possède au plus un antécédent.
• Surjectivité : Lorsque chaque élément de F possède au moins un antécédent dans E.
• Bijectivité : Lorsqu’elle est à la fois injective et surjective, de sorte que chaque élément de F possède un antécédent unique dans E.
• Bijection réciproque : Si f:E→F est bijective, sa bijection réciproque f⁻¹:F→E associe à chaque élément de F son unique antécédent par f.

📝 Points essentiels

📌 Deux applications f:A→B et f′:A′→B′ sont égales si leurs ensembles de départ et d’arrivée sont égaux et si elles ont la même valeur en chaque élément du départ.

💡 Astuce mémo

Injective : au plus un antécédent ; surjective : au moins un

📖 3. Divisibilité et division euclidienne

🔑 Notions clés & Définitions

• Divisibilité : Un entier a divise un entier b s’il existe un entier k tel que b=ka; dans ce cas, b est un multiple de a.

★ À maîtriser

📌 Un entier est divisible par 2 si et seulement si son chiffre des unités est 0, 2, 4, 6 ou 8; il est divisible par 5 si et seulement si ce chiffre est 0 ou 5.

• La division euclidienne de a par un entier naturel non nul b fournit un unique quotient q et un unique reste r tels que a=bq+r et 0≤r<b.

📌 Dans une division euclidienne par b, l’entier a est divisible par b si et seulement si le reste est nul.

Compléments

• La divisibilité est réflexive et transitive, mais elle n’est pas antisymétrique dans Z; sa restriction à N est une relation d’ordre.

💡 Astuce mémo

Diviser → quotient et reste → reste nul si divisibilité

📖 4. PGCD, PPCM et nombres premiers

🔑 Notions clés & Définitions

• PGCD : Le plus grand diviseur commun de deux entiers a et b; il vaut 0 lorsque a=b=0.
• PPCM : Le plus petit multiple commun strictement positif de deux entiers a et b non nuls; il vaut 0 si a=0 ou b=0.
• Nombre premier : Un entier naturel n tel que n≥2 et dont les seuls diviseurs naturels sont 1 et n.

📝 Points essentiels

• L’algorithme d’Euclide calcule le PGCD en remplaçant successivement le couple formé par deux entiers par le diviseur et le reste de leur division euclidienne; le dernier reste non nul est le PGCD.

📌 Deux entiers non nuls a et b sont premiers entre eux si et seulement s’il existe u,v∈Z tels que 1=au+bv.

📐 Formule - Pour deux entiers non nuls a et b, le produit de leur PGCD et de leur PPCM vérifie $(a\wedge b)(a\vee b)=|ab|$.

• Tout entier n≥2 s’écrit de manière unique comme un produit de puissances de nombres premiers distincts, sous la forme $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ avec αᵢ≥1.

💡 Astuce mémo

Euclide → Bézout → facteurs premiers → PGCD/PPCM

📖 5. Congruences et équations diophantiennes

🔑 Notions clés & Définitions

• Congruence : Pour n naturel non nul, deux entiers a et b sont congrus modulo n si a−b est un multiple de n, ce qui se note a≡b (mod n).
• Équation diophantienne : Une équation dont on recherche les solutions dans l’ensemble des nombres entiers.

★ À maîtriser

• Deux entiers sont congrus modulo n si et seulement si leurs restes dans la division euclidienne par n sont égaux.

• La congruence modulo n est compatible avec l’addition, la multiplication et les puissances entières naturelles.

• Pour l’équation diophantienne ax+by=c, avec a,b,c entiers et d=PGCD(a,b), il existe des solutions entières si et seulement si d divise c.

Compléments

• Lorsque d=PGCD(a,b) divise c, l’équation ax+by=c possède une infinité de solutions entières.

💡 Astuce mémo

PGCD divise le second membre → solutions entières

📖 6. Équations diophantiennes et congruences

🔑 Notions clés & Définitions

• Équation diophantienne : Équation dont on cherche les solutions en nombres entiers.

★ À maîtriser

📌 L'équation $ax+by=c$, avec $a,b,c\in\mathbb Z$ et $d=\operatorname{pgcd}(a,b)$, possède des solutions entières si et seulement si $d\mid c$.

📐 Formule - Lorsque $d\mid c$, toutes les solutions entières de $ax+by=c$ sont de la forme $x=x_0+\frac{b}{d}k$ et $y=y_0-\frac{a}{d}k$, avec $k\in\mathbb Z$ et $(x_0,y_0)$ une solution particulière.

📌 L'équation de congruence $ax\equiv b\pmod n$ possède des solutions si et seulement si $\operatorname{pgcd}(a,n)\mid b$.

Compléments

• Les solutions entières de $161x+368y=115$ sont $x=35-16k$ et $y=-15+7k$, avec $k\in\mathbb Z$.

• Les solutions de $9x\equiv6\pmod{24}$ sont regroupées en trois classes modulo 24 : $x=6+24m$, $x=14+24m$ et $x=22+24m$, avec $m\in\mathbb Z$.

💡 Astuce mémo

PGCD diviseur du second membre → existence des solutions

📖 7. Théorème chinois des restes

★ À maîtriser

📌 Si $N_1,\ldots,N_k$ sont des entiers positifs deux à deux premiers entre eux, tout système $z\equiv a_i\pmod{N_i}$ possède une solution et est équivalent à une congruence unique modulo $N_1\cdots N_k$.

📐 Formule - La solution générale d'un système chinois s'écrit $z=z_0+N_1\cdots N_k\mathbb Z$, où $z_0$ est une solution particulière.

Compléments

• Pour deux congruences, on peut construire des entiers $e_1,e_2$ tels que $e_1\equiv1\pmod{N_1},e_1\equiv0\pmod{N_2}$ et $e_2\equiv0\pmod{N_1},e_2\equiv1\pmod{N_2}$, puis prendre $z_0=a_1e_1+a_2e_2$.

• Le système $x\equiv2\pmod{10}$ et $x\equiv5\pmod{13}$ a pour solution générale $x=122+130k$, avec $k\in\mathbb Z$.

💡 Astuce mémo

Des modules premiers entre eux s’emboîtent en un seul grand module

📖 8. Anneaux modulo n et indicatrice d’Euler

🔑 Notions clés & Définitions

• Élément inversible : Dans $\mathbb Z/n\mathbb Z$, un élément a est inversible si et seulement si a et n sont premiers entre eux.
• Indicatrice d’Euler : Le nombre d'entiers compris entre 1 et n−1 qui sont premiers avec n.

★ À maîtriser

📌 L'ensemble $\mathbb Z/n\mathbb Z$ est un corps si et seulement si n est premier.

📐 Formule - Si $n=\prod_i p_i^{r_i}$, alors $\varphi(n)=n\prod_i\left(1-\frac1{p_i}\right)$, où les $p_i$ sont les facteurs premiers distincts de n.

Compléments

• Pour $300=12\times25$, on obtient $\varphi(12)=4$, $\varphi(25)=20$ et donc $\varphi(300)=80$.

💡 Astuce mémo

Élément inversible si premier avec n, corps seulement si n est premier

📖 9. Théorèmes de calcul modulo n

★ À maîtriser

• Si a et n sont premiers entre eux avec $n\ge2$, alors $a^{\varphi(n)}\equiv1\pmod n$.

• Si p est premier et ne divise pas a, alors $a^{p-1}\equiv1\pmod p$, ce qui équivaut aussi à $a^p\equiv a\pmod p$.

• Un entier p est premier si et seulement si $p\mid((p-1)!+1)$.

Compléments

• En appliquant le petit théorème de Fermat, on obtient $14^{3141}\equiv12\pmod{17}$.

💡 Astuce mémo

Euler → Fermat → Wilson

📖 10. Principe et fonctionnement de RSA

★ À maîtriser

• La génération d'une clé RSA consiste à choisir deux nombres premiers distincts p et q, calculer $n=pq$ et $\varphi(n)=(p-1)(q-1)$, choisir e premier avec $\varphi(n)$, puis calculer d tel que $ed\equiv1\pmod{\varphi(n)}$.

📌 En RSA, la clé publique est le couple $(n,e)$, tandis que la clé privée est constituée de d et que p, q et $\varphi(n)$ doivent rester secrets.

📐 Formule - Le chiffrement RSA calcule $C\equiv M^e\pmod n$ et le déchiffrement calcule $M\equiv C^d\pmod n$.

Compléments

📌 La condition $\operatorname{pgcd}(e,\varphi(n))=1$ assure l'existence et l'unicité de l'inverse d de e modulo $\varphi(n)$.

💡 Astuce mémo

Choisir p,q → construire les clés → chiffrer → déchiffrer

📖 11. Matrices et opérations fondamentales

🔑 Notions clés & Définitions

• Matrice : Tableau de scalaires de K comportant p lignes et q colonnes, dont le coefficient situé à la ligne i et à la colonne j est noté aij.
• Transposée : La transposée d'une matrice A est la matrice obtenue en échangeant ses lignes et ses colonnes, avec $(^tA)_{ij}=a_{ji}$.

📝 Points essentiels

📌 Deux matrices de même type sont égales si et seulement si tous leurs coefficients correspondants sont égaux.

📐 Formule - Pour des matrices de même type, l'addition est définie coefficient par coefficient par $[A+B]_{ij}=a_{ij}+b_{ij}$ et la multiplication par un scalaire par $[\lambda A]_{ij}=\lambda a_{ij}$.

📐 Formule - Le produit $AB$ est défini lorsque le nombre de colonnes de A égale le nombre de lignes de B, et son coefficient vérifie $[AB]_{ij}=\sum_{k=1}^{n}a_{ik}b_{kj}$.

📌 Le produit matriciel n'est pas commutatif en général, car $AB$ peut être défini sans que $BA$ le soit, ou bien $AB\ne BA$.

💡 Astuce mémo

Addition terme à terme, produit ligne-colonne

📖 12. Rang, équivalence et déterminants

🔑 Notions clés & Définitions

• Rang : Le rang d'une matrice A est l'entier r tel que sa forme échelonnée réduite contient la matrice identité $I_r$ dans le bloc principal et des blocs nuls ailleurs.
• Matrice inversible : Une matrice carrée A est inversible s'il existe une matrice B telle que $AB=BA=I_n$, et B est alors notée $A^{-1}$.
• Déterminant d’ordre 2 : Pour A=\begin{pmatrix}a&b\c&d\end{pmatrix}, le déterminant est $\det(A)=ad-bc$.

★ À maîtriser

📌 Deux matrices sont équivalentes si et seulement si elles ont le même rang.

• Pour développer un déterminant suivant une ligne ou une colonne, on multiplie chaque coefficient par son cofacteur $C_{ij}=(-1)^{i+j}X_{ij}$, puis on additionne les termes obtenus.

Compléments

📐 Formule - Pour une matrice carrée d'ordre 3, $\det(A)=a_{11}a_{22}a_{33}+a_{12}a_{23}a_{31}+a_{13}a_{21}a_{32}-a_{31}a_{22}a_{13}-a_{32}a_{23}a_{11}-a_{33}a_{21}a_{12}$.

📌 La méthode de Sarrus s'applique uniquement aux déterminants d'ordre 3 ou inférieur.

💡 Astuce mémo

Opérations élémentaires → forme échelonnée → rang

📖 13. Développement des déterminants

🔑 Notions clés & Définitions

• Cofacteur : Le cofacteur de l’élément a_{ij} est $C_{ij}=(-1)^{i+j}X_{ij}$, où X_{ij} est le déterminant obtenu en supprimant la i-ième ligne et la j-ième colonne.

★ À maîtriser

📐 Formule - Le déterminant d’une matrice carrée d’ordre 3 développée suivant la première ligne vérifie $\det A=a_{11}(a_{22}a_{33}-a_{32}a_{23})-a_{12}(a_{21}a_{33}-a_{31}a_{23})+a_{13}(a_{21}a_{32}-a_{31}a_{22}).$

📌 Le déterminant peut être développé suivant n’importe quelle ligne ou colonne comme la somme des produits de chaque élément par son cofacteur.

📐 Formule - Pour une matrice carrée A=(a_{ij}) d’ordre n, le développement suivant la i-ième ligne est $\det(A)=\sum_{k=1}^{n}a_{ik}C_{ik}$, et le développement suivant la j-ième colonne est $\det(A)=\sum_{k=1}^{n}a_{kj}C_{kj}$.

Compléments

📌 Pour réduire les calculs, il est préférable de choisir une ligne ou une colonne contenant le plus de zéros.

💡 Astuce mémo

Mineur → cofacteur → développement

📖 14. Propriétés des déterminants

★ À maîtriser

📐 Formule - Pour deux matrices carrées A et B de même ordre, $\det(AB)=\det(A)\det(B).$

📐 Formule - Pour tout scalaire λ et toute matrice A d’ordre n, $\det(\lambda A)=\lambda^n\det(A).$

• Le déterminant d’une matrice triangulaire est le produit de ses éléments diagonaux, et le déterminant d’une matrice unité vaut 1.

• Ajouter à une ligne une combinaison des autres lignes ne change pas le déterminant, et le même résultat vaut pour les colonnes.

• Le déterminant est nul si une ligne ou une colonne est nulle, si elle est combinaison des autres, ou si deux lignes ou deux colonnes sont proportionnelles.

Compléments

📌 Permuter deux lignes ou deux colonnes transforme le déterminant en son opposé, tandis que transposer une matrice conserve son déterminant : $\det(A)=\det({}^{t}A)$.

💡 Astuce mémo

Zéros facilitent le calcul, dépendance annule le déterminant

📖 15. Inverse et rang des matrices

🔑 Notions clés & Définitions

• Matrice inversible : Une matrice carrée A d’ordre n est inversible s’il existe une matrice carrée B telle que $AB=BA=I_n$; cette matrice B est l’inverse A^{-1}.
• Comatrice : La comatrice de A est la matrice des cofacteurs $\operatorname{com}(A)=(C_{ij})$, avec $C_{ij}=(-1)^{i+j}X_{ij}$.

★ À maîtriser

📐 Formule - Si A est inversible, alors $\det(A^{-1})=\frac{1}{\det(A)}$, $({}^{t}A)^{-1}={}^{t}(A^{-1})$ et $(AB)^{-1}=B^{-1}A^{-1}$.

📐 Formule - Si A est inversible, son inverse se calcule par $A^{-1}=\frac{1}{\det(A)}\,{}^{t}\operatorname{com}(A)=\frac{1}{\det(A)}\operatorname{com}({}^{t}A).$

• La méthode du pivot de Gauss transforme simultanément la matrice augmentée [A|I_n] en [I_n|A^{-1}] par des opérations élémentaires sur les lignes; si A ne peut pas devenir I_n, elle n’est pas inversible.

📐 Formule - Pour une matrice A de dimension n×m, $\operatorname{rg}(A)\leq\min(n,m)$; si A est carrée d’ordre n, $\operatorname{rg}(A)=n\Longleftrightarrow\det(A)\neq0$.

Compléments

📌 Deux matrices carrées A et B de même ordre vérifiant AB=I_n ou BA=I_n sont inversibles et sont inverses l’une de l’autre.

💡 Astuce mémo

Déterminant non nul → inverse → comatrice ou pivot

📖 16. Résolution des systèmes linéaires

🔑 Notions clés & Définitions

• Système linéaire : Un système linéaire est un ensemble fini d’équations linéaires portant sur les mêmes inconnues, et il s’écrit matriciellement $AX=B$.
• Matrice augmentée : La matrice augmentée d’un système s’obtient en ajoutant à la matrice des coefficients A la colonne des seconds membres B.
• Système de Cramer : Un système est de Cramer lorsque le nombre d’équations égale le nombre d’inconnues et que $\det(A)\neq0$.

★ À maîtriser

• 🔄 Les opérations élémentaires sont:
  1. Multiplier une ligne par une constante non nulle
  2. Permuter deux lignes
  3. Ajouter un multiple d’une ligne à une autre

📌 Un système de matrice A et de matrice augmentée M est compatible si et seulement si $\operatorname{rg}(A)=\operatorname{rg}(M)$.

📐 Formule - Tout système de Cramer admet une solution unique donnée par $X=A^{-1}B$.

• Pour résoudre un système échelonné carré dont les coefficients diagonaux sont non nuls, on calcule d’abord la dernière inconnue puis on remonte progressivement jusqu’à la première.

Compléments

📐 Formule - Dans la règle de Cramer, si $\Delta=\det(A)$ et si Δ_{x_i} est obtenu en remplaçant la i-ième colonne de A par les seconds membres, alors la solution est $x_i=\frac{\Delta_{x_i}}{\Delta}$.

📌 Dans un système échelonné, une ligne de la forme 0=c impose une incompatibilité si c est non nul, tandis qu’une ligne 0=0 fournit une condition toujours vérifiée.

💡 Astuce mémo

Augmentée → opérations élémentaires → système échelonné → solution

📊 Tableaux de synthèse

Types d’applications

Clés RSA