PGCD et PPCM

Exercice 3106. On appelle nombre parfait tout entier naturel $n$ dont la somme des diviseurs vaut $2n$ ou de manière équivalente tout entier naturel $n$ dont la somme des diviseurs stricts vaut $n$.\\
  1. Pour $n \in \N^*$, on note $S(n)$ la somme des diviseurs de $n$. Montrer que la fonction $S$ est multiplicative, c'est-à-dire que si $m$ et $n$ sont premiers entre eux, alors \[ S(mn)=S(m)S(n) \]
  2. Soit $p \in \N$ tel que $2^p-1$ soit premier. \\
    1. Montrer que $p$ est premier. \\
    2. Montrer que \[ n=2^{p-1}(2^p-1) \] est parfait. \\
  3. Montrer que tout nombre parfait pair est de la forme \[ 2^{p-1}(2^p-1) \] où $p$ est premier.
Exercice 3107. Résoudre l’équation \[ x\wedge y+x\vee y=y+9, \] d’inconnues entières $x$ et $y$.
Exercice 3108. Déterminer le pgcd et des coefficients de Bézout des entiers $a$ et $b$ suivants.\\
  1. $a=33$ et $b=24$\\
  2. $a=37$ et $b=27$\\
  3. $a=270$ et $b=105$
Exercice 3109. Soient $a,b,d \in \mathbb{Z}$.\\ Montrer l'équivalence \[ (\exists u,v \in \mathbb{Z}, au+bv=d) \iff \mathrm{pgcd}(a,b) \mid d \]
Exercice 3110. Montrer que le pgcd de $2n+4$ et $3n+3$ ne peut être que $1$, $2$, $3$ ou $6$.
Exercice 3111. \\
  1. Montrer que si $r$ est le reste de la division euclidienne de $a \in \mathbb{N}$ par $b \in \mathbb{N}^*$, alors $2^r-1$ est le reste de la division euclidienne de $2^a-1$ par $2^b-1$.\\
  2. Montrer que \[ \mathrm{pgcd}(2^a-1,2^b-1)=2^{\mathrm{pgcd}(a,b)}-1 \]
