%+----------------------------------------------------------------------------+
%|                             Exercices pggd                                 |
%+----------------------------------------------------------------------------+

\input exos
\fiche{Pgcd}

%----------------------------------------------------------------------
\ex $a$ est premier à $b$ $⇒\pgcd(a,bc)=\pgcd(a,c)$

Soient $a,b,c ∈ ℤ$ tels que $a∧b = 1$. Montrer que $a∧(bc) = a∧c$.


%----------------------------------------------------------------------
\ex $\pgcd(a+b, \ppcm(a,b))$

Soient $a,b$ entiers, $d = a∧b$, $m = a∨b$. Chercher $(a+b)∧m$.
\reponse{$=d$.}

%----------------------------------------------------------------------
\ex $\pgcd((a-b)³, a³-b³)$

Soient $a,b ∈ ℤ$. Chercher $(a-b)³∧(a³ - b³)$.
\reponse{$= |a-b|(a∧b)²$ ou $3|a-b|(a∧b)²$.}

%----------------------------------------------------------------------
\ex $\pgcd( n³ + n, 2n + 1 )$

Soit $n ∈ ℕ$. Chercher $(n³+n)∧(2n+1)$.
\reponse{$8(n³ + n) = (2n+1)(4n²-2n+5) - 5 ⇒ d = (2n+1)∧5
         ⇒ d=5$ si $n≡2\pmod5$, $d=1$ sinon.}

%----------------------------------------------------------------------
\ex $\pgcd( 15n²+8n+6, 30n²+21n+13 )$

Soit $n ∈ ℕ$. Chercher $(15n²+8n+6)∧(30n²+21n+13)$.
\reponse{$=1$.}

%----------------------------------------------------------------------
\ex pgcd et ppcm imposés

Soient $d,m ∈ ℕ^*$. Donner une condition nécéssaire et suffisante sur
$d$ et $m$ pour qu'il existe $a,b ∈ ℤ$ tels que $a∧b = d$ et $a∨b = m$.

Résoudre ce problème pour $d = 50$ et $m = 600$.
\reponse{$⦃a,b⦄ ∈ ⦃⦃50,600⦄,⦃150,200⦄⦄$.}

%----------------------------------------------------------------------
\ex $\ppcm(x,y) + 11\pgcd(x,y) = 203$

Trouver les couples d'entiers $(x,y) ∈ ℤ²$ tels que : $x∨y + 11(x∧y) = 203$.
\reponse{$⦃a,b⦄ ∈ ⦃⦃1,192⦄,⦃3,32⦄,⦃7,126⦄,⦃14,63⦄⦄$.}

%----------------------------------------------------------------------
\ex $x²+y² = 85113$, $\ppcm(x,y) = 1764$

Résoudre : $\cases{x²+y² = 85113\cr x∨y = 1764.\cr}$
\reponse{$⦃x,y⦄ = ⦃147,252⦄$.}

%----------------------------------------------------------------------
\ex $\ppcm(x,y) = 210\pgcd(x,y)$, $y - x = \pgcd(x,y)$

Résoudre : $\cases{ x∨y = 210(x∧y)\cr y-x = x∧y.}$
\reponse{$x = 14k$, $y = 15k$.}

%----------------------------------------------------------------------
\ex $\pgcd(x,y) = x+y-1$

Résoudre dans $ℤ$ : $x∧y = x + y - 1$.
\reponse{$x$ impair, $y = 2-x$.}

%----------------------------------------------------------------------
\ex $\ppcm(x,y) = x+y-1$

Résoudre dans $ℤ^*$ : $x∨y = x + y - 1$.
\reponse{$x=1$ ou $y=1$.}

%----------------------------------------------------------------------
\ex $\pgcd(x,y) = x-y$, $\ppcm(x,y) = 300$

Résoudre dans $ℕ^*$ :
$\cases{x∧y = x-y \cr x∨y = 300.}$
\reponse{$(300,150)$, $(150,100)$, $(100,75)$, $(75,60)$, $(60,50)$.}

%----------------------------------------------------------------------
\ex $\pgcd( a^n - 1, a^m - 1 )$

Soient $a,m,n ∈ ℕ^{*}$, $a⩾2$, et $d = (a^n - 1)∧(a^m - 1)$.

\qq   Soit $n = qm + r$ la division euclidienne de $n$ par $m$.
      Démontrer que $a^n ≡ a^r \pmod {a^m - 1}$.
      \reponse{$a^m - 1│(a^{qm} - 1)a^r = a^n - a^r$.}
\qq   En déduire que $d = (a^r - 1)∧(a^m - 1)$, puis $d = a^{(n∧m)} - 1$.
      \reponse{$A∧(AQ+R) = A∧R$. Algorithme d'Euclide sur les exposants de $a$.}
\qq   A quelle condition $a^m - 1$ divise-t-il $a^n-1$ ?
      \reponse{ssi $m│n$.}

%----------------------------------------------------------------------
\ex pgcd multiple

Soient $a_1, …, a_n ∈ ℕ^{*}$ et $b_i = ℿ_{j \ne i} a_j$.
Montrer que $a_1, …, a_n$ sont {\it deux à deux\/} premiers entre eux si et
seulement si $b_1, …, b_n$ sont premiers entre eux {\it dans leur ensemble}.


\bye
