Soient $r$ et $s$ deux entiers naturels non nuls de sorte que $\pgcd(r,s)=1.$
Vous allez démontrer que, pour tout entier naturel non nul $d’$, si $d’$ divise le produit $rs$ alors il existe deux entiers naturels non nuls $r’$ et $s’$ premiers entre eux, tels que $d’ = r’s’$ avec $r’$ qui divise $r$ et $s’$ qui divise $s.$
Effectuez une récurrence forte
Pour tout entier naturel $d’$ supérieur ou égal à $1$ vous notez $\mathscr{P}(d’)$ la propriété suivante : quels que soient les entiers naturels non nuls $r$ et $s$ premiers entre eux, si $d’$ est un entier naturel non nul qui divise le produit $rs$ alors, il existe deux entiers naturels non nuls $r’$ et $s’$ tels que $r’\mid r\comma$ $s’\mid s\comma$ $\pgcd(r’,s’)=1$ et $d’=r’s’.$
Initialisation
Soient $r$ et $s$ deux entiers naturels non nuls premiers entre eux.
Posez $d’=1$ et supposez que $d’\mid rs.$
Vous posez $r’=1$ et $s’=1.$ Alors $r’\mid r$ et $s’\mid s.$ Vous avez aussi $\pgcd(r’,s’)=1$ et $d’=r’s’.$
La propriété $\mathscr{P}(1)$ est vérifiée.
Hérédité
Soit $d’$ un entier naturel supérieur ou égal à $1.$ Vous supposez que, pour tout $k\in\llbracket 1, d’ \rrbracket$ la propriété $\mathscr{P}(k)$ est vérifiée.
Soient $r$ et $s$ deux entiers naturels non nuls premiers entre eux. Supposez que $d’+1$ divise le produit $rs.$ Comme $d’+1$ est supérieur ou égal à $2$, il existe un nombre premier $p »$ tel que $p »\mid d’+1.$ Il existe un entier naturel non nul $d »$ tel que $\boxed{d’+1=p »d »}.$
Comme $p »\mid d’+1$ et comme $d’+1 \mid rs$ vous avez $p »\mid rs.$ Vous appliquez le lemme d’Euclide, ce qui conduit à deux possibilités.
Premier cas
La première hypothèse est $p » \mid r.$ Il existe un entier naturel non nul $u »$ tel que $\boxed{r = p »u »}.$ L’entier $d’+1$ divise $rs$ cela s’écrit $p »d » \mid p »u »s$ puis $d »\mid u »s.$ Comme $p »\geq 2$ nécessairement $d »< d’+1$ donc $d »\leq d’.$ Donc $d »\in\llbracket 1, d’\rrbracket.$
Or, $\pgcd(u »,s)$ divise $u »$ et divise $s.$ De plus, $u »$ divise $r$ donc $\pgcd(u »,s)$ divise $r$ et $s.$ Vu que $r$ et $s$ sont premiers entre eux, vous déduisez $\pgcd(u »,s)=1.$
Vous appliquez maintenant $\mathscr{P}(d »).$ Il existe deux entiers naturels non nuls $u »’$ et $s »’$ premiers entre eux tels que $\boxed{d »=u »’ s »’}$ avec $u »’\mid u »$ et $s »’\mid s.$
En multipliant par $p »$ vous avez $p » d »=p » u »’ s »’$ soit $d’+1 = (p » u »’) s »’.$ Vous posez $\boxed{r »’ = p » u »’}.$
Comme $u »’ \mid u »$ vous avez aussi $p » u »’ \mid p » u ».$ Cela s’écrit $p » u »’ \mid r$ donc $r »’ \mid r.$
Il reste à démontrer que $\pgcd(r »’, s »’)=1.$ En raisonnant par l’absurde, supposez que $\pgcd(r »’, s »’)\geq 2.$ Il existe un nombre premier $q$ tel que $q\mid \pgcd(r »’, s »’).$ Donc $q$ divise $r »’ = p » u »’.$ Si $q$ divise $u »’$ alors comme $u »’\mid u »$ vous avez $q\mid u ».$ Comme $q$ divise $s »’$ et comme $s »’\mid s$ vous avez $q \mid s$ donc $q$ divise à la fois $u »$ et $s.$ Comme $u »$ et $s$ sont premiers entre eux, cela fournit $q=1$ ce qui est absurde : $q$ en tant que nombre premier est supérieur ou égal à $2.$ Donc $q$ ne peut pas diviser $u »’.$
Comme $q\mid p » u »’$ et comme $q\nmid u »’$ vous avez nécessairement $q \mid p »$ par le lemme d’Euclide. Comme $p »$ est un nombre premier cela aboutit à $q\in\{1, p »\}.$ Or $q$ est un nombre premier donc $q\geq 2$ d’où $q=p ».$ Comme $q\mid \pgcd(r »’, s »’)$ vous déduisez $p » \mid s »’.$ Or $s »’\mid s$ donc $p »\mid s.$ L’hypothèse de départ était $p »\mid r$ donc $p »$ divise $r$ et $s.$ Comme $r$ et $s$ sont premiers entre eux, cela fournit $p »=1.$ Mais $p »$ est un nombre premier donc $p »\geq 2\comma$ ce qui est une contradiction. Vous en déduisez que $\pgcd(r »’, s »’)=1.$
Ainsi, $d’+1 = r »’ s »’$ avec $r »’\mid r\comma$ $s »’\mid s$ et $\pgcd(r »’,s »’)=1\comma$ donc vous avez prouvé que $\mathscr{P}(d’+1)$ est vraie.
Deuxième cas
L’autre hypothèse est $p » \mid s.$ Le premier cas s’applique en échangeant les rôles des entiers $r$ et $s.$ Les détails sont omis pour des questions de longueur.
Fin de la récurrence
Grâce au principe de récurrence forte, vous avez établi que, pour tout entier $d’$ supérieur ou égal à $1$ la propriété $\mathscr{P}(d’)$ est vraie.
Concluez
En reformulant ce qui a été effectué plus haut, vous venez de démontrer que, quel que soit $d\in\NN$ et quel que soit le couple $(r,s)\in(\NN)^2$ vous avez :
Prolongement
Soient $r$ et $s$ deux entiers naturels non nuls premiers entre eux. Notez $D_r$ l’ensemble des diviseurs strictement positifs de $r$, $D_s$ l’ensemble des diviseurs strictement positifs de $s$ et $D_{rs}$ l’ensemble des diviseurs strictement positifs du produit $rs.$
Vous considérez l’application $f$ suivante :
Pourriez-vous justifier que $f$ est bien définie et que c’est une bijection ?