Dénombrement d'infinis

[nodjim]

Bonsoir à tous.
Une question pas bien méchante.
Soit E(F) l'ensemble des nombres de Fermat (nombres de la forme 2^(2^k)+1) et E(p) l'ensemble des nombres premiers qui divisent les nombres de Fermat.
Quel est, de ces 2 ensembles, celui qui contient le plus d'éléments ? On comptera dans les 2 ensembles les nombres de Fermat premiers.

[miikou]

salut,

On a bien trivialement E(p) > E(f)

[nodjim]

C'est sûrement trivial, un minimum de justification ne sera pas nuisible.
Comme qui dirait, cela va dire, mais c'est mieux en le disant.

[miikou]

salut,

On associe 2^2^k +1 ces diviseurs premiers

On constate simplement que 2^2^a+1 et 2^2^b+1 non pas de diviseurs premiers commun.

Supposons a different b et p diviseur de 2^2^a+1 et 2^2^b+1
alors p divise la difference
p divise 2^2^a- 2^2^b , donc p = 2
or p ne divise ni 2^2^a+1 ni 2^2^b+1

Ce qui conclus, sauf erreur ..

[nodjim]

Vrai. La question initiale que je voulais poser au départ est celle ci:
Prouver qu'un diviseur d'un nombre de Fermat est diviseur d'une infinité de nombres de Mersenne (nombre de la forme 2^n-1)

[Doraki]

Supposons a different b et p diviseur de 2^2^a+1 et 2^2^b+1
alors p divise la difference
p divise 2^2^a- 2^2^b , donc p = 2

pourquoi "donc p=2" ? 2^2^a - 2^2^b n'est pas une puissance de 2.

[nodjim]

pourquoi "donc p=2" ? 2^2^a - 2^2^b n'est pas une puissance de 2.

J'ai vu l'erreur, mais le raisonnement reste bon, p pair.

[miikou]

salut a vous deux et merci doraki ;)

Utilisons le lemme :

si p est un diviseur premier de 2^2^a-1 alors p=k*a+1


dans ce cas on considere un diviseur premier commun a 2^2^a-1 et 2^2^b-1

en particulier on a : ka+1=hb+1 => ka=hb donc a|hb => hb=ia
donc p=ka+1 et p = ia+1 donc ka=ia => k=i

CONCLUSIOn : p est unique, de plus on sait que 3 divise tjs 2^2^n-1
deplus 2^2^n-1 nest jms une puissance de trois, ce qui conclus !

[Doraki]

si p est un diviseur premier de 2^2^a-1 alors p=k*a+1

J'aimerais une preuve de ça quand a = 3.
(que ce soit 2^2^a-1 ou 2^2^a+1)

[miikou]

ormis 3 c'est ca que tu veux me faire comprendre ?

[Doraki]

Non j'ai regardé si c'était vrai pour p=3 (ça l'était pas), et j'ai pas cherché plus loin (c'est faux pour tout p>=3 si tu veux savoir)

[nodjim]

Oui, ça ne marche pas bien sa démo..

[miikou]

heu confirmer a l'aide de matlab

si tu prend 2^2^n-1 alors un diviseur premier different de 3 est de la dorme kn+1 ...

[Doraki]

Oui par exemple, 5 et 17, qui sont diviseurs de 2^2^3-1 = 255, sont congrus à 1 modulo 3.

[miikou]

OULA jme suis planté lamentablement :mur: dsl de vous avoir fait perdre votre temps a tout les deux ..

[miikou]

je reviens a la charge j'avais lu de travers l'énoncé !

solution finale ( et exacte ! )

on prend p un diviseur premier de 2^2^n+1
d'apres fermat p=k*2^(n+1) + 1

en particulier un diviseur commun a 2^2^a+1 et 2^2^b+1 verifie :

p=k*2^(a+1) +1 = h*2^(b+1)+1 on prend a
=> k=h*2^(b-a)

2^2^a+1 et 2^2^b+1 sont premier entre eux !

ce qui conclus :we:

[Doraki]

comment tu appliques le petit théorème de Fermat pour trouver que p = 1 mod 2^(n+1) ??

En quoi est-ce que k = h*2^(b-a) serait une contradiction ?

Bon pour t'éviter d'écrire encore n'importe quoi :
Si a = 2kb, alors
(2^b+1)*(2^(a-b) - 2^(a-2b) + 2^(a-3b) ... - 2^(a-2kb)) = 2^a - 1.

Par conséquent, en prenant a = 2^n et b = 2^m avec n > m,
2^2^n - 1 = 0 mod 2^2^m + 1, et donc
2^2^n + 1 = 2 mod 2^2^m + 1.

Donc pgcd(2^2^n+1, 2^2^m+1) = pgcd(2, 2^2^m+1) = pgcd(2, 1) = 1.

[miikou]

nimporte quoi ?

et bien je vais etre plus clair :)
si p divise le nombre de fermat alors

1)2^2^n-1 = 0 (p) => 2^2^n = -1 (p) => 2^2^(n+1) = 1 (p) et c'est pas bien compliqué de constaté que 2^(n+1) est le plus petit exposant pour lequel la relation est verifiée.

2) d'apres fermat 2^p=2 (p)
=> 2^p - 2 = p*q
=> 2(2^(p-1) -1 ) =p*q

d'apres Gauss p | 2^(p-1) - 1

=> 2^(p-1) = 1 (p)

3) lemme : a^k=1(p) on choisi k0 le plus petit alors k est un multiple de k0


1) + 2) + 3) => p=k*2^(n+1)+1

je pense que la on est d'accord !

[Doraki]

ah ouais ça marche, désolé.

Mais je suis toujours pas convaincu par la fin.
Si a < b,
p = 1 mod 2^(a+1) et p = 1 mod 2^(b+1) <=> p = 1 mod 2^(b+1).
y'a pas de contradiction là.

[miikou]

h*2^(b+1)+1 divise jms 2^2^a+1 sous la condition a