Home

MPSI/PCSI

Maths

Algèbre

PGCD et algorithme d’Euclide

Exercice

Résoudre dans $\mathbb{N}^{2}$ les systèmes : (a) $\left\{\begin{aligned} \operatorname{pgcd}(x, y) & =5 \\ \operatorname{ppcm}(x, y) & =60\end{aligned}\right.$ (b) $\left\{\begin{aligned} x+y & =100 \\ \operatorname{pgcd}(x, y) & =10\end{aligned}\right.$

Résoudre dans $\mathbb{N}^{2}$ l'équation : $$\operatorname{pgcd}(x, y)+\operatorname{ppcm}(x, y)=x+y$$


Soient $d, m \in \mathbb{N}$. 

Donner une condition nécessaire et suffisante pour que le système

$$\left\{\begin{array}{c}\operatorname{pgcd}(x, y)=d \\ \operatorname{ppcm}(x, y)=m\end{array}\right.$$ 

possède un couple $(x, y) \in \mathbb{N}^{2}$ solution.

Montrer que le pgcd de $2 n+4$ et $3 n+3$ ne peut être que $1,2,3$ ou 6 . 

a) 

b) 

c)

Soient $a, b, d \in \mathbb{Z}$. Montrer l'équivalence : $$ (\exists u, v \in \mathbb{Z}, a u+b v=d) \Longleftrightarrow \operatorname{pgcd}(a, b) \mid d $$

On considère la suite $\left(\varphi_{n}\right)_{n \in \mathbb{N}}$ définie par 
$$\varphi_{0}=0, \varphi_{1}=1 \text { et } \forall n \in \mathbb{N}, \varphi_{n+2}=\varphi_{n+1}+\varphi_{n}$$ 
(a) Montrer 
$$\forall n \in \mathbb{N}^{*}, \varphi_{n+1} \varphi_{n-1}-\varphi_{n}^{2}=(-1)^{n}$$ 
(b) En déduire 
$$\forall n \in \mathbb{N}^{*}, \varphi_{n} \wedge \varphi_{n+1}=1$$

Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^{*}$, on note $q$ le quotient de la division euclidienne de $a-1$ par $b$. Déterminer pour tout $n \in \mathbb{N}$, le quotient de la division euclidienne de $\left(a b^{n}-1\right)$ par $b^{n+1}$.

Déterminer le pgcd et les coefficients de l'égalité de Bézout (1730-1783) des entiers $a$ et $b$ suivants : 
(a) $a=33$ et $b=24$ 
(b) $a=37$ et $b=27$ 
(c) $a=270$ et $b=105$.