%+-----------------------------------------------------------------------------»
%|                             Relation de Bezout                              |
%+-----------------------------------------------------------------------------¼

\input exos
\fiche{Relation de Bézout}


%---------------------------------------------------------------
\ex Équations à coefficients entiers
Soient $a,b,c$ trois entiers relatifs. On considère l'équation : $ax+by=c$,
dont on recherche les solutions dans $ℤ²$.

\qq Donner une condition nécéssaire et suffisante pour que cette équation
    admette une solution.
\qq Soit $(x₀,y₀)$ une solution du problème de Bézout : $ax₀ + by₀ = d$.
    Déterminer toutes les solutions de $ax + by = c$ en fonction de $a$, $b$,
    $c$, $d$, $x₀$ et $y₀$.
\qq Résoudre dans $ℤ²$ : $2520x - 3960y = 6480$.
    \reponse{$x=1+11k$, $y=-1+7k$.}

%---------------------------------------------------------------
\ex Équations à coefficients entiers
Résoudre dans $ℤ$ :

{\bf1)} $95x + 71y = 46$.
        \reponse{\qq $x = 67-71k$, $y = -89 + 95k$.}
{\bf2)} $20x - 53y = 3$.
        \reponse{\qq $x = 24 + 53k$, $y = 9 + 20k$.}
{\bf3)} $12x + 15y + 20z = 7$.
        \reponse{\qq $x = -49 + 20k - 5m$, $y = 49 - 20k + 4m$, $z = -7 + 3k$.}

%---------------------------------------------------------------
\ex Congruences simultanées
\qq Soient $a,b,a',b' ∈ ℤ$ avec $b ∧ b' = 1$.
    Montrer que le système : $\cases{x ≡ a \pmod b \cr x ≡ a' \pmod {b'} \cr}$
    possède des solutions et qu'elles sont congrues entre elles modulo $bb'$.
\qq Généraliser.

%---------------------------------------------------------------
\ex Congruences simultanées
Résoudre :

{\bf1)} $\cases{x≡\phantom-2 \pmod {140} \cr x≡ -3 \pmod {99}.\cr}$
        \reponse{\qq $x≡ 7422 \pmod {13860}$.}
{\bf2)} $\cases{x≡\phantom-3\pmod 4\cr x≡-2\pmod 3\cr x≡\phantom-7\pmod 5.\cr}$
        \reponse{\qq $x≡ 7 \pmod {60}$.}

%---------------------------------------------------------------
\ex Congruences simultanées
Une bande de 17 pirates dispose d'un butin composé de $N$ pièces d'or
d'égale valeur. Ils décident de se le partager également et de donner le
reste au cuisinier (non pirate). Celui ci reçoit 3 pièces.
\medskip
Mais une rixe éclate et 6 pirates sont tués. Tout le butin est reconstitué et
partagé entre les survivants comme précédemment; le cuisinier reçoit alors 4
pièces.
\medskip
Dans un naufrage ultérieur, seuls le butin, 6 pirates et le cuisinier sont
sauvés. Le butin est à nouveau partagé de la même manière et le cuisinier
reçoit 5 pièces.
\medskip
Quelle est alors la fortune minimale que peut espérer le cuisinier lorsqu'il
décide d'empoisonner le reste des pirates~?
\reponse{785.}

%---------------------------------------------------------------
\ex Décomposition à coefficients positifs
Soient $a,b ∈ ℕ^*$ premiers entre eux.
Montrer que~: $∀x⩾ab$, $∃u,v∈ℕ$ tels que $au + bv = x$.


\bye

