Bonsoir,
- mathman a écrit:
- Maintenant prouve qu'il n'y a pas d'autres solutions.
Je crois que j'y suis.
L'idée de la très laborieuse démonstration ci-dessous est de montrer que si l'ensemble cherché contient un nombre comportant un facteur premier > 3, ce nombre est divisible par 2 autant de fois que l'on veut, ce qui revient à dire qu'il n'en existe pas.
J'ai eu beaucoup de mal à être très rigoureux.
Je suis intéressé par toute démonstration plus simple.
Allons-y :
Soit A = l'ensemble des nombres cherchés.
Notation : phi^[k](x) représente l'application de phi k fois de suite à x.
Pour x dans N*, soit P2(x) l'exposant de 2 dans la décomposition en facteurs premiers de x.
Propriété P1 (rappel) : si x et y sont premiers entre eux phi(xy) = phi(x)phi(y)
Propriété P2 (Rappel) : Si x = prod_{i=1,n}p_i^k_i, avec p_i premiers et k_i > 0, alors phi(x) = prod_{i=1,n}(p_i - 1)p_i^(k_i - 1)
Propriété P3 (directement à partir de P2) : phi(2^m*3^n) = 2^m * 3^(n-1) avec m et n dans N*
Propriété P4 : si x possède au moins deux diviseurs premiers différents >= 3, p2(phi(x)) > p2(x)
Simple : x = 2^a p^b q^c y avec y premier avec p et q
Si a = 0 phi(x) = (p-1) p^(b-1) (q-1) q^(c-1) phi(y). Comme p-1 et q-1 sont pairs, on a le résultat.
Si a > 0 phi(x) = 2^(a-1) (p-1) p^(b-1) (q-1) q^(c-1) phi(y). Comme p-1 et q-1 sont pairs, on a le résultat.
propriété P5 : si x ne possède pas de diviseurs premiers > 3, alors phi(x) non plus
Evident d'après P2 et P3
Propriété P6 : Si x possède un diviseur premier > 3, alors p2(phi(x)) >= p2(x)
Simple : x = 2^a p^b y avec y premier avec p
Si a = 0 phi(x) = (p-1) p^(b-1) phi(y). Comme p-1 est pair, on a le résultat.
Si a > 0 phi(x) = 2^(a-1) (p-1) p^(b-1) phi(y). Comme p-1 est pair, on a le résultat.
Propriété P7 : Soient x, k>1 dans N* tels que phi^[k](x) possède un facteur premier > 3, alors p2(phi^[k](x)) >= p2(x) et l'égalité ne peut être obtenue que si la suite p_i = phi^[i](x)/2^p2(phi^[i](x)) n'est composée que de nombres premiers impairs pour i = 0 à k-2 et si p_(k-1) est une puissance d'un nombre premier impair. Accessoirement p_i = 2*p_(i+1) + 1.
C'est la propriété importante (avec P8) de la démonstration.
La première partie (p2(phi^[k](x)) >= p2(x)) découle directement de P6 et de la contraposée de P5.
La deuxième partie (conditions pour l'égalité) est plus complexe. Elle se démontre assez facilement par récurrence.
Démarrage : k = 2
D'après la contraposée de P5, x possède un diviseur premier > 3.
D'après P4, il n'en possède qu'un
Il est donc de la forme x = 2^a 3^b p^c
Si a = 0 et comme p-1 est pair, on aurait p2(phi(x)) > p2(x) ==> a > 0
Si b > 0 et comme p-1 est pair, on aurait p2(phi(x)) > p2(x) ==> b = 0
on a donc x = 2^a p^c, et donc phi(x) = 2^a ((p-1)/2) p^(c-1)
(p-1)/2 est > 1. S'il est pair, p2(phi(x)) > p2(x) ==> (p-1)/2 est impair.
Donc (p-1)/2 contient au moins un facteur premier >=3 et différent de p. Si c > 1, la proprété P4 permet donc de dire que p2(phi(phi(x))) > p2(phi(x)).
Donc c = 1 et on a x = 2^a p avec p premier.
Donc p_0 = p_i = x/2^p2(x) est bien un nombre premier impair.
On a alors phi(x) = 2^a ((p-1)/2) p^n
Phi(x) comporte un facteur premier > 3 (contraposée de P5)
Phi(x) ne comporte qu'un seul facteur premier >= 3 (d'après P4)
Donc phi(x) = 2^a q^m et on a bien p1 = q^m
CQFD
Récurrence : Soit k > 2 et la propriété vraie pour toutes valeurs de 2 à k-1.
L'application de la propiété à x et à k-1 permet de dire que la suite p_i = phi^[i](x)/2^p2(phi^[i](x)) n'est composée que de nombres premiers impairs pour i = 0 à k-3.
L'application du même raisonnement que pour le démarrage de la récurrence permet de dire que p_(k-2) est premier impair et p_(k-1) puissance d'un nombre premier impair > 3, ce qui boucle la récurrence.
Le fait que p_i = 2*p(i+1) + 1 découle directement de ce que :
phi^[i](x) = 2^a p_i
phi^[i+1](x) = 2^a (p_i - 1)/2 = 2^a p_(i+1)
Propriété P8 : Soit p premier > 3 , la suite u_0 = p, u_(n+1)= 2*u_n + 1 comprend au moins un nombre non premier dans {u0, u1, ... u_(p-1)}
Simple : u_(p-1) = 2^(p-1) p + 2^(p-1) - 1 = 0 [p]
Propriété P9 : Soit y dans A possédant un facteur premier > 3. Alors, il existe k tel que pour tout x vérifiant phi^[k](x) = y, p2(y) > p2(x).
Supposons k tel que p2(y) = p2(x). d'après P7 :
phi^[k-2](x) = 2^a p_(k-2)
phi^[k-1](x) = 2^a (p_(k-2) - 1)/2 = 2^a p_(k-1) = 2^a q^n
phi^[k] (x) = 2^a (q-1) q^(n-1)
==> phi^[k](x) > 2^a (q-1)^n
==> (q-1)^n < phi^[k](x)/ 2^a
==> q <= phi^[k](x)/ 2^a
Mais phi^[k] (x) = 2^a (q-1) q^(n-1) et q > 3 ==> n <= 1 + log3(phi^[k] (x)/2^(a+1))
Donc q^n <= (phi^[k](x)/ 2^a)^(1 + log3(phi^[k] (x)/2^(a+1)))
Donc p_(k-2) <= 2*(phi^[k](x)/ 2^a)^(1 + log3(phi^[k] (x)/2^(a+1))) + 1
La série P0, P1, ..., p_(k-2) n'est composée que de nombres premiers et p_i = 2*p_(i+1) + 1.
Donc d'après P8, k-2 < p_(k-2)
Donc k < 2 + 2*(phi^[k](x)/ 2^a)^(1 + log3(phi^[k] (x)/2^(a+1))) + 1
En conséquence, pour tout k supérieur à la valeur ci-dessus, p2(y) > p2(x)
CQFD
Démonstration du résultat final :
La propriété P9 montre que si y dans A possède un facteur premier > 3, on peut, en appliquant autant que fois que nécessaire P9, démontrer que p2(y) est aussi grand que l'on veut, ce qui est évidemment impossible.
Donc il n'existe pas dans A de nombres possédant des facteurs premiers > 3.
Il est quasi immédiat d'en déduire A = {1} U {2^m 3^n avec m et n dans N*}
Ouff !
--
Patrick
Accueil 
)