Diviseurs [2] - solution
Définissons φ(n) le nombre de nombres ≤ n et premiers avec n
(c'est à dire
PGCD(x, n) = 1)
Soit γ(n) le plus grand diviseur de n sans facteur carré.
si n = ∏pa est la décomposition en facteurs premiers de n, on a :
γ(n) = ∏p
φ(n) = n ∏(p-1) / ∏p
φ(n) = γ(n)
Soit n × ∏(p-1) / ∏p = ∏p
ou
n × ∏(p-1) = ∏p²
Tout diviseur premier de p-1 est donc un des (autres) facteurs premiers de n.
Si p = 2, p - 1 = 1, si p > 2, p - 1 est pair.
Il ne peut donc pas y avoir plus de un seul facteur premier p > 2, et 2,
sinon l'exposant de 2 du second membre
serait > 2.
Les seuls facteurs premiers de p - 1 sont alors 2, la seule possibilité est
p = 3, si p > 2 il y a.
Et les seules solutions : 1, 4, 18
φ(n) = γ(n)²
On a de même
n × ∏(p-1) = ∏p³
Il y a au plus 2 facteurs premiers p et q > 2.
De plus le produit des facteurs 2 de p - 1 et q - 1 ne peut dépasser 4.
Donc p - 1 = 2, 4, 2q, ou 2q² et de même pour q - 1, soit :
p-1 | q-1 | |
- | - | n = 1 ou n = 2³ |
2 | - | p = 3, n = 2²×3³ |
4 | - | p = 5, n = 2×5³ |
2 | 2p | p = 3, q = 7, n = 2×3²×7³ |
2 | 2p² | p = 3, q = 19, n = 2×3×19³ |
2q | 2p² | p - 1 = 2(2p² + 1) > p impossible |
Et les seules solutions : 1, 8, 108, 250, 6174, 41154
Etc...
On peut montrer de même qu'il y a un nombre fini de solutions à
φ(n) = γ(n)k,
et les calculer.