$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Exercices corrigés - pgcd, ppcm, nombres premiers entre eux

Enoncé
  1. Quels sont les diviseurs communs à 390 et 525?
  2. Calculer $(3^{123}-5)\wedge 25$.
  3. Soit $n\in\mathbb Z$. Démontrer que $6|n(n+1)(n+2)$.
Indication
Corrigé
Exercice 2 - Des équations de Bezout [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre les équations suivantes dans $\mathbb Z^2$ :
  1. $2x+5y=3$;
  2. $323x-391y=612$;
  3. $162x+207y=27$;
  4. $221x+247y=15$.
Indication
Corrigé
Exercice 3 - Rationnels qui sont entiers [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a$ et $b$ deux rationnels tels que $a+b$ et $a\times b$ sont des entiers. Prouver que $a$ et $b$ sont des entiers.
Indication
Corrigé
Enoncé
  1. Démontrer que si deux entiers relatifs sont premiers entre eux, leur somme et leur produit sont premiers entre eux. La réciproque est-elle vraie?
  2. Démontrer que l'on ne change pas le pgcd de deux entiers en multipliant l'un d'entre eux par un entier premier avec l'autre.
Indication
Corrigé
Exercice 5 - Points à coordonnées entières sur une droite rationnelle [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le plan est muni d'un repère $(O,\vec i,\vec j)$. On considère 4 entiers relatifs non nuls $m,n,p$ et $q$ tels que $\textrm{pgcd}(m,n)=\textrm{pgcd}(p,q)=1$. Le but de l'exercice est de déterminer une condition nécessaire et suffisante portant sur $m,n,p,q$ pour que la droite $\Delta$ d'équation $y=\frac mn x-\frac pq$ comporte au moins un point dont les coordonnées sont deux entiers relatifs.
  1. On suppose dans cette question que la droite $\Delta$ comporte un point de coordonnées $(x_0,y_0)$ où $x_0$, $y_0$ sont des entiers relatifs.
    1. Démontrer que $q$ divise le produit $np$.
    2. En déduire que $q$ divise $n$.
  2. Réciproquement, on suppose que $q$ divise $n$ et on souhaite trouver un couple $(x_0,y_0)$ d'entiers relatifs tels que $y_0=\frac mnx_0-\frac pq$.
    1. On pose $n=qr$, où $r$ est un entier relatif non nul. Démontrer que l'on peut trouver deux entiers relatifs $u$ et $v$ tels que $qru-mv=1$.
    2. En déduire qu'il existe un couple $(x_0,y_0)$ d'entiers relatifs tels que $y_0=\frac mn x_0-\frac pq$.
  3. On donne l'algorithme suivant :


    Variables :
      m,n,p,q entiers relatifs non nuls tels que pgcd(m,n)=pgcd(p,q)=1
      x entier naturel
    Algorithme
      Si q divise n alors
         x prend la valeur 0
         Tant que (mx/n - p/q) n'est pas un entier et (-mx/n-p/q) n'est pas un entier faire
             x prend la valeur x+1
         Fin Tant Que
         Si (mx/n-p/q) est entier alors Afficher x, mx/n-p/q
         Sinon Afficher -x,-mx/n-p/q
         Fin Si
      Sinon Afficher "Pas de solutions"
      Fin Si.

    Justifier que cet algorithme se termine. Que permet-il d'obtenir?

Indication
Corrigé
Enoncé
La machine allemande G-Schreiber était une machine à chiffrer utilisée par l'Allemagne pendant la Seconde Guerre Mondiale. Elle était constituée (entre autres) de dix roues comprenant respectivement 47, 53, 59, 61, 64, 65, 67, 69, 71 et 73 positions. A chaque fois qu'un caractère était tapé, il était chiffré à l'aide d'un algorithme un peu compliqué utilisant la position des roues, puis toutes les roues tournaient d'une position. Combien fallait-il taper de caractères pour revenir à la position initiale des roues?
Indication
Corrigé
Enoncé
Calculer le pgcd de $2^{445}+7$ et $15$.
Indication
Corrigé
Enoncé
Soient $n\in\mathbb Z$. Calculer les pgcd suivants : $$\begin{array}{lll} \mathbf 1.\ (n^2+n)\wedge (2n+1)&\quad\quad&\mathbf 2.\ (15n^2+8n+6)\wedge(30n^2+21n+13)\\ \end{array} $$
Indication
Corrigé
Exercice 9 - Bezout à coefficients positifs [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a,b>0$ deux entiers premiers entre eux et $x>ab$. Montrer que l'équation $au+bv=x$ a deux solutions avec $a,b\in\mathbb N$.
Indication
Corrigé
Enoncé
J'ai une pile de livres. Lorsque je les range par 10, il m'en reste 3. Lorsque je les range par 17(!), il m'en reste 2. Quel est le nombre minimum de livres que je possède? Quels sont tous les nombres possibles?
Indication
Corrigé
Exercice 11 - Le magicien des mathématiques [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Bonjour, je suis le magicien des mathématiques. Je vais deviner votre date de naissance.
Prenez votre jour de naissance. Multipliez le par 31.
Prenez votre mois de naissance. Multiplier le par 12.
Ajoutez ces deux nombres. Combien trouvez-vous? 811 vous me dites?
Et bien vous êtes né un 25 mars!
En plus, c'est vrai. Mais comment a-t-il fait?
Indication
Corrigé
Exercice 12 - Pas de solutions rationnelles [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Montrer que l'équation $x^3-x^2+x+1=0$ n'a pas de solutions dans $\mathbb Q$.
Indication
Corrigé
Exercice 13 - Termes consécutifs d'une suite [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $(u_n)$ la suite d'entiers définie par $u_0=14$ et $u_{n+1}=5u_n-6$. Démontrer que le pgcd de deux termes consécutifs de la suite est constant. Préciser sa valeur.
Indication
Corrigé
Exercice 14 - pgcd et somme ou produit prescrits [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Déterminer les couples d'entiers naturels de pgcd 18 et de somme 360.
  2. Déterminer les couples d'entiers naturels de pgcd 18 et de produit 6480.
Indication
Corrigé
Enoncé
  1. Résoudre le système $$\left\{ \begin{array}{rcl} x\wedge y&=&18\\ x\vee y&=&540 \end{array}\right.$$ avec $(x,y)\in\mathbb N^2$.
  2. Généralisation : trouver une condition nécessaire et suffisante sur $d$ et $m$ pour qu'il existe $(x,y)\in\mathbb N^2$ tels que $x\wedge y=d$ et $x\vee y=m$.
Indication
Corrigé
Exercice 16 - Équation avec pgcd et ppcm [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Trouver tous les couples d'entiers $(x,y)\in\mathbb N^2$ tels que $x\vee y+11(x\wedge y)=203$.
Indication
Corrigé
Enoncé
Soient $a,m,n\in\mathbb N^*$ avec $a\geq 2$ et $m\leq n$. On note $d=(a^n-1)\wedge (a^m-1)$ et $r$ le reste dans la division euclidienne de $n$ par $m$.
  1. Montrer que $a^n\equiv a^r\ [a^m-1]$.
  2. En déduire que $d=(a^r-1)\wedge (a^m-1)$, puis que $d=a^{n\wedge m}-1$.
  3. A quelle condition $a^m-1|a^n-1$?
Indication
Corrigé
Exercice 18 - Irrationalité de $\sqrt 2$ [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le but de cet exercice est de démontrer que $\sqrt 2$ est irrationnel en utilisant l'algorithme d'Euclide. On raisonne par l'absurde et on suppose qu'il existe deux entiers strictement positifs $a$ et $b$ tels que $\sqrt 2=a/b$. On pose $c=\sqrt 2+1$.
  1. Vérifier que $a=b+\frac bc$, puis que $c=2+\frac 1c$.
  2. Démontrer que $\frac bc$ est un entier, et qu'il est égal au reste $r_1$ de la division euclidienne de $a$ par $b$. Quel est le quotient $q_1$ de cette division?
  3. Montrer que dans la division euclidienne de $b$ par $r_1$, le quotient est $q_2=2$ et le reste est $r_2=\frac{r_1}c$.
  4. Soit $n$ un entier supérieur ou égal à 2. Démontrer que l'algorithme d'Euclide appliqué au couple $(a,b)$ comporte au moins $n$ étapes, que le $n$-ième quotient est $q_n=2$, et que le $n$-ième reste est $r_n=\frac{r_{n-1}}c$.
  5. Conclure.
Indication
Corrigé