Sujet A.3.5 Congruences
Choisir
un exercice, puis le résoudre
:
Signaler une erreur
Signaler une erreur
Exercice a
Démontrer que, pour tout $\,n\app\bb N\sp{1.5},\,$ l'entier $\,2^n+5^n\,$ n'est pas multiple de $\,3\sp{1.5}.\,$
relation de congruence dans $\bb Z$
Deux entiers relatifs $\,x\,$ et $\,y\,$ sont congrus modulo $\,n\app\bb N\,$ ssi :
$\displaystyle{}\iex k\app\bb Z\sp{1.5},\ \,x-y=k\sp{1.5}n$
C'est une relation d'équivalence sur $\,\bb Z\sp{1.5},\,$ notée : $\,x\sp{-1.5}\equiv\sp{-1.5} y\,[\sp{.75}n\sp{.75}]\sp{1.5}.\,$
congruence et opérations
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
indication
Comparer les restes modulo $\,3\,$ de $\,2^n\,$ et les restes modulo $\,3\,$ de $\,5^n\sp{1.5}.\,$
réponse
On démontre bien que, quel que soit $\,n\app\bb N\sp{1.5},\,$ l'entier $\,2^n+5^n\,$ n'est pas multiple de $\,3\sp{1.5}.\,$
correction
Soient $\,q\app\bb N\,$ et $\,r\app\{0,1\}\,$ le quotient et le reste de la
Pour $\,a,b\app\bb Z\,$ et $\,b\neq0\sp{1.5},\,$ il existe un et un seul $\,(q,r)\app\bb Z^2\,$ tel que :
division
euclidienne de $\,n\,$ par $\,2\sp{1.5}.\,$
On a les relations de
$\displaystyle{}a=b\sp{1.5}q+r\,\txt{et}\,0\leq r< |b|$
$q$ et $r$ sont le quotient et le reste de la division euclidienne de $a$ par $b\sp{1.5}.$
Deux entiers relatifs $\,x\,$ et $\,y\,$ sont congrus modulo $\,n\app\bb N\,$ ssi :
congruence :
$\,4
\equiv 1\ [\sp{.75}3\sp{.75}]\,$ et $\,25\equiv1\ [\sp{.75}3\sp{.75}]\,;\,$ par
$\displaystyle{}\iex k\app\bb Z\sp{1.5},\ \,x-y=k\sp{1.5}n$
C'est une relation d'équivalence sur $\,\bb Z\sp{1.5},\,$ notée : $\,x\sp{-1.5}\equiv\sp{-1.5} y\,[\sp{.75}n\sp{.75}]\sp{1.5}.\,$
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
produits,
elles impliquent que :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
$\displaystyle{}\ptt q\app\bb N,\ \big(2^{2\sp{.75}q}=\ 4^q\equiv1\ [\sp{.75}3\sp{.75}]\,\txt{et}\,
5^{2\sp{.75}q}=25^q\equiv1\ [\sp{.75}3\sp{.75}]\big)$
On en déduit, pour tout $\,n\app\bb N\sp{1.5},\,$ les relations de congruence :
$\eqalign{2^n=2^{2\sp{.75}q+r}&\equiv\ 4^q\sp{1.5}.\sp{-1.5}2^r &\equiv2^r\ [\sp{.75}3\sp{.75}]\\
5^n=5^{2\sp{.75}q+r}&\equiv25^q\sp{1.5}.\sp{-1.5}5^r&\equiv5^r\ [\sp{.75}3\sp{.75}]}$
On obtient alors, par
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
somme
de congruences, les deux éventualités :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
$\eqalign{\Syst{\smh0{2^n+5^n\equiv 2^0+5^0}\equiv 2\ [\sp{.75}3\sp{.75}]&\txt{si}r=0\\
2^n+5^n\equiv 2^1+5^1\equiv 1\ [\sp{.75}3\sp{.75}]&\txt{si}r=1}}$
Il s'ensuit qu'on n'a jamais : $\,2^n+5^n\equiv 0\ [\sp{.75}3\sp{.75}]\,;\,$ quel que soit $\,n\app\bb N\sp{1.5},\,$ l'entier $\,2^n+5^n\,$ n'est pas multiple de $\,3\sp{1.5}.\,$
Signaler une erreur
Signaler une erreur
Exercice b
Déterminer l'ensemble des entiers relatifs $\,x\,$ tels que l'entier $\,x^2-4\sp{.75}x+3\,$ soit divisible par $\,5\sp{1.5}.\,$
relation de congruence dans $\bb Z$
Deux entiers relatifs $\,x\,$ et $\,y\,$ sont congrus modulo $\,n\app\bb N\,$ ssi :
$\displaystyle{}\iex k\app\bb Z\sp{1.5},\ \,x-y=k\sp{1.5}n$
C'est une relation d'équivalence sur $\,\bb Z\sp{1.5},\,$ notée : $\,x\sp{-1.5}\equiv\sp{-1.5} y\,[\sp{.75}n\sp{.75}]\sp{1.5}.\,$
congruence et opérations
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
indication
1
Exprimer la relation demandée sous forme de congruence modulo $\,5\sp{1.5}.\,$
indication
2
Modifier, modulo $\,5\sp{1.5},\,$ l'expression de $\,x^2-4\sp{.75}x+3\,$ jusqu'à obtenir une expression factorisable.
réponse
On obtient pour l'ensemble $\sc S$ des $\,x\app\bb Z\,$ tels que l'entier $\,x^2-4\sp{.75}x+3\,$ soit divisible par $\,5:\,$
$\displaystyle{}\sc S=\ens{5\sp{1.5}k+1}{k\app\bb Z}\cup\ens{5\sp{1.5}k+3}{k\app\bb Z}$
correction
En termes de
Deux entiers relatifs $\,x\,$ et $\,y\,$ sont congrus modulo $\,n\app\bb N\,$ ssi :
congruence,
l'entier $\,x^2-4\sp{.75}x+3\,$ est
$\displaystyle{}\iex k\app\bb Z\sp{1.5},\ \,x-y=k\sp{1.5}n$
C'est une relation d'équivalence sur $\,\bb Z\sp{1.5},\,$ notée : $\,x\sp{-1.5}\equiv\sp{-1.5} y\,[\sp{.75}n\sp{.75}]\sp{1.5}.\,$
$\,a\app\bb Z\,$ est un diviseur de $\,b\app\bb Z\,$ ssi $\,b\,$ est un multiple de $\,a\sp{1.5},\,$ soit :
divisible
par $\,5\,$ si et seulement si :
$\,x^2-4\sp{.75}x+3\equiv0\ [5]\sp{1.5}.\,$
On va utiliser la
$\displaystyle{}\iex q\app\bb Z,\ b=a\sp{1.5}q$
On écrit : $\,a\sp{1.5}\big|\sp{1.5}b\sp{1.5},\,$ et $\,a\sp{1.5}\bb Z\,$ désigne l'ensemble des multiples de $\,a\,$ dans $\bb Z\sp{1.5}.$
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
compatibilité
de la relation de congruence modulo $\,5\,$ avec les opérations usuelles.
Compte tenu des relations : $\,-4\equiv1\ [5]\txt{et}3\equiv-2\ [5]\sp{1.5},\,$ on peut écrire le terme $\,x^2-4\sp{.75}x+3\,$ sous diverses formes :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
$\eqalign{x^2-4\sp{.75}x+3\,&\equiv& \!x^2+x+3\ [5]\\&\equiv&\! x^2+x-2\ [5]\\[-.5ex]
&\sp{-15}\txt{etc.}\sp{-10}&}$
On retient parmi ces différentes expressions celle qui, avec des
Une racine de $\,P\app\bb K[X]\,$ est un $\,\alpha\app\bb K\,$ tel que $\,P(\alpha)=0\,.\,$
$\,\alpha\app\bb K\,$ est racine de $\,P\app\bb K[X]\,$ ssi $\,(X\!-\!\alpha)\,$ divise le polynôme $P.$
racines
évidentes, se factorise facilement :
$\eqalign{x^2-4\sp{.75}x+3\equiv\,0\ [5]&\Ssi&\ \ \ x^2+x-2&\equiv\ 0\ [5]\\ &\Ssi&(x-1)\sp{.75}(x+2)&\equiv\ 0\ [5]}$
Le nombre $\,5\,$ étant
Un nombre premier est un entier naturel $\,p\neq1\sp{1.5},\,$ ayant pour seuls diviseurs positifs $\,1\,$ et $\,p\sp{1.5}.\,$
L'ensemble des nombres premiers est un ensemble infini.
premier,
il divise $\,(x-1)\sp{.75}(x+2)\,$ si et seulement si il
Un nombre premier $p$ divise un produit d'entiers relatifs $a$ et $b$ ssi il divise l'un d'entre eux :
divise
l'un des facteurs, c'est-à-dire que :
$\displaystyle{}p\op{|}\sp{1.5}(a\sp{1.5}b)\Ssi \big(\sp{1.5}p\sp{-1.5}\op{|}\sp{-1.5}a\,\text{ ou }\,p\sp{-1.5}\op{|}\sp{-1.5}b\sp{1.5}\big)$
$\displaystyle{}(x-1)\sp{.75}(x+2)\equiv\ 0\ [5]\Ssi\Syst{\ x&\equiv1\ [5]\\[-1ex]&\!\!\!\!\txt{ou}\\[-1ex]
x&\equiv-2\equiv3\ [5]}$
L'ensemble des $\,x\app\bb Z\,$ tels que $\,x^2-4\sp{.75}x+3\,$ soit divisible par $\,5\,$ peut donc s'écrire comme une
Soient $A$ et $B$ deux parties d'un ensemble $E\,.$ La réunion de $A$ et $B$ est l'ensemble des $x\app E$ appartenant à $\,A\,$ ou à $\,B:\,$
réunion
:
$\displaystyle{}A\cup B=\ens{x\app E}{x\app A \,\text{ ou }\,x\app B}$
$\displaystyle{}\sc S=\ens{5\sp{1.5}k+1}{k\app\bb Z}\cup\ens{5\sp{1.5}k+3}{k\app\bb Z}$
Signaler une erreur
Signaler une erreur
Exercice c
Déterminer l'ensemble des entiers relatifs $\,x\,$ tels que $\,5\,x^2-3\sp{1.5}x+4\,$ soit divisible par $\,6\sp{1.5}.\,$
relation de congruence dans $\bb Z$
Deux entiers relatifs $\,x\,$ et $\,y\,$ sont congrus modulo $\,n\app\bb N\,$ ssi :
$\displaystyle{}\iex k\app\bb Z\sp{1.5},\ \,x-y=k\sp{1.5}n$
C'est une relation d'équivalence sur $\,\bb Z\sp{1.5},\,$ notée : $\,x\sp{-1.5}\equiv\sp{-1.5} y\,[\sp{.75}n\sp{.75}]\sp{1.5}.\,$
congruence et opérations
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
indication
1
Exprimer la relation demandée sous forme de congruence modulo $\,6\sp{1.5}.\,$
indication
2
Montrer que la relation demandée est équivalente à un système de deux congruences, l'une modulo $\,2\,$ et l'autre modulo $\,3\sp{1.5}.\,$
réponse
On obtient pour ensemble des solutions $\sc S$ l'ensemble des entiers qui ne sont pas multiples de $\,3:\,$
$\displaystyle{}\sc S=\ens{x\app\bb Z}{x\not\equiv0\ [\sp{.75}3\sp{.75}]}=\bb Z\!\setminus\!3\sp{.75}\bb Z$
correction
En termes de
Deux entiers relatifs $\,x\,$ et $\,y\,$ sont congrus modulo $\,n\app\bb N\,$ ssi :
congruence,
l'expression $\,5\,x^2-3\sp{1.5}x+4\,$ est
$\displaystyle{}\iex k\app\bb Z\sp{1.5},\ \,x-y=k\sp{1.5}n$
C'est une relation d'équivalence sur $\,\bb Z\sp{1.5},\,$ notée : $\,x\sp{-1.5}\equiv\sp{-1.5} y\,[\sp{.75}n\sp{.75}]\sp{1.5}.\,$
$\,a\app\bb Z\,$ est un diviseur de $\,b\app\bb Z\,$ ssi $\,b\,$ est un multiple de $\,a\sp{1.5},\,$ soit :
divisible
par $\,6\,$ si et seulement si :
$\,5\,x^2-3\sp{1.5}x+4\equiv0\ [\sp{.75}6\sp{.75}]\sp{1.5}.\,$
On va utiliser la
$\displaystyle{}\iex q\app\bb Z,\ b=a\sp{1.5}q$
On écrit : $\,a\sp{1.5}\big|\sp{1.5}b\sp{1.5},\,$ et $\,a\sp{1.5}\bb Z\,$ désigne l'ensemble des multiples de $\,a\,$ dans $\bb Z\sp{1.5}.$
La relation de congruence modulo $\,n\app\bb N\,$ sur $\bb Z$ est compatible avec la somme et le produit :
compatibilité
de la relation de congruence modulo $\,6\,$ avec les opérations usuelles.
Compte tenu des relations : $\,5\equiv-1\ [\sp{.75}6\sp{.75}]\txt{et}4\equiv-2\ [\sp{.75}6\sp{.75}]\sp{1.5},\,$ on peut écrire les équivalences :
$\displaystyle{}\syst{\ a&\equiv a'\sp{-1.5}&[\sp{.75}n\sp{.75}]\ \\[-.5ex] b&\equiv b'\sp{-1.5}&[\sp{.75}n\sp{.75}]}\Imp \syst{\sp{1.5}a+b&\equiv a'+b'\ [\sp{.75}n\sp{.75}]\\[-.5ex]
a\sp{1.5}b&\equiv a'\sp{1.5}b'\ [\sp{.75}n\sp{.75}]}$
$\eqalign{5\,x^2-3\sp{1.5}x+4\equiv\,0\ [\sp{.75}6\sp{.75}]&\Ssi&\ -x^2-3\sp{1.5}x-2\ &\equiv\,0\ [\sp{.75}6\sp{.75}]\\[.5ex] &\Ssi&-(x+1)\sp{1.5}(x+2)&\equiv\,0\ [\sp{.75}6\sp{.75}]}$
Le nombre $\,6\,$ n'étant pas
Un nombre premier est un entier naturel $\,p\neq1\sp{1.5},\,$ ayant pour seuls diviseurs positifs $\,1\,$ et $\,p\sp{1.5}.\,$
L'ensemble des nombres premiers est un ensemble infini.
premier,
on va utiliser sa
Tout entier naturel $\,n\geq2\,$ admet une et une seule décomposition de la forme :
décomposition
en facteurs premiers : $\,6=2\sp{-1.5}\times\sp{-1.5}3\,.\,$
Selon le critère de
$\displaystyle{}n=p_1^{\alpha_1}\!\dots\, p_r^{\alpha_r},\ \txt{avec}p_1 < \cdots < p_r$
où les $p_i$ sont des nombres premiers et où les $\alpha_i$ appartiennent à $\bb N^{\ast}\!.$
Soient $\,p_1,\dots,p_r\,$ des nombres premiers distincts, et $\,a\,$ et $\,b\,$ tels que :
divisibilité
relatif à ces décompositions, on a l'équivalence :
$\displaystyle{}a=p_{1}^{\alpha_1}\dots p_{r}^{\alpha_r}\txt{et}b=p_1^{\beta_1}\dots p_r^{\beta_r}\,\txt{pour} \alpha_k,\beta_k\app\bb N$
Alors $\,a\,$ est un diviseur de $\,b\,$ ssi : $\,\ptt k\app\,[\![1,r]\!]\sp{1.5},\ \alpha_k\leq\beta_k\,.\,$
$\displaystyle{}6\,\big|\sp{1.5}(x+1)\sp{1.5}(x+2)\Ssi\Syst{\ 2\,\smh0{\big|}\sp{1.5}(x+1)\sp{1.5}(x+2)\\[-.25ex]3\,\smb0{\big|}\sp{1.5}(x+1)\sp{1.5}(x+2)}$
Il s'agit donc de résoudre le système suivant, formé de deux relations de congruence :
$\displaystyle{}\Syst{\sp{1.5}(x+1)\sp{1.5}(x+2)\equiv0\ [\sp{.75}2\sp{.75}]\\ (x+1)\sp{1.5}(x+2)\equiv0\ [\sp{.75}3\sp{.75}]}$
L'un des deux entiers consécutifs $\,x+1\,$ et $\,x+2\,$ étant nécessairement
Un entier relatif $a$ est pair ssi il est divisible par $2\sp{1.5},$ c'est-à-dire ssi il existe $q\app\bb Z$ tel que $\,a=2\sp{1.5}q\sp{1.5}.\,$
Les entiers non pairs sont les entiers impairs, de la forme : $\,a=2\sp{1.5}q+1\sp{1.5},\,$ pour $\,q\app\bb Z\sp{1.5}.\,$
pair,
la première relation est toujours satisfaite.
D'autre part, le nombre $\,3\,$ étant
Un nombre premier est un entier naturel $\,p\neq1\sp{1.5},\,$ ayant pour seuls diviseurs positifs $\,1\,$ et $\,p\sp{1.5}.\,$
L'ensemble des nombres premiers est un ensemble infini.
premier,
il divise $\,(x+1)(x+2)\,$ si et seulement si il
Un nombre premier $p$ divise un produit d'entiers relatifs $a$ et $b$ ssi il divise l'un d'entre eux :
divise
l'un des facteurs, c'est-à-dire que :
$\displaystyle{}p\op{|}\sp{1.5}(a\sp{1.5}b)\Ssi \big(\sp{1.5}p\sp{-1.5}\op{|}\sp{-1.5}a\,\text{ ou }\,p\sp{-1.5}\op{|}\sp{-1.5}b\sp{1.5}\big)$
$\displaystyle{}(x+1)(x+2)\equiv\ 0\ [\sp{.75}3\sp{.75}]\Ssi\Syst{\ x&\equiv-1\equiv2\ [\sp{.75}3\sp{.75}]\\[-1.5ex]&\!\!\!\!\txt{ou}\\[-1.5ex]
x&\equiv-2\equiv1\ [\sp{.75}3\sp{.75}]}$
L'ensemble des $\,x\app\bb Z\,$ tels que $\,5\,x^2-3\sp{1.5}x+4\,$ soit divisible par $\,6\,$ est alors l'ensemble des entiers congrus à $1$ ou $2$ modulo $\,3\sp{1.5}.\,$
Il s'agit donc de l'ensemble des entiers relatifs non congrus à $\,0\,$ modulo $\,3\sp{1.5},\,$ c'est-à-dire ceux qui ne sont pas multiples de $\,3:\,$
$\displaystyle{}\sc S=\ens{x\app\bb Z}{x\not\equiv0\ [\sp{.75}3\sp{.75}]}=\bb Z\!\setminus\!3\sp{.75}\bb Z$