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\):
-
Vérifier que pour tout \(n\) : \(n^2+5-(n-3)(n+3)=14\)
Corrigé
\(n^2+5-(n^2-9)=5+9=14\)
-
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)
-
Quel est le reste de la division de \(2018\) par \(7\) ?
Corrigé
\(2018=7 \times 288 +2\) (en posant la division).
-
Vérifier que \(2^3 \equiv 1[7]\)
Corrigé
\(2^3=8=7+1\) d'où \(2^3 \equiv 1[7]\)
-
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}\).
-
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]\).
-
Donner le quotient et le reste de la division euclidienne de \(11^2\) par \(17\).
Corrigé
\(121 = 7 \times 17 + 2\)
-
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)
-
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]\)
-
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]\)
-
Déterminer un inverse de \(x=2\).
Corrigé
\(2 \times 3=6 \equiv 1 [5]\) donc \(3\) est un inverse de \(2\) modulo 5.
-
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.
-
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\).
-
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\}\)