[T S] Primalité

[Anonyme]

Bonjour à nouveau !

Je souhaiterais savoir s'il n'existe pas un moyen simple de voir la primalité
de 2^11 - 1 ..

Bien entendu, sans faire appel aux nombres de Mersennes ... sans aucune théorie
au-delà du programme de Terminale S ...

Je ne vois pour ma part que la manière "bête" : ENT(rac(2^11 - 1)) = 45.
On teste donc avec tous les nombres premiers inférieurs à 45 ... Mais ça me
semble long pour une première question de bac (donné en 1973)...

Merci d'avance.

[Anonyme]

On 11 Dec 2004 21:10:23 GMT, pasquetstephane wrote:

> Bonjour à nouveau !
>
> Je souhaiterais savoir s'il n'existe pas un moyen simple de voir la primalité
> de 2^11 - 1 ..
>
> Bien entendu, sans faire appel aux nombres de Mersennes ... sans aucune théorie
> au-delà du programme de Terminale S ...
>
> Je ne vois pour ma part que la manière "bête" : ENT(rac(2^11 - 1)) = 45.
> On teste donc avec tous les nombres premiers inférieurs à 45 ... Mais ça me
> semble long pour une première question de bac (donné en 1973)...
>

Je dirais que 2^11 - 1 = 2047.
Les facteurs pourraient donc se terminer par:
1 et 7
3 et 9

Il reste donc peu de nombres à essayer et on voit assez bien avec un
ordre de grandeur que ça ne marche pas.

Mais ce n'est peut-être pas ce qu'ils demandaient.

--
Nicolas

[Anonyme]

> Je souhaiterais savoir s'il n'existe pas un moyen simple de voir la
> primalité
> de 2^11 - 1 ..
>
> Bien entendu, sans faire appel aux nombres de Mersennes ... sans aucune
> théorie
> au-delà du programme de Terminale S ...
>
> Je ne vois pour ma part que la manière "bête" : ENT(rac(2^11 - 1)) = 45.
> On teste donc avec tous les nombres premiers inférieurs à 45 ... Mais ça
> me
> semble long pour une première question de bac (donné en 1973)...

Supposons que 2^11-1 ne soit pas premier: il a alors un facteur premier
p<45, et 2^11=1 mod p.
En multipliant par (p+1)/2 (possible car p est forcément impair, vu que
2^11-1 est impair), qui est inverse de 2 modulo p: 2^10=(p+1)/2 mod p. Ainsi
(p+1)/2 est un carré non nul modulo p, donc son inverse 2 aussi. On a donc:
2^((p-1)/2)=1 mod p.
Sachant que les seules valeurs possibles de p sont 3, 5, 7, 11, 13, 17, 19,
23, 31, 37, 41 et 43, on a respectivement (p-1)/2=1, 2, 3, 5, 6, 8, 9, 11,
15, 18, 20 et 21. Les puissances modulo p se calculent facilement:
2^1=2 mod 3
2^2=4 mod 5
2^3=8=1 mod 7
2^5=32=10 mod 11
2^6=64=12 mod 13
2^8=16^2=1 mod 17
2^9=2*16^2=18 mod 19
2^11=1 mod 23
2^15=32^3=1 mod 31
2^18=8*32^3=8*(-125)=8*23=36 mod 37
2^20=(1024)^2=(-1)^2=1 mod 41
2^21=128^3=(-1)^3=42 mod 43

Les seuls facteurs premiers possibles de 2047 sont donc 7, 17, 23, 31 et 41.
Or: 2100 est un multiple de 7, et pas 53, donc 2047 ne l'est pas.
1717 est multiple de 17, donc 330 le serait aussi si 2047 l'était, donc 347,
donc 7 aussi: absurde.
2047=23*89, donc 2^11-1 n'est pas premier...

Un peu tordu, mais fait sans calculette!

--
Mû

[Anonyme]

> Les seuls facteurs premiers possibles de 2047 sont donc 7, 17, 23, 31 et
> 41.

Il fallait bien spur lire: les seuls facteurs premiers <45 possibles sont 7,
17, 23, 31 et41.

--
Mû

[Anonyme]

"pasquetstephane" a écrit

> Je souhaiterais savoir s'il n'existe pas un moyen simple de voir la
> primalité
> de 2^11 - 1 ..
>
> Bien entendu, sans faire appel aux nombres de Mersennes ... sans
> aucune théorie
> au-delà du programme de Terminale S ...
>
> Je ne vois pour ma part que la manière "bête" : ENT(rac(2^11 - 1)) =
> 45.
> On teste donc avec tous les nombres premiers inférieurs à 45 ... Mais
> ça me
> semble long pour une première question de bac (donné en 1973)...

Soient p un diviseur premier impair de 2^11 - 1, d le plus petit entier
strictement positif tel que 2^d = 1 mod p et n un entier tel que 2^n = 1
mod p.
On peut écrire n = dq + r (division euclidienne).
Donc 2^r = 1 mod p et donc r = 0 (sinon d ne serait pas le plus petit.)
Par hypothèse, 2^11 = 1 mod p, donc d divise 11.
Comme d n'est pas égal à 1, d = 11.
D'après le th. de Fermat 2^(p-1) = 1 mod p.
Donc d divise p -1 c'est-à-dire 11 divise p - 1.
Comme p - 1 est pair, il est même divisible par 22.
p est donc de la forme 22k + 1.
Les valeurs possibles de p sont donc 23, 47, 67, 89,...
Seul 23 est à tester, car inférieur à 45. On trouve 2^11 - 1 = 23*89.

Cordialement
Stéphane

[Anonyme]

"Stéphane Ménart" a écrit

> p est donc de la forme 22k + 1.
> Les valeurs possibles de p sont donc 23, 47, 67, 89,...

23, 67, 89 mais pas 47, bien sûr, ni même 45 qui n'est pas premier...

[Anonyme]

On Sun, 12 Dec 2004 12:07:24 +0100, "Stéphane Ménart"
wrote:


>Soient p un diviseur premier impair de 2^11 - 1, d le plus petit entier
>strictement positif tel que 2^d = 1 mod p et n un entier tel que 2^n = 1
>mod p.
>On peut écrire n = dq + r (division euclidienne).
>Donc 2^r = 1 mod p et donc r = 0 (sinon d ne serait pas le plus petit.)
>Par hypothèse, 2^11 = 1 mod p, donc d divise 11.
>Comme d n'est pas égal à 1, d = 11.
>D'après le th. de Fermat 2^(p-1) = 1 mod p.
>Donc d divise p -1 c'est-à-dire 11 divise p - 1.
>Comme p - 1 est pair, il est même divisible par 22.
>p est donc de la forme 22k + 1.
>Les valeurs possibles de p sont donc 23, 47, 67, 89,...
>Seul 23 est à tester, car inférieur à 45. On trouve 2^11 - 1 = 23*89.
>
>Cordialement
>Stéphane
"marrant"
la méthode ci-dessus (elle se généralise sans pb) appliquée à 2^23-1
donne comme 1er nb 1er candidat
47, lequel divise effectivement 2^23-1 , qui n'est pas 1er donc


moins marrant
j'avais noté dans mes papiers :
2^44497-1 est 1er : exercice p133 du bs TS spé Nathan
mais bernique je ne retrouve pas cet exo (ni p33
ni p13) et j'ai pas envie de le refaire...pour l'instant

[Anonyme]

Marc Pichereau wrote:

>...
> moins marrant
> j'avais noté dans mes papiers :
> 2^44497-1 est 1er : exercice p133 du bs TS spé Nathan
> mais bernique je ne retrouve pas cet exo (ni p33
> ni p13) et j'ai pas envie de le refaire...pour l'instant

c'est un nombre de Mersenne dont la primalite a ete prouvee en 1979 sur
Cray1. J'aimerai bien croire que le niveau monte mais quand bien meme ce
serait le cas il m etonnerait que tu en trouves une preuve adaptee aux
terminales...