Aller au contenu

Feuille d'exercices sur les diviseurs et le pgcd

Exercice 1 Vrai ou Faux

Soient \(a\) et \(b\) deux entiers naturels non nuls.

  1. Si \(a\) divise \(bc\) et si \(a\) ne divise pas \(b\) alors \(a\) divise \(c\).

  2. Si \(b\) et \(c\) divisent \(a\) alors \(bc\) divise \(a\).

  3. Les nombres \(a\) et \(2a+1\) sont premiers entre eux.

  4. Les nombres \(3b\) et \(2b+1\) sont premiers entre eux.

Exercice 2

DĂ©composer \(140\) et \(175\) en produit de nombres premiers.

En déduire \(\mathrm{pgcd}(455, 175)\).

Exercice 3

Calculer le pgcd de \(195\) et \(143\) avec l'algorithme d'Euclide.

Exercice 4

On considère la fonction Python suivante dont les arguments \(a\) et \(b\) sont des entiers naturels non nuls.

def mystere(a,b):
    n=1
    while n<=a and n<=b:
        if a%n==0 and b%n==0:
            p=n
        n=n+1
    return p

  1. Que renvoie l’instruction mystere(142,76) ?

  2. Quel est le rĂ´le de cette fonction ?

Exercice 5

DĂ©terminer le pgcd et un couple de BĂ©zout des couples d'entiers \((a, b)\) suivants :

  1. \(a = 33\) et \(b = 24\)

  2. \(a = 37\) et \(b = 27\)

  3. \(a = 270\) et \(b = 105\)

Exercice 6

Montrer qu'il n'existe pas d'entiers \(m\) et \(n\) tels que \(m+n = 101\) et \(\mathrm{pgcd}(m,n)=3\).

Exercice 7

DĂ©terminer tous les entiers naturels \(a\) tels que \(600 < a <1100\) et \(\mathrm{pgcd}(a ; 630)=105\).

Exercice 8

Montrer que, pour tout entier naturel n, \(\mathrm{pgcd}(3n+4;4n+3)=7 \Leftrightarrow n \equiv 1 [7]\).

Exercice 9

Soit \(n\) un entier naturel tel que \(\mathrm{pgcd}(n;18)=3\), \(\mathrm{pgcd}(n;175)= 5\).

  1. Quel est le pgcd de \(n\) et \(42\) ? De \(n\) et \(30\) ?

  2. Héloïse affirme : « Si \(n\) est plus petit que \(100\), le problème n'a qu'une seule solution ». A-t-elle raison ? Justifier.

Exercice 10

Soient \(a\), \(b\) et \(c \in \mathbb{Z}\), avec \((a, b) \neq (0, 0)\).

On souhaite résoudre l’équation \(ax + by = c\), notée \((E)\), d'inconnue \((x, y) \in \mathbb{Z}^2\).

  1. Montrer que \((E)\) n'a pas de solution si \(c\) n'est pas un multiple de \(a \wedge b\).

  2. On suppose dans cette question que \(a \wedge b\) divise \(c\).

    a. En considérant un couple de coefficients de Bézout de \((a, b)\), montrer que \((E)\) possède une solution \((x_0, y_0)\).

    b. En s'appuyant sur \((x_0, y_0)\), résoudre complètement (E)

  3. RĂ©soudre les Ă©quations d'inconnue \((x, y) \in \mathbb{Z}^2\) :

    a. \(2x + 5y = 13\)

    b. \(14x - 24y = 6\)

    c. \(6x - 14y = 9\)

Exercice 11

  1. DĂ©terminer le pgcd de \(4^5-1\) et de \(4^6-1\).

  2. On considère la suite \((u_n)\) définie par \(u_0=0\) et pour tout entier naturel \(n\), \(u_{n+1}= 4u_n+1\).

    a. Prouver par récurrence que pour tout entier naturel \(n\), \(u_n\) est un entier naturel.

    b. En déduire, pour tout entier naturel \(n\), le pgcd de \(u_n\) et de \(u_{n+1}\).

  3. Soit \((v_n)\) la suite définie pour tout entier naturel \(n\) par \(v_n= u_n+\dfrac{1}{3}\).

    a. Montrer que la suite \((v_n)\) est géométrique et déterminer sa raison et son premier terme.

    b. Exprimer \(v_n\) puis \(u_n\) en fonction de \(n\).

    c. DĂ©terminer, pour tout entier naturel \(n\), le pgcd de \(4^{n+1}-1\) et de \(4^n-1\).

Exercice 12

\(a\) et \(b\) sont deux entiers naturels. Le pgcd de \(a\) et \(b\) est Ă©gal Ă  \(2\). Quand on applique l'algorithme d'Euclide Ă  a et b, le premier reste nul est \(r_4\) et les quotients successifs obtenus sont : \(q_1 = 1\), \(q_2 = 3\), \(q_3 = 1\), \(q_4 = 2\). DĂ©terminer \(a\) et \(b\).

Exercice 13

Le pgcd de deux nombres est \(12\) ; les quotients successifs obtenus dans le calcul de ce pgcd par l'algorithme d’Euclide sont \(8\), \(2\) et \(7\). Trouver ces deux nombres.

Exercice 14

On range 461 pots de yaourt dans des caisses identiques. La règle est de ne pas commencer une caisse avant d'avoir fini la précédente. À la fin, on a rangé les pots dans 14 caisses. Combien de pots contient une caisse pleine ? Combien de pots contient la dernière caisse ?

Exercice 15

Soient \(a\) et \(b\) deux entiers naturels non nuls tels que \(\mathrm{pgcd}(a, b) = 1\). Montrer que \(\mathrm{pgcd}(a + b, ab) = 1\).

Exercice 16

Programmer en Python un algorithme qui prend en argument deux entiers naturels et qui calcule leur pgcd en utilisant l'algorithme d'Euclide.

Exercice 17

On dit que \(x\) est un inverse de \(a\) modulo \(n\) lorsque \(ax \equiv 1 [n]\).

  1. a. Justifier que \(x\) est l'inverse de \(a\) modulo \(n\) si et seulement si il existe un entier relatif \(y\) tel que \(ax-ny=1\).

    b. En déduire que si \(\mathrm{pgcd}(a;n)=1\) alors \(a\) possède un inverse modulo \(n\).

  2. a. DĂ©terminer un inverse de \(5\) modulo \(7\).

    b. En déduire les nombres entiers relatifs \(x\) tels que \(5x \equiv 3 [7]\)

Exercice 18

  1. a. Justifier qu'il existe deux entiers relatifs \(u\) et \(v\) tels que \(17u-43v=1\).

    b. DĂ©terminer deux entiers relatifs \(u\) et \(v\) tels que \(17u-43v=1\).

    c. En déduire un entier relatif \(x\) vérifiant \(17x \equiv 1 [43]\).

  2. En utilisant la question précédente, résoudre les équations suivantes dans \(\mathbb{Z}\)

    a. \(17x \equiv 1 [43]\)

    b. \(17x \equiv 8 [43]\)