Diviseurs d'un entier décomposé : énoncé (Maths expertes)
Diviseurs d'un entier décomposé
Si $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, les diviseurs positifs de $n$ sont les entiers $p_1^{\beta_1} \cdots p_k^{\beta_k}$ avec $0 \leqslant \beta_i \leqslant \alpha_i$ pour tout $i$.
Le nombre de diviseurs positifs de $n$ est donc $(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$.
Le PGCD de deux entiers s'obtient en prenant les facteurs premiers communs, chacun avec le plus petit des deux exposants.
Décomposition de 360 et de 84
$360 = 2 \times 180 = 2^2 \times 90 = 2^3 \times 45 = 2^3 \times 3^2 \times 5$.
Nombre de diviseurs positifs de $360$ : $(3+1)(2+1)(1+1) = 24$.
$84 = 2^2 \times 3 \times 7$. Facteurs communs : $2$ (exposants $3$ et $2$) et $3$ (exposants $2$ et $1$). Donc $\mathrm{PGCD}(360, 84) = 2^2 \times 3 = 12$. Vérification : $360 = 12 \times 30$ et $84 = 12 \times 7$, avec $30$ et $7$ premiers entre eux.
Crible d'Ératosthène
Pour lister les nombres premiers jusqu'à $N$, on écrit les entiers de $2$ à $N$, puis on barre les multiples stricts de $2$, de $3$, de $5$, etc. Il suffit de le faire pour les nombres premiers $p \leqslant \sqrt{N}$. Les entiers non barrés sont les nombres premiers.
S’entraîner
- Divisions euclidiennes et restes
- Primalité et décomposition en facteurs premiers
- Entiers n tels que n + 1 divise n² + 5
- Une divisibilité pour tout entier naturel
- Carrés modulo 8 et sommes de trois carrés