Informations

Vous devez être inscrit pour accéder à ces informations.

Ceci vous permet de visualiser les ressources déjà vues et marquer à revoir celles qui nécessitent d'être retravaillées.

Inscrivez vous gratuitement ici....

Contenu

PGCD, théorème de Bezout et de Gauss

Points de coordonnées entières d’une droite

Algorithme

Devoir d'entraînement | temps recommandé 20mn ou plus | Niveau 3 difficulté supérieure | exercices complémentaires et devoirs d’entraînement |
Exercice 1 (8 points)
Pour chaque question, dire si l'affirmation est vraie ou fausse en justifiant la réponse.
Chaque question est indépendante.
  1. On considère l'équation $(E)$: $2x+11y=7$ avec $x$ et $y$ entiers relatifs.
    Affirmation: Les seuls couples solutions de $(E)$ sont de la forme $(22k-2;-4k+1)$ avec $k$ appartenant à $\mathbb{Z}$.
    Aide

    Chercher une solution de $(E)$ et vérifier si il existe une valeur de $k$ donnant cette solution

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  2. $a$ et $b$ sont deux entiers relatifs quelconques et $n$ et $p$ deux entiers naturels premiers entre eux.
    Affirmation: $a\equiv b$ ($p$) si et seulement si $na\equiv nb$ ($p$)
    Rappel cours

    Addition, multiplication et exposant
    $n$ est un entier naturel superieur ou égal à 2 et $a$, $b$, $c$ et $d$ quatre entiers relatifs tels que $a\equiv b$ $(n)$ et $c\equiv d$ $(n)$
    - addition: $a+c\equiv c+d$ $(n)$
    - multiplication $ac\equiv bd$ $(n)$
    - exposant: $a^k \equiv b^k$ $(n)$
    Théorème de Gauss
    Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.
    Si $a$ divise $bc$ et PGCD$(a,b)=1$ alors $a$ divise $c$.

    Aide

    Démontrer l'implication puis la réciproque
    On a $na-nb\equiv 0$ (p$) soit $n(a-b)=kp$ avec $k\in \mathbbb{Z}$ et $n$ et $p$ premiers entre eux

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  3. $n$ est un entier naturel non nul congru à $1$ modulo $7$ alors PGCD de $3n+4$ et de $4n+3$ est égal à $7$.
    Aide

    Effectuer la division euclidienne de $4n+3$ par $3n+4$

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  4. Soient $a$ et $b$ deux entiers naturels.
    Affirmation: Si il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=2$ alors PGCD$(a,b)=2$
    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

Exercice 2 (12 points)
Pour tout couple d'entiers relatifs non nuls $(a,b)$, on note pgcd$(a,b)$ le plus grand diviseur commun de $a$ et $b$.
Le plan est muni d'un repère $(O;\overrightarrow{i};\overrightarrow{j})$.
  1. Exemple. Soit $\Delta_1$ la droite d'équation $y = \dfrac{5}{4} x - \dfrac{2}{3}$.
    1. Montrer que si $(x,y)$ est un couple d'entiers relatifs alors l'entier $15x - 12y$ est divisible par $3$.
      Aide

      $15x-12y=3(5x-4y)$

      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

    2. Existe-il au moins un point de la droite $\Delta_1$ dont les coordonnées sont deux entiers relatifs ? Justifier.
      Aide

      $y_0=\frac{5}{4}x_0-\frac{2}{3}\Longleftrightarrow 15x_0-12y_0=8$

      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

    Généralisation
    On considère désormais une droite $\Delta$ d'équation $(E)$: $ y = \dfrac{m}{n} x - \dfrac{p}{q}$ où $m, n, p$ et $q$ sont des entiers relatifs non nuls tels que pgcd$(m,n) = $pgcd$(p, q) = 1$.
    Ainsi, les coefficients de l'équation $(E)$ sont des fractions irréductibles et on dit que $\Delta$ est une droite rationnelle.
    Le but de l'exercice est de déterminer une condition nécessaire et suffisante sur $m, n, p$ et $q$ pour qu'une droite rationnelle $\Delta$ comporte au moins un point dont les coordonnées sont deux entiers relatifs.
  2. On suppose ici que la droite $\Delta$ comporte un point de coordonnées $\left(x_0,\:y_0\right)$ où $x_0$ et $y_0$ sont des entiers relatifs.
    1. En remarquant que le nombre $n y_0 - m x_0$ est un entier relatif, démontrer que $q$ divise le produit $np$.
      Aide

      $y_0=\frac{m}{n}x_0-\frac{p}{q}\Longleftrightarrow qmx^0-qny_0=qm x_0=np$

      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

    2. En déduire que $q$ divise $n$.
      Rappel cours

      Théorème de Gauss
      Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.
      Si $a$ divise $bc$ et PGCD$(a,b)=1$ alors $a$ divise $c$.

      Aide

      $q$ divise $np$ et $q$ et $p$ premiers entre eux

      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

  3. Réciproquement, on suppose que $q$ divise $n$, et on souhaite trouver un couple $\left(x_0,\:y_0\right)$ d'entiers relatifs tels que $y_0 = \dfrac{m}{n}x_0 - \dfrac{p}{q}$.
    1. On pose $n = qr$, où $r$ est un entier relatif non nul.
      Démontrer qu'on peut trouver deux entiers relatifs $u$ et $v$ tels que $qru - mv = 1$.
      Rappel cours

      Théorème de Bezout
      Les entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement si il existe un couple d'entiers relatifs $(u;v)$ tel que $au+bv=1$

      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

    2. En déduire qu'il existe un couple $\left(x_0,\:y_0\right)$ d'entiers relatifs tels que $y_0 = \dfrac{m}{n} x_0 - \dfrac{p}{q}$.
      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

  4. Soit $\Delta$ la droite d'équation $y = \dfrac{3}{8} x - \dfrac{7}{4}$.
    Cette droite possède-t-elle un point dont les coordonnées sont des entiers relatifs ? Justifier.
    Aide

    Utiliser les questions 1 et 2

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  5. On donne l'algorithme suivant :
    1. Justifier que cet algorithme se termine pour toute entrée de $M, N, P, Q$, entiers relatifs non nuls tels que pgcd$(M, N)$ = pgcd$(P, Q) = 1$. Soit $\Delta$ la droite d'équation $y=\frac{M}{N}x-\frac{P}{Q}$.
      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements

    2. Que permet-il d'obtenir ?
      Solution

      Vous devez être abonné pour accéder à ce contenu...
      Infos abonnements


Vous devez être abonné pour accéder à ce contenu...Infos abonnements
error: Ce contenu est protégé