Exercice 3112. Résoudre dans $\mathbb{N}^2$ l'équation \[ \mathrm{pgcd}(x,y)+\mathrm{ppcm}(x,y)=x+y \]
Exercice 3113. Résoudre dans $\mathbb{N}^2$ les systèmes suivants.\\
  1. \[ \left\{ \begin{array}{l} \mathrm{pgcd}(x,y)=5\\ \mathrm{ppcm}(x,y)=60 \end{array} \right. \]
  2. \[ \left\{ \begin{array}{l} x+y=100\\ \mathrm{pgcd}(x,y)=10 \end{array} \right. \]
Exercice 3114. On divise un cercle en $n$ arcs égaux et on joint les points de division de $p$ en $p$ jusqu'à ce qu'on revienne au point de départ.\\ Quel est le nombre de côtés du polygone construit ?
Exercice 3115. On considère la suite $(\phi_n)_{n\in\mathbb{N}}$ définie par \[ \phi_0=0,\quad \phi_1=1 \quad \text{et} \quad \forall n \in \mathbb{N},\ \phi_{n+2}=\phi_{n+1}+\phi_n \]
  1. Montrer \[ \forall n \in \mathbb{N}^*,\ \phi_{n+1}\phi_{n-1}-\phi_n^2=(-1)^n \]
  2. En déduire \[ \forall n \in \mathbb{N}^*,\ \phi_n \wedge \phi_{n+1}=1 \]
  3. Montrer \[ \forall n \in \mathbb{N},\ \forall m \in \mathbb{N}^*,\ \phi_{n+m}=\phi_m\phi_{n+1}+\phi_{m-1}\phi_n \]
  4. En déduire \[ \forall m,n \in \mathbb{N}^*,\ \mathrm{pgcd}(\phi_n,\phi_{m+n})=\mathrm{pgcd}(\phi_n,\phi_m) \] puis \[ \mathrm{pgcd}(\phi_m,\phi_n)=\mathrm{pgcd}(\phi_n,\phi_r) \] où $r$ est le reste de la division euclidienne de $m$ par $n$.\\
  5. Conclure \[ \mathrm{pgcd}(\phi_m,\phi_n)=\phi_{\mathrm{pgcd}(m,n)} \]
Exercice 3116. Soit $n \in \mathbb{N}^*$. \\
  1. Montrer que tout entier de $\llbracket 1,n \rrbracket$ admet un multiple dans $\llbracket n+1,2n \rrbracket$. \\
  2. En déduire que $1 \vee 2 \vee \cdots \vee (2n) = (n+1) \vee (n+2) \vee \cdots \vee (2n)$.
Exercice 3117. Soit $n$ et $m$ dans $\N^*$, montrer que $\gcd(5^n-1,5^m-1)=5^{\gcd(n,m)}-1$.
Exercice 3118.
  1. Soit $(a,b)\in(\mathbb{N}^*)^2$ fixé, résoudre dans $(\mathbb{N}^*)^2$ le système d’équations : \[ \left\{ \begin{array}{l} x\wedge y=a\\ x\vee y=b \end{array} \right. \]
  2. Exemples : Résoudre $(S)$ dans chacun des deux exemples suivants :\\
    • $a=10$, $b=22$ \\
    • $a=8$, $b=80$.
Exercice 3119. Résoudre dans $(\mathbb{N}^*)^2$ : $11(x\wedge y)+(x\vee y)=203$.
Exercice 3120. Déterminer tous les $(a,b)\in\N^2$ tels que : $m+11\delta=203$, avec $m=a\vee b$ et $\delta=a\wedge b$.
Exercice 3121. On s'intéresse au système suivant dans $\mathbb{Z}$ : \\ \[ (1)\;\;\left\{ \begin{array}{l} x \equiv 1 \; [3] \\ x \equiv 5 \; [11] \end{array} \right. \]
  1. Trouver une relation de Bézout entre les entiers $3$ et $11$. \\
  2. En déduire une solution particulière du système $(1)$. \\
  3. Trouver toutes les solutions de $(1)$.
Exercice 3122. On considère une application $f : \mathbb{N}^* \times \mathbb{N}^* \to \mathbb{N}^*$ vérifiant pour tout $m,n \in \mathbb{N}^*$ : \\
  • $f(m,n) = f(n,m)$, \\
  • $f(m,m) = m$, \\
  • $f(m+n,n) = f(m,n)$. \\
Déterminer $f$.
Exercice 3123. Montrer que deux $\mathrm{PGCD}$ (resp. $\mathrm{PPCM}$) de $a_1,\ldots,a_n$ sont associés.
Exercice 3124. Soient $a,b \in \N^*$.\\ Déterminer les paires $\{a,b\}$ telles que $a \wedge b = 10$ et $a \vee b = 360$.
Exercice 3125. Obtenir une relation de Bézout entre $412$ et $39$.
Exercice 3126. Obtenir une relation de Bézout entre $100$ et $27$.
Exercice 3127. Obtenir une relation de Bézout entre $1031$ et $417$.
Exercice 3128. \\
  1. Calculer $d = 420 \wedge 198$.\\
  2. Déterminer $u,v \in \Z$ tels que $420u + 198v = d$.
Exercice 3129. Résoudre l'équation $54x + 128y = 6$.
Exercice 3130. Montrer que pour tout $n \in \N^*$, $n \wedge (2n+1)=1$ et $(n+1) \wedge (2n^2+n)=1$.\\ Que pensez-vous de : $(n+1) \wedge (n^2-n)=1$ ?
Exercice 3131. Soit $n \in \N^*$.\\
    1. Montrer que tout entier de $\llbracket 1,n \rrbracket$ admet un multiple dans $\llbracket n+1,2n \rrbracket$.\\
    2. En déduire que $1 \vee 2 \vee \cdots \vee (2n) = (n+1) \vee (n+2) \vee \cdots \vee (2n)$.
Exercice 3132. \\
  1. Soit $d$ et $n$ dans $\N^*$, montrer que le nombre de multiple de $d$ dans $\llbracket 1,n \rrbracket$ est égal à $\left\lfloor \Frac{n}{d}\right\rfloor$.\\
  2. Montrer que pour tout nombre premier $p$, $\nu_p(n!)=\Sum_{k\geqslant 1}\left\lfloor \Frac{n}{p^k}\right\rfloor$.\\
  3. Trouver la puissance de $2$ dans le décomposition en facteurs premiers de $1000!$\\
  4. Montrer que l'écriture décimale de $1000!$ se termine par $249$ zéros.
Exercice 3133. Soit $a \in \N^* \setminus \{1\}$ et $b \in \N^* \setminus \{1\}$ tels que $a \wedge b = 1$. Prouver qu’il existe toujours un couple $(u,v) \in \Z^2$ tel que $au + bv = 1$ avec la contrainte $|u| < b$ et $|v| < a$. Peut-il en exister plusieurs ?
Exercice 3134. Déterminer tous les $(a,b) \in \mathbb{N}^2$ tels que $m + 11\delta = 203$ avec $m = a \vee b$ et $\delta = a \wedge b$.
Exercice 3135. Soit $n$ et $m$ dans $\N^*$, montrer que le $\mathrm{pgcd}$ de $5^n-1$ et de $5^m-1$ est égal à $5^{n\wedge m}-1$.
Exercice 3136. Soit $P$ une partie de $\mathbb{N}$ stable par addition. Montrer qu'il existe $(n,k) \in \mathbb{N}^2$ tel que \[ P \cap [n,+\infty[=k\mathbb{N}\cap [n,+\infty[. \]
Exercice 3137. Soient $a,m,n \in \N^*$, avec $a \geqslant 2$ et $d=(a^n-1) \wedge (a^m-1)$.\\
  1. Soit $n=qm+r$ la division euclidienne de $n$ par $m$. Démontrer que $a^n$ est congru à $a^r$ modulo $a^m-1$.
  2. En déduire que $d=(a^r-1) \wedge (a^m-1)$, puis que $d=a^{n \wedge m}-1$.
  3. A quelle condition $a^m-1$ divise-t-il $a^n-1$ ?
Exercice 3138. Nombres de Leonard de Pise dit Fibonacci fils de Bonacci.\\ On considère la suite $(F_n)$ définie par ses premiers termes $F_0=0$ et $F_1=1$ et par la relation de récurrence \[ F_{n+2}=F_n+F_{n+1} \] pour tout $n \in \N$.\\
  1. Montrer que pour tout entier $n \in \N^*$, \[ F_{n-1}F_{n+1}-F_n^2 = (-1)^n \] Déduisez-en que $F_n$ et $F_{n+1}$ sont premiers entre eux.
  2. Montrer que pour tout couple $(n,p) \in \N \times \N^*$, \[ F_{n+p}=F_pF_{n+1}+F_{p-1}F_n \] En déduire que \[ F_n \wedge F_p = F_{n+p} \wedge F_p \]
  3. Démontrer que pour tout $(m,n) \in (\N^*)^2$, \[ F_m \wedge F_n = F_{m \wedge n} \]
Exercice 3139. Soit $A$ une partie de $\N$ contenant $0$, non réduite à $\{0\}$ et stable par somme. On note \[ d=\mathrm{pgcd}(A), \] le plus grand diviseur commun à tous les éléments de $A$ dans $\N^*$.\\
  1. Justifier l'existence de $d$.\\
  2. Montrer que \[ \{x-y,\; (x,y)\in A^2\}=d\Z. \]
  3. On suppose que \[ d=1. \] Montrer que \[ \N \setminus A \] est fini.\\
  4. Soient \[ a,b \] deux entiers naturels premiers entre eux. Quel est le plus grand entier naturel n'appartenant pas à \[ a\N+b\N \; ? \]