Programme de mathématiques MPSI, MP2I · semestre 1
b) PGCD et algorithme d’Euclide
Rechercher dans cette partie du programmeTexte officiel du programme
| Contenus | Capacités et commentaires |
|---|---|
PGCD de deux entiers naturels dont l’un au moins est non nul. | Notation $a \wedge b$. Le PGCD de $a$ et $b$ est défini comme étant le plus grand élément (pour l’ordre naturel dans $\mathbb{N}$) de l’ensemble des diviseurs communs à $a$ et $b$. |
Algorithme d’Euclide. | L’ensemble des diviseurs communs à $a$ et $b$ est égal à l’ensemble des diviseurs de $a \wedge b$. $a \wedge b$ est le plus grand élément (au sens de la divisibilité) de l’ensemble des diviseurs communs à $a$ et $b$. Pour $k \in \mathbb{N}^*$, PGCD de $ka$ et $kb$. |
Extension au cas de deux entiers relatifs. | |
Relation de Bézout. | Détermination d’un couple de Bézout par l’algorithme d’Euclide étendu. |
PPCM. | Notation $a \vee b$. |
exo7 1324
Déterminer le sous-groupe de \(\Zz\) engendré par les entiers 24, 36 et \(-54.\) ...
exo7 2124
Soit \(G\) un groupe abélien et \(a\) et ...
exo7 2243
On dit que \(\quad a \mod n\) est inversible si il existe \(b \mod n\) tel que ...
exo7 2270
Pour quel \(n\), \(m\) dans \(\Zz\) la fraction ...
exo7 2301
Trouver toutes les solutions des systèmes suivantes :
exo7 255
Quel est le plus petit entier naturel qui, divisé par \(8,15,18\) et \(24\), donn ...
exo7 287
Montrer que l’intersection de deux sous-groupes de \(\mathbb{Z}\) est un sous-groupe de ...
exo7 290
Calculer le pgcd des nombres suivants :
exo7 291
Calculer le ppcm des nombres : 108 et 144 ; 128 et 230 ; 6, 16 et 50.
exo7 292
Déterminer les couples d’entiers naturels de pgcd 18 et de somme 360. De même avec pgcd 18 et produit 6480.
exo7 293
Si \(a,b,c,d\) sont des entiers supérieurs à \(1\), montrer que l’on a : ...
exo7 294
Soient \(a,b,c\) des entiers relatifs tels que \((a,b)\not =(0,0)\), montrer que ...
exo7 295
Soient \(a\) et \(b\) deux entiers tels que ...
exo7 296
Calculer par l’algorithme d’Euclide : \(\pgcd(18480,9828)\). En déduire une écriture de ...
exo7 297
Déterminer le pgcd de \(99\,099\) et \(43\,928\). Déterminer le pgcd de ...
exo7 298
Déterminer l’ensemble de tous les couples \((m,n)\) tels que \[955m+183n=1.\] ...
exo7 299
Calculer, en précisant la méthode suivie, \[a=\text{pgcd} (720,252) \quad\quad b = \text{ppcm} (720,252)\] ainsi ...
exo7 302
Déteminer deux entiers naturels connaissant leur somme, \(1008\), et leur pgcd, ...
exo7 303
Notons \(a=1\;111\;111\;111\) et \(b=123\;456\;789\).
exo7 304
Soient \(m\) et \(n\) deux entiers ...
exo7 305
Résoudre dans \({\Zz}:1665x+1035y=45.\)
exo7 3053
Soient \(a,b \in \N\). On pose \(m = \text{ppcm}(a,b)\) et ...
exo7 306
Montrer qu’il n’existe pas d’entiers \(m\) et \(n\) tels que ...
exo7 307
Soit \(m\) et \(n\) deux entiers positifs.
exo7 308
Trouver une CNS pour que \(ax+b\equiv 0 \ \rm{mod} \ n\) ait une solution.
exo7 309
Calculer \(\mbox{pgcd}(18,385)\) par l’algorithme d’Euclide, en déduire un couple ...
exo7 310
Trouver \(a\) et \(b\) entiers naturels tels que
exo7 3108
Soient \(p,q\) premiers impairs tels que \(q\mid2^p-1\). Montrer que ...
exo7 3110
Soient \(a,b,c \in \Z\) tels que \(a\wedge b = 1\). Montrer que ...
exo7 3111
Soient \(a,b\) entiers, \(d = a \wedge b\), ...
exo7 3112
Soient \(a,b \in \Z\). Chercher \((a-b)^3 \wedge (a^3 - b^3)\).
exo7 3113
Soit \(n \in \N\). Chercher \((n^3+n) \wedge (2n+1)\).
exo7 3114
Soit \(n \in \N\). Chercher \((15n^2+8n+6) \wedge (30n^2+21n+13)\).
exo7 3115
Soient \(d,m \in \N^*\). Donner une condition nécéssaire et suffisante sur ...
exo7 3116
Trouver les couples d’entiers \((x,y) \in \Z^2\) tels que : ...
exo7 3117
Résoudre : \[\begin{cases}x^2+y^2 = 85113\cr x\vee y = 1764.\end{cases}\]
exo7 3118
Résoudre : \(\begin{cases} x \vee y = 210(x \wedge y)\cr y-x = x \wedge y.\end{cases}\)
exo7 3119
Résoudre dans \(\Z\) : \(x \wedge y = x + y - 1\).
exo7 312
Résoudre dans \(\mathbb{Z}\) le système suivant : ...
exo7 3120
Résoudre dans \(\Z^*\) : \(x \vee y = x + y - 1\).
exo7 3121
Résoudre dans \(\N^*\) : ...
exo7 3122
Soient \(a,m,n\ \in \N^{*}\), \(a\ge 2\), et ...
exo7 3124
Soient \(a,b,c\) trois entiers relatifs. On considère l’équation : ...
exo7 3125
Résoudre dans \(\Z\) :
exo7 3127
Résoudre :
exo7 314
Résoudre dans \(\mathbb{Z}^2\) les équations suivantes : ...
exo7 3150
On cherche les couples \((x,y) \in \bigl(\Q^{+*}\bigr)^2\) tels que \(x < y\) ...
exo7 3153
Soient \(n,p \ge 2\). Montrer que : \(n \wedge p = 1 \iff \exists\ k > 0\) tel ...
exo7 316
Trouver \(\mbox{pgcd}(-357,629)\) et trouver des entiers \(x\) et ...
exo7 317
Trouver \(\mbox{pgcd}(2183,6313)=d\) et trouver des entiers \(x\) et ...