Nombres premiers

Si un nombre entier \(a\) admet comme décomposition en facteurs premiers \(a=\prod_{i=1} ^n p_i ^{\alpha i},\) alors tout diviseur \(c\) de \(a\) admet une décomposition en facteurs premiers \(c=\Pi_{i=1} ^n p_i ^{\alpha' i},\) avec \(\forall \quad i \quad 0 \leq \alpha'_i \leq\alpha_i\)

Si un nombre entier \(m\) est un multiple de \(a\) et si \(a\) admet comme décomposition en facteurs premiers \(a=\Pi_{i=1} ^n p_i ^{\alpha i},\) alors tous les facteurs premiers \(p_i\) figurent dans la décomposition en facteurs premiers de \(m,\) avec un exposant au moins égal à celui qu'ils ont dans la décomposition de \(a.\)

On considère deux nombres \(a\) et \(b\) dont on connaît les décompositions en facteurs premiers. On va déterminer la décomposition du pgcd et celle du ppcm, connaissant les décompositions des deux nombres.

Pour cela, on va modifier l'écriture de la décomposition des deux nombres. En rajoutant formellement éventuellement des exposants nuls, on peut écrire ainsi ces deux décompositions :

\(a=\Pi_{i=1}^{n} p_i ^{\alpha i}\)

et

\(b=\Pi_{i=1} ^n p_i ^{\beta i},\)

avec les mêmes facteurs premiers. Si par exemple, un facteur \(p_j\) ne figure pas dans la décomposition de \(a,\) mais figure dans celle de \(b,\) on le fait apparaître avec un exposant nul dans la décomposition de \(a.\)

Tout diviseur commun \(c\) de \(a\) et \(b\) admet une décomposition en facteurs premiers :

\(c=\Pi_{i=1} ^n p_i ^{\alpha' i},\),

avec \(\forall \quad i \quad 0 \leq \alpha'_i \leq \textrm {min} (\alpha _i, \beta_i).\) Donc le pgcd a pour décomposition

\(\textrm {pgcd} (a,b)=\displaystyle {\prod_{i=1}^{i=n}} p_i ^{\textrm{min}(\alpha_i,\beta_i)}\)

Tout multiple commun \(c\) de \(a\) et \(b\) admet une décomposition en facteurs premiers où figurent tous les facteurs premiers \(p_i\) avec un exposant au moins égal à \(\textrm {max} (\alpha_i, \beta_i),\) (et peut-être d'autres facteurs.) Donc le ppcm a pour décomposition

\(\textrm {ppcm} (a,b)=\Pi_{i=1}^n p_i ^{\textrm{max}(\alpha_i,\beta_i)}\)