Sujet A.3.8 Entiers premiers entre eux
Choisir
un exercice, puis le résoudre
:
Signaler une erreur
Signaler une erreur
Exercice a
Montrer que si $\,a\sp{1.5},b\sp{1.5},c\app\bb Z\,$ sont deux à deux premiers entre eux, alors $\,(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\,$ et $\,(a\sp{1.5}b\sp{1.5}c)\,$ sont premiers entre eux.
nombres premiers entre eux
Deux entiers relatifs $a$ et $b$ sont premiers entre eux ssi leur pgcd $\,a\land b\,$ est égal à $1\sp{1.5}.$
En d'autres termes, $\,a\,$ et $\,b\,$ ont $\,1\,$ et $\,-1\,$ pour seuls diviseurs communs.
lemme de Gauss
Dans $\,\bb Z\sp{1.5},\,$ si $\,a\,$ est premier avec $\,b\,$ et si $\,a\,$ divise $\,b\sp{1.5}c\sp{1.5},\,$ alors $\,a\,$ divise $\,c:\,$
$\displaystyle{}\big(a\land b = 1\ \text{ et }\ a\op{|}(b\sp{1.5}c)\big)\Imp a\op{|}c$
nombres premiers entre eux et opérations
Pour des entiers relatifs $a\sp{1.5},$ $b$ et $c\sp{1.5},$ on a les propriétés suivantes :
- $\,\big(a\land c =1\txt{et}b\land c =1\big)\Imp(a\sp{1.5}b)\land c= 1\,;\,$
- $\,\big(a\land b =1\txt{et}a\op{|}c\txt{et}b\op{|}c\big)\Imp (a\sp{1.5}b)\op{|}c\sp{1.5}.\,$
théorème de Bézout
Soient $a$ et $b$ deux entiers relatifs ; alors :
$\displaystyle{}a\land b= 1\Ssi\iex \,(u,v)\app\bb Z^2,\ a\sp{1.5}u+b\sp{1.5}v=1$
indication
En désignant par $\,x\land y\,$ le pgcd de deux entiers $\,x\,$ et $\,y\sp{1.5},\,$ commencer par montrer que :
$\displaystyle{}(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land a=a\land(b\sp{1.5}c)$
réponse
En désignant par $\,x\land y\,$ le pgcd de deux entiers $\,x\,$ et $\,y\sp{1.5},\,$ on démontre bien que :
$\displaystyle{}a\land b=b\land c=c\land a=1\!\Imp\! (a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land (a\sp{1.5}b\sp{1.5}c)=1$
correction
En désignant par $\,x\land y\,$ le
Soient $\,a\sp{1.5},b\app\bb Z\,$ tels que $\,(a,b)\neq(0,0)\,;\,$ leur pgcd est leur plus grand diviseur commun dans $\,\bb N:\,$
pgcd
de deux entiers $\,x\,$ et $\,y\sp{1.5},\,$ on a
par
$\displaystyle{}a\land b=\max\ens{d\app\bb N}{\sp{1.5}d\op{|}a\!\txt{et}\!d\op{|}b\sp{1.5}}$
Pour des entiers relatifs $a\sp{1.5},$ $b$ et $c\sp{1.5},$ on a les propriétés suivantes :
propriété
des nombres
- $\,\big(a\land c =1\txt{et}b\land c =1\big)\Imp(a\sp{1.5}b)\land c= 1\,;\,$
- $\,\big(a\land b =1\txt{et}a\op{|}c\txt{et}b\op{|}c\big)\Imp (a\sp{1.5}b)\op{|}c\sp{1.5}.\,$
Deux entiers relatifs $a$ et $b$ sont premiers entre eux ssi leur pgcd $\,a\land b\,$ est égal à $1\sp{1.5}.$
En d'autres termes, $\,a\,$ et $\,b\,$ ont $\,1\,$ et $\,-1\,$ pour seuls diviseurs communs.
premiers
entre eux :
$\displaystyle{}(\sp{1.5}a\land b=1\txt{et} a\land c=1\sp{1.5})\Imp a\land(b\sp{1.5}c)=1\sp{1.5}$
Selon le
Pour tous $\,a,\sp{.75}b\app\bb Z\,$ et $\,k\app\bb Z\sp{1.5},\,$ on a : $\,a\land b=b\land(a-b\sp{1.5}k)\sp{1.5}.\,$
Le calcul du pgcd par l'algorithme d'Euclide utilise ce principe.
principe
de l'algorithme d'Euclide, il s'ensuit que :
$\eqalign{(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land a&= a\land\big((a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)-a\,(b+c)\big)\\&=a\land(b\sp{1.5}c)=1}$
En procédant de même par permutations circulaires de $a,b$ et $c,$ on a aussi :
$\eqalign{(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land b&= b\land(a\sp{1.5}c)=1\\
(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land c&=c\land(a\sp{1.5}b)=1}$
Le nombre $\,(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\,$ étant premier avec $\,a\sp{1.5},\,$ $\,b\,$ et$\,c\sp{1.5},\,$ on a alors, toujours selon la même
Pour des entiers relatifs $a\sp{1.5},$ $b$ et $c\sp{1.5},$ on a les propriétés suivantes :
propriété :
- $\,\big(a\land c =1\txt{et}b\land c =1\big)\Imp(a\sp{1.5}b)\land c= 1\,;\,$
- $\,\big(a\land b =1\txt{et}a\op{|}c\txt{et}b\op{|}c\big)\Imp (a\sp{1.5}b)\op{|}c\sp{1.5}.\,$
$\eqalign{&(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land (a\sp{1.5}b)&=1\\ \txt{puis :}&(a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land (a\sp{1.5}b\sp{1.5}c)&=1}$
Finalement, on a établi l'implication recherchée, à savoir :
$\displaystyle{}a\land b=b\land c=c\land a=1\Imp (a\sp{1.5}b+b\sp{1.5}c+c\sp{1.5}a)\land (a\sp{1.5}b\sp{1.5}c)=1$
Signaler une erreur
Signaler une erreur
Exercice b
Démontrer que, pour tout $n\app\bb N,$ les entiers $\,A_n=2^n+3^n\,$ et $\,A_{n+1}=2^{n+1}+3^{n+1}\,$ sont premiers entre eux.
En est-il de même pour $\,A_n=2^n+3^n\,$ et $\,A_{n+2}=2^{n+2}+3^{n+2}\,?\,$
nombres premiers entre eux
Deux entiers relatifs $a$ et $b$ sont premiers entre eux ssi leur pgcd $\,a\land b\,$ est égal à $1\sp{1.5}.$
En d'autres termes, $\,a\,$ et $\,b\,$ ont $\,1\,$ et $\,-1\,$ pour seuls diviseurs communs.
lemme de Gauss
Dans $\,\bb Z\sp{1.5},\,$ si $\,a\,$ est premier avec $\,b\,$ et si $\,a\,$ divise $\,b\sp{1.5}c\sp{1.5},\,$ alors $\,a\,$ divise $\,c:\,$
$\displaystyle{}\big(a\land b = 1\ \text{ et }\ a\op{|}(b\sp{1.5}c)\big)\Imp a\op{|}c$
nombres premiers entre eux et opérations
Pour des entiers relatifs $a\sp{1.5},$ $b$ et $c\sp{1.5},$ on a les propriétés suivantes :
- $\,\big(a\land c =1\txt{et}b\land c =1\big)\Imp(a\sp{1.5}b)\land c= 1\,;\,$
- $\,\big(a\land b =1\txt{et}a\op{|}c\txt{et}b\op{|}c\big)\Imp (a\sp{1.5}b)\op{|}c\sp{1.5}.\,$
théorème de Bézout
Soient $a$ et $b$ deux entiers relatifs ; alors :
$\displaystyle{}a\land b= 1\Ssi\iex \,(u,v)\app\bb Z^2,\ a\sp{1.5}u+b\sp{1.5}v=1$
indication
1
Utiliser le principe de l'algorithme d'Euclide.
indication
2
Examiner les premières valeurs du couple $\,(A_n,A_{n+2})=\big(2^n+3^n,\,2^{n+2}+3^{n+2}\big)\sp{1.5}.\,$
réponse
Les entiers $\,A_n=2^n+3^n\,$ et $\,A_{n+1}=2^{n+1}+3^{n+1}\,$ sont bien premiers entre eux, pour tout $n\app\bb N\sp{1.5}.$
En revanche, pour $\,n=1\,$ par exemple, $\,A_n=2^n+3^n\,$ et $\,A_{n+2}=2^{n+2}+3^{n+2}\,$ ne sont pas premiers entre eux.
correction
On désigne par $\,a\land b\,$ le
Soient $\,a\sp{1.5},b\app\bb Z\,$ tels que $\,(a,b)\neq(0,0)\,;\,$ leur pgcd est leur plus grand diviseur commun dans $\,\bb N:\,$
pgcd
de deux entiers $\,a\,$ et $\,b\sp{1.5}.\,$
Avec : $\,A_{n+1}=2^{n+1}+3^{n+1}=2\sp{1.5}\big(2^n+3^n\big)+3^n,\,$
on obtient, selon le
$\displaystyle{}a\land b=\max\ens{d\app\bb N}{\sp{1.5}d\op{|}a\!\txt{et}\!d\op{|}b\sp{1.5}}$
Pour tous $\,a,\sp{.75}b\app\bb Z\,$ et $\,k\app\bb Z\sp{1.5},\,$ on a : $\,a\land b=b\land(a-b\sp{1.5}k)\sp{1.5}.\,$
Le calcul du pgcd par l'algorithme d'Euclide utilise ce principe.
principe
de l'algorithme d'Euclide :
$\eqalign{A_{n+1}\land A_n
&=(2^n+3^n)\land\big((2^{n+1}+3^{n+1})-2\sp{1.5}(2^n+3^n)\big)\\
&=(2^n+3^n)\land 3^n\\
&=3^n\sp{-1.5}\land \big((2^n+3^n)-3^n\big)\\
&=3^n\sp{-1.5}\land \sp{1.5}2^n}$
Selon
Soient $\,p_1,\dots,p_r\,$ des nombres premiers distincts, et $\,a\,$ et $\,b\,$ tels que :
l'expression
d'un pgcd au moyen des
$\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$
- on a alors : $\,a\land b=\smh{0}{p_{1}^{\delta_1}\dots p_{r}^{\delta_r}}\,$ pour $\,\delta_k=\min(\alpha_k,\,\beta_k)\sp{1.5},\,$
- ainsi que : $\,a\lor b=\smh{0}{p_{1}^{\mu_1}\dots p_{r}^{\mu_r}}\,$ pour $\,\mu_k=\max(\alpha_k,\,\beta_k)\sp{1.5}.\,$
Tout entier naturel $\,n\geq2\,$ admet une et une seule décomposition de la forme :
décompositions
en facteurs premiers, on a :
$\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}\!.$
$\displaystyle{}3^n\land 2^n=3^{\min(n,0)}.\sp{1.5}2^{\min(0,n)}=3^0.\sp{1.5}2^0=1$
Finalement, les nombres $\,A_n=2^n+3^n\,$ et $\,A_{n+1}=2^{n+1}+3^{n+1}\,$ sont toujours
Deux entiers relatifs $a$ et $b$ sont premiers entre eux ssi leur pgcd $\,a\land b\,$ est égal à $1\sp{1.5}.$
En d'autres termes, $\,a\,$ et $\,b\,$ ont $\,1\,$ et $\,-1\,$ pour seuls diviseurs communs.
premiers
entre eux.
La suite des $\,A_n=2^n+3^n\,$ a pour premiers termes :
$\eqalign{A_0=2^0+3^0 &=2\\ A_1=2^1+3^1 &= 5\\ A_2=2^2+3^2 &= 13\\ A_3=2^3+3^3&=35=5\times7}$
Ainsi pour $\,n=1\sp{1.5},\,$ on a :
$\,A_1\land A_3=5\land 35=5\neq1\,.\,$
On peut en conclure que $\,A_n=2^n+3^n\,$ et $\,A_{n+2}=2^{n+2}+3^{n+2}\,$ ne sont pas toujours premiers entre eux.
On peut montrer plus précisément que $A_n$ et $A_{n+2}$ sont premiers entre eux si et seulement si $n$ est
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.
Signaler une erreur
Signaler une erreur
Exercice c
\\(\def\x{\!\times\!}\\)Déterminer l'ensemble $\sc S$ des solutions dans $\bb Z^2$ de l'équation :
$\,48\,x+35\,y=1\sp{1.5}.\,$
nombres premiers entre eux
Deux entiers relatifs $a$ et $b$ sont premiers entre eux ssi leur pgcd $\,a\land b\,$ est égal à $1\sp{1.5}.$
En d'autres termes, $\,a\,$ et $\,b\,$ ont $\,1\,$ et $\,-1\,$ pour seuls diviseurs communs.
lemme de Gauss
Dans $\,\bb Z\sp{1.5},\,$ si $\,a\,$ est premier avec $\,b\,$ et si $\,a\,$ divise $\,b\sp{1.5}c\sp{1.5},\,$ alors $\,a\,$ divise $\,c:\,$
$\displaystyle{}\big(a\land b = 1\ \text{ et }\ a\op{|}(b\sp{1.5}c)\big)\Imp a\op{|}c$
nombres premiers entre eux et opérations
Pour des entiers relatifs $a\sp{1.5},$ $b$ et $c\sp{1.5},$ on a les propriétés suivantes :
- $\,\big(a\land c =1\txt{et}b\land c =1\big)\Imp(a\sp{1.5}b)\land c= 1\,;\,$
- $\,\big(a\land b =1\txt{et}a\op{|}c\txt{et}b\op{|}c\big)\Imp (a\sp{1.5}b)\op{|}c\sp{1.5}.\,$
théorème de Bézout
Soient $a$ et $b$ deux entiers relatifs ; alors :
$\displaystyle{}a\land b= 1\Ssi\iex \,(u,v)\app\bb Z^2,\ a\sp{1.5}u+b\sp{1.5}v=1$
indication
1
Déterminer d'abord une solution particulière au moyen de l'algorithme d'Euclide.
indication
2
Utiliser le lemme de Gauss pour établir la forme générale des solutions.
réponse
On obtient pour ensemble des solutions dans $\bb Z^2:$
$\,\sc S=\ens{(-8+35\sp{1.5}q,\,11-48\sp{1.5}q)}{q\app\bb Z}\!\cdot\,$
correction
Selon le théorème de
Soient $a$ et $b$ deux entiers relatifs ; alors :
Bézout,
cette équation a des solutions si et seulement si $48$ et $35$ sont premiers entre eux.
On vérifie que c'est bien le cas en calculant leur
$\displaystyle{}a\land b= 1\Ssi\iex \,(u,v)\app\bb Z^2,\ a\sp{1.5}u+b\sp{1.5}v=1$
Soient $\,p_1,\dots,p_r\,$ des nombres premiers distincts, et $\,a\,$ et $\,b\,$ tels que :
pgcd
à partir de leurs
$\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$
- on a alors : $\,a\land b=\smh{0}{p_{1}^{\delta_1}\dots p_{r}^{\delta_r}}\,$ pour $\,\delta_k=\min(\alpha_k,\,\beta_k)\sp{1.5},\,$
- ainsi que : $\,a\lor b=\smh{0}{p_{1}^{\mu_1}\dots p_{r}^{\mu_r}}\,$ pour $\,\mu_k=\max(\alpha_k,\,\beta_k)\sp{1.5}.\,$
Tout entier naturel $\,n\geq2\,$ admet une et une seule décomposition de la forme :
décompositions
en facteurs premiers :
$\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}\!.$
$\displaystyle{}48\land 35=(2^4\x3)\land(5\x7)=1$
On doit cependant calculer $48\land 35$ par
Pour calculer le pgcd de $\,a\app\bb N\,$ et $\,b\app\bb N^{\ast}\!,\,$ on calcule le reste $\,r\,$ de la division euclidienne de $\,a\,$ par $\,b\sp{1.5}.\,$On répète cette opération en substituant récursivement au couple $(a\sp{1.5},b)$ le couple $(b\sp{1.5},r)\sp{1.5},$ tant que $\,r\neq0\sp{1.5}.\,$
On obtient une suite de couples ayant tous le même pgcd que $(a\sp{1.5},b)\sp{1.5},$ égal enfin au dernier reste $r_n$ non nul :
l'algorithme
d'Euclide afin d'obtenir une solution particulière de l'équation :
$\eqalign{(a\sp{1.5},\sp{1.5}b)&\ot&(b\sp{1.5},\sp{1.5}r)&\ot&\cdots&\ot&(r_n\sp{1.5},\sp{1.5}0)\\[-.5ex] a\land b&\,\sp{1.5}=&\,b\land r&\,\sp{1.5}=&\cdots &\,\sp{1.5}=&\,r_n\land 0&=&r_n}$
$\eqalign{ 48&=1\x35+13&\Imp&48\land35&=35\land13\\
35&=2\x13+9&\Imp&35\land13&=13\land9\\
13&=1\x9+4&\Imp&13\land9&=\ \ 9\land4\\
9&=2\x4+1&\Imp&\ \ 9\land4&=\ \ 4\land1\ =\ 1}$
On obtient bien $\,48\land35=1\sp{1.5},\,$ et on reprend à partir de la fin les restes de chaque
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 :
$\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}.$
$\eqalign{ 1&=\ph{-}1\x\,9\,-\,2\x4\\
&=\ph{-}1\x\,9\,-\,2\x(13-1\x9)&=-2\x13+3\x9\\
&=-2\x13+3\x(35-2\x13)&=\ph{-}3\x35-8\x13\\
&=\ph{-}3\x35-8\x(48-1\x35)&=-8\x48+11\x35}$
On en déduit une solution particulière $\,(x_0,y_0)=(-8,11)\,$ de l'équation $\,48\,x+35\,y=1\sp{1.5}.\,$
On peut aussi utiliser l'algorithme d'Euclide étendu, consistant à calculer simultanément le pgcd et le couple $(x_0,y_0)\sp{1.5}.$ Toutefois ce procédé, important pour la programmation sur machine, nous fait perdre de vue la justification des calculs.
L'équation peut maintenant s'écrire :
$\eqalign{ &48\,x+35\,y=48\,x_0+35\,y_0\\ \Ssi&48\sp{1.5}(x-x_0)=-35\sp{1.5}(y-y_0)}$
- Si on connaît le lemme de
Dans $\,\bb Z\sp{1.5},\,$ si $\,a\,$ est premier avec $\,b\,$ et si $\,a\,$ divise $\,b\sp{1.5}c\sp{1.5},\,$ alors $\,a\,$ divise $\,c:\,$Gauss, on a obtient : $\,35\op{\big|}(x-x_0)\sp{1.5},\,$ d'où l'existence de $q\app\bb Z$ tel que : $\,x=x_0+35\sp{1.5}q\,;\,$$\displaystyle{}\big(a\land b = 1\ \text{ et }\ a\op{|}(b\sp{1.5}c)\big)\Imp a\op{|}c$
- sinon on remarque que $5$ et $7,$ qui sont les facteurs premiers de $35\sp{1.5},$ ne figurent pas dans la décomposition de $48\sp{1.5}.$ Ils figurent donc nécessairement dans celle de $(x-x_0)\sp{1.5},$ d'où l'existence de $q\app\bb Z$ tel que : $\,x=x_0+35\sp{1.5}q\sp{1.5}.\,$
$\displaystyle{}\sc S=\ens{(-8+35\sp{1.5}q\sp{1.5},\,11-48\sp{1.5}q)}{q\app\bb Z}$