Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Racines carrée de 1

Posté par
LittleFox
07-02-18 à 15:29


Soit n = \prod_{i=1}^{20} p_i^{p_i}p_i est le ième nombre premier (p_1,p_2,p_3,... = 2,3,5,...).

Quelle est la somme de tous les a tels que 0 \le a < n et a^2 \equiv 1 \pmod n?

On donnera le résultat modulo 1000000007.

J'espère que ce ne sera pas trop difficile mais pas trop facile non plus. N'oubliez pas de blanker, merci

Posté par
LittleFox
re : Racines carrée de 1 09-02-18 à 10:28


Indice, commencez par n = \prod_{i=1}^{k} p_i^{p_i} avec k=2,3,4 et extrapolez

Posté par
dpi
re : Racines carrée de 1 09-02-18 à 16:02

Je fais une petite avancée :

 Cliquez pour afficher

Posté par
LittleFox
re : Racines carrée de 1 12-02-18 à 09:12


Comme le fait remarquer dpi les nombres obtenus sont très grands et difficilement calculable. Et pas du tout énumérable.

Donc parcourir tous les a possibles n'est pas faisable dans un temps raisonnable, la force brute ne marchera pas.

Note: le modulo est important. Si 71^{71} est un nombre à 132 chiffres (et n un nombre à 1035 chiffres), leur modulo est parfaitement calculable avec l'exponentiation modulaire. pow(x,y,z) en python

Autres indices :

 Cliquez pour afficher

Posté par
dpi
re : Racines carrée de 1 12-02-18 à 12:39

Bonjour,

En faisant remonter, j'espère que tu auras des réponses; pour ma part, il y a très longtemps que je n'ai pas travaillé sur les  congruences et j'attends donc les experts....

Posté par
dpi
re : Racines carrée de 1 23-02-18 à 19:01

Posté par
LittleFox
re : Racines carrée de 1 28-02-18 à 19:37

C'est gentil dpi mais je crois que ça fait trop peur ^^

Pourtant pas besoin de maths avancées.
Enfin, je n'ai pas une preuve de ma réponse, seulement des observations empiriques.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !