Aller au contenu

Devoir divisibilité et congruences

Les détails des calculs sont attendus

L'usage de la calculatrice n'est pas autorisé

Durée : 55 minutes

Exercice 1 (2 points)

On recherche les entiers relatifs \(n>3\) tels que \(n-3\) divise \(n^2+5\):

  1. Vérifier que pour tout \(n\) : \(n^2+5-(n-3)(n+3)=14\)

    Corrigé

    \(n^2+5-(n^2-9)=5+9=14\)

  2. Trouver tous les entiers relatifs \(n>3\) tels que \(n-3\) divise \(n^2+5\).

    Corrigé

    Si \(n-3\) divise \(n^2+5\), alors \(n-3\) divise toute combinaison linéaire de \(n^2+5\) et de \(n-3\), donc \(n-3\) divise \(n^2+5-(n-3)(n+3)=14\)

    Les diviseurs de 14 sont \(\left\{-14;-7;-2;-1;1;2;7;14\right\}\).

    D'où \(n-3 \in \left\{-14;-7;-2;-1;1;2;7;14\right\} \Rightarrow n \in \left\{-11;-4;1;2;4;5;10;17\right\}\)

    Avec \(n>3\), on obtient \(n \in \left\{4;5;10;17\right\}\)

Exercice 2 (2,5 points)

  1. Quel est le reste de la division de \(2018\) par \(7\) ?

    Corrigé

    \(2018=7 \times 288 +2\) (en posant la division).

  2. Vérifier que \(2^3 \equiv 1[7]\)

    Corrigé

    \(2^3=8=7+1\) d'où \(2^3 \equiv 1[7]\)

  3. Quel est le reste de \(2018^{2018}\) dans la division par \(7\) ?

    Corrigé

    \(2018 \equiv 2 [7] \Rightarrow 2018^{2018} \equiv 2^{2018} [7]\)

    \(\phantom{2018 \equiv 2 [7]} \Rightarrow 2018^{2018} \equiv 2^{3 \times 96 \times 7+2} [7]\)

    \(\phantom{2018 \equiv 2 [7]} \Rightarrow 2018^{2018} \equiv 2^2 \times \left(2^{3}\right)^{7 \times 96} [7]\)

    \(\phantom{2018 \equiv 2 [7]} \Rightarrow 2018^{2018} \equiv 4 [7]\) car \(2^3 \equiv 1 [7]\)

    Le reste de \(2018^{2018}\) dans la division par \(7\) est donc 4.

Exercice 3 (4 points)

Pour tout entier naturel \(n\), on pose \(u_n=11^{2n} +2^{n+4}\).

  1. Calculer \(u_0,u_1\). Vérifier que \(u_1 \equiv 0[17]\)

    Corrigé

    \(u_0=11^0+2^4=17\) et \(u_1=11^2+2^5=153\)

    Or \(153=17 \times 9\) d'où \(u_1 \equiv 0[17]\).

  2. Donner le quotient et le reste de la division euclidienne de \(11^2\) par \(17\).

    Corrigé

    \(121 = 7 \times 17 + 2\)

  3. Démontrer que, pour tout \(n\) : \(u_n\) est un multiple de \(17\).

    Corrigé

    \(u_n=11^{2n} +2^{n+4} \Rightarrow u_n=(11^2)^n+2^4 \times 2^n\)

    \(\phantom{u_n=11^{2n} +2^{n+4}} \Rightarrow u_n \equiv 2^n+ (-1) \times 2^n [17]\)

    \(\phantom{u_n=11^{2n} +2^{n+4}} \Rightarrow u_n \equiv 0 [17]\)

    $\Rightarrow u_n est bien un multiple de 17, pour tout \(n\).

Exercice 4 (3 points)

  1. Montrer que, pour tout entier naturel \(n\), \(1000n \equiv n [111]\)

    Corrigé

    \(1000=111 \times 9 +1 \Rightarrow 1000 \equiv 1 [111]\)

    \(\phantom{1000=111 \times 9 +1} \Rightarrow 1000n \equiv n [111]\)

  2. Expliquer comment on trouve le reste de la division par \(111\) du nombre \(123456789\), sans poser la division.

    Corrigé

    \(123456789=789+123456 \times 1000\)

    \(\Rightarrow 123456789 \equiv 789+123456 \times 1000 [111]\)

    \(\Rightarrow 123456789 \equiv 789+456+123 \times 1000 [111]\)

    \(\Rightarrow 123456789 \equiv 789+456+123 \times 1000 [111]\)

    \(\Rightarrow 123456789 \equiv 7 \times 111 +12 + 4 \times 111+12+111+12 [111]\)

    \(\Rightarrow 123456789 \equiv 36 [111]\)

    Le reste de la division par \(111\) du nombre \(123456789\) est \(36\).

Exercice 5 (4 points)

On appelle inverse de \(x\) modulo 5, un entier \(y\) tel que \(xy \equiv 1 [5]\)

  1. Déterminer un inverse de \(x=2\).

    Corrigé

    \(2 \times 3=6 \equiv 1 [5]\) donc \(3\) est un inverse de \(2\) modulo 5.

  2. Est-il vrai que 4 est son propre inverse ?

    Corrigé

    \(4 \times 4=16 \equiv 1 [5] \equiv 1 [5]\) donc \(4\) est bien son propre inverse.

  3. Le nombre \(5\) admet-il un inverse ? Expliquer.

    Corrigé

    Supposons que \(5\) admette un inverse noté \(x\), alors \(5x \equiv 1 [5]\), or \(5 \equiv 0 [5] \Rightarrow 5x \equiv 0 [5]\), ce qui est absurde car \(0\) n'est pas congru à \(1\) modulo \(5\).

  4. Résoudre dans \(\mathbb{Z}\) les équations:

    \((E_1) \quad 9 x \equiv 12 [5]\)

    \((E_2) \quad 2x+3 \equiv 3 [5]\)

    Corrigé

    \(9x \equiv 12 [5] \Rightarrow 4 \times 9x \equiv 4 \times 12 [5] \Rightarrow x \equiv 3 [5]\)

    L'ensemble \(\text{S}_{E_1}\) des solutions de \(E_1\) s'écrit \(\left\{5k+3;k \in \mathbb{Z}\right\}\)

    \(2x+3 \equiv 3 [5] \Rightarrow 2x \equiv 0 [5] \Rightarrow 3 \times 2x \equiv 0 [5] \Rightarrow x \equiv 0 [5]\)

    L'ensemble \(\text{S}_{E_2}\) des solutions de \(E_2\) s'écrit \(\left\{5k;k \in \mathbb{Z}\right\}\)