icone-challenge-math-OS

Solution pour le challenge 79

On peut décomposer tout entier n\geqslant2 en produit de facteurs premiers :

    \[n=\prod_{i=1}^{r}p_{i}^{\alpha_{i}}\]

avec p_{1},\cdots,p_{r} premiers distincts et \alpha_{1},\cdots,\alpha_{r}\in\mathbb{N}^{\star}. Le nombre de diviseurs de n est :

    \[\tau\left(n\right)=\prod_{i=1}^{r}\left(1+\alpha_{i}\right)\]

Comme 61 est un nombre premier, la condition \tau\left(n\right)=61 impose r=1 et \alpha_{1}=60. Ainsi n est nécessairement de la forme :

    \[n=p^{60}\]

avec p premier. Dès lors, la plus petite solution est obtenue pour p=2. En conclusion, le plus petit entier positif possédant 61 diviseurs est :

    \[2^{60}=1\thinspace152\thinspace921\thinspace504\thinspace606\thinspace846\thinspace976\]

Plus généralement, si q est premier, alors le plus petit entier positif possédant q diviseurs est 2^{q-1}. On peut encore généraliser …

Notons désormais \pi_{i} le i-ème nombre premier (de sorte que \pi_{1}=2, \pi_{2}=3, \pi_{3}=5, etc …). Soient q_{1},\cdots,q_{s} des nombres premiers distincts et soit q leur produit (par exemple : q=30=2\times3\times5). Si n\geqslant2 vérifie \tau\left(n\right)=q, c’est-à-dire :

    \[\prod_{i=1}^{r}\left(1+\alpha_{i}\right)=\prod_{i=1}^{s}q_{i}\]

nécessairement r=s et les entiers 1+\alpha_{i} (pour 1\leqslant i\leqslant s) sont exactement les q_{i}, à l’ordre près, en raison de l’unicité de la décomposition en produit de facteurs premiers. Notre entier n est donc de la forme :

(\star)   \[n=\prod_{i=1}^{s}p_{i}^{q_{i}-1}\]

Supposons désormais que q_{1}>q_{2}>\cdots>q_{s} (on peut toujours supposer cela, quitte à renuméroter). Le produit figurant au second membre de \left(\star\right) est minimal lorsque p_{i}=\pi_{i} pour tout i\in\left\llbracket 1,s\right\rrbracket . Ainsi, par exemple, le plus petit entier positif possédant 30 diviseurs est :

    \[n=2^{5-1}\times3^{3-1}\times5^{2-1}=720\]

Pour consulter l’énoncé, c’est ici

Partager cet article
    

Laisser un commentaire