Période et Facteurs Premiers

[Rouvire]

Bonjour,
On prend p et q premiers différents l’un de l’autre et différents de 2.
On fait la division 1/pq en base 2. La division est périodique. La période a une certaine longueur Lng (cette longueur n’est pas forcément la même que celle qu’on aurait pu obtenir en faisant la division dans une autre base).

Par exemple pour 91 = 7*13, la division 1/91 en base 2 donne les restes: 1, 2, 4, 8, 16, 32, 64, 37, 74, 57, 23, 46, 1, … Après 12 restes différents ont retombe à 1. La longueur de la période est 12.

On décompose cette longueur en facteurs premiers, on s’aperçoit que ses facteurs premiers appartiennent aussi à ceux de p-1 et/ou de q-1. Ici 12=2*2*3 et (7-1)=2*3 et (13-1)=2*2*3

Un autre exemple: 22013*33569 = 738954397.
Pour 1/738954397 en base 2, on trouve une période de longueur Lng = 23090588.
On a: 23090588 = 2*2*1049*5503
Et (22013-1) = 2*2*5503, et (33569-1) = 2*2*2*2*2*1049

Un autre exemple: 5261*6899 = 36295639.
Pour 1/36295639 en base 2, on trouve une période de longueur Lng = 18141740.
On a: 18141740 = 2*2*5*263*3449
Et (5261-1) = 2*2*5*263 et (6899-1) = 2*3449

Est-ce-que c’est toujours vrai, et si oui quelle explication?

Merci

[GaBuZoMeu]

Tu t'intéresses à la suite des modulo .
Ça se passe dans le groupe multiplicatif des inversibles modulo , qui est un groupe d'ordre . La période est l'ordre de dans ce groupe. L'ordre d'un élément est toujours un diviseur de l'ordre du groupe (théorème de Lagrange), donc ici la période est toujours un diviseur de .
J'emploie sans doute un vocabulaire technique qui ne t'est pas familier. Dis-moi ce que tu ne comprends pas.

[Rouvire]

Merci GaBuZoMeu.
Je crois que j'ai compris.

Par exemple on prend p=7 et q=11 soit pq=77
Le groupe des inversibles modulo 77 à un ordre de 60 (il a 60 éléments, représentés par les nombres de 1 à 76 moins les multiples de 7 ou de 11)
Il est multiplicatif: sa loi de composition interne (*) se "manie" comme la multiplication "normale".
Ex: 47*17=29 (799 est congru à 29 modulo 77)
1 est l’élément neutre: 1*X=X*1=X
Chaque élément a un inverse. Ex 50*57=1 (2850 est congru à 1 modulo 77) . 57 est l'inverse de 50
La loi est associative

L’ordre de 2 dans ce groupe est 30 (on a 2^30 congru à 1 modulo 77) et c’est aussi la période de 1/77 et il divise bien 60 (théorème de Lagrange).

[GaBuZoMeu]

Voila. Maintenant tu peux passer au produit de trois premiers distincts.

[Rouvire]

Bonjour,
Le groupe multiplicatif des inversibles modulo pq a un ordre X=(p-1)(q-1).
Si les X éléments de ce groupe sont toujours représentés par les nombres de 1 à pq moins les multiples de p ou q et si on a un algorithme rapide pour trouver la période P de 1/pq en base 2, il me semble qu’on peut trouver assez facilement la valeur de (p-1)(q-1).
En effet (p-1)(q-1) doit être proche de ([pq/P])*P. (partie entière de pq/P multipliée par P).
Par exemple: p=859 et q=1063, pq=913117 et on trouve une période P=151866.
On a 913117/151866=6,012649… et on a 6*151866=(859-1)*(1063-1)=911196.

Si on a pq et (p-1)(q-1) on a aussi p+q.
p+q=913117-911196+1=1922=859+1063.

On a alors la somme S et le produit P de 2 nombres (p et q), on peut alors trouver ces 2 nombres avec les racines du polynôme X²-SX+P=0.

J’ai l’impression qu’en informatique un algorithme pour trouver la période de 1/pq en base 2 doit être assez rapide, est-ce-qu'une impression ?

[GaBuZoMeu]

Si tu veux te faire comprendre des pros, il vaut mieux que tu parles de l'ordre multiplicatif de 2 modulo .

Quant aux algorithmes pour trouver l'ordre multiplicatif modulo , rien de très brillant si on ne dispose pas de la décomposition en produit de facteurs premiers.

[Rouvire]

Bonjour,

Il y a une vidéo sur youtube "The Reciprocals of Primes" par Numberphile" qui montre qu'un anglais du 19éme siècle W. Shanks, a calculé, à la main, la longueur des périodes pour des nombres premiers jusqu'à 110.000.
Il calcule en base 10 et par exemple pour 60013 il a trouvé une longueur de période de 5001. (1/60013 est une fraction dont les chiffres doivent se répéter tous les 5001).
Apparemment, Numberphile, pense qu'il avait une méthode "spéciale" pour faire ça. (calculer tout ça à la main parait impossible).
Est-ce-que quelqu'un a une idée de la méthode?

Merci.