Primalitéé

par **sad13** » 10 Mar 2012, 00:51

Bonsoir, je suis en train de bosser sur un algo sur la décompo. en nombres premiers; pourquoi pour le test de primalité on écrit 6k-1 ou 6k+1 et d'où viennent ces nombres?

"On cherche si 2 et 3 divisent N, puis on teste les diviseurs D entre 5 et E() de la forme 6*k - 1 ou 6*k + 1. "

De plus,
les premiers nombres premiers sont : 2,3,5,7,11,13,17,37 et 37 ne s'écrit pas sous la forme 6k+-1

par **Blueberry** » 10 Mar 2012, 09:02

Ses diviseurs premiers ne sont divisibles ni par 2, ni par 3, ils sont donc congrus à 1 ou -1 modulo 6.
Donc on ne teste que les nombres de la forme 6k - 1 et 6k + 1.

par **sad13** » 10 Mar 2012, 10:34

Ok merci mais il faudrait le montrer "Ses diviseurs premiers ne sont divisibles ni par 2, ni par 3, ils sont donc congrus à 1 ou -1 modulo 6" pourquoi pas par 7 ni 11 mais par 6

par **nodjim** » 10 Mar 2012, 11:01

Parce que 7 et 11 n'existent pas modulo 6. Plus précisément :
7=1 modulo 6
11=5=-1 modulo 6.

par **sad13** » 10 Mar 2012, 11:02

J'ai rectifié le message initial

Autrement dit, pourquoi est-on sût d'avoir balayé tous les facteurs premiers , si l'on cherche ceux de la forme 6k-1 ou 6k+1?

Merci

par **nodjim** » 10 Mar 2012, 11:10

6k+-0: jamais premier car divisible par 6
6k+-2: jamais premier car divisible par 2
6k+-3: jamais premier car divisible par 3
reste donc seulement
6k+-1

par **Blueberry** » 10 Mar 2012, 11:13

Déjà dit : si p premier

alors p = 1 ou p = -1 mod(6) (Vérifie-le c'est facile)
Donc les diviseurs premiers de ton nombre sont forcément de la forme 6k - 1 ou 6k + 1

par **sad13** » 10 Mar 2012, 13:39

Ok pas mal du coup en testant 2,3, puis 6k-1 et 6k+1 on a tous les facteurs premiers possibles

(5=6-1;7=6+1 .....)

merci

Primalitéé

Primalitéé

Qui est en ligne