Factorielle allégée
dans Arithmétique
Bonjour,
la factorielle allégée
On note $(n!)_2$ la factorielle de n alléger de 2, qui est le produit des nombres entre 1 et n, à l'exception des nombres pairs.
Calculer :$(2^{77}!)_2 \mod 2^{101}$
PS : l'usage de la calculatrice est recommandée.
Bonne journée.
la factorielle allégée
On note $(n!)_2$ la factorielle de n alléger de 2, qui est le produit des nombres entre 1 et n, à l'exception des nombres pairs.
Calculer :$(2^{77}!)_2 \mod 2^{101}$
PS : l'usage de la calculatrice est recommandée.
Bonne journée.
Réponses
-
Dans pas mal de bouquin, ce que tu appelles "factorielle allégée" est noté $(2n)!!$.
-
Et comment note-t-on la factorielle allégée de 101 : $(n!)_{101}$ ?
-
Le reste demandé (bien que la question soit mal posée je l'ai comprise de la sorte) est, sauf erreur,:
$1045593516627615941359991749983$ -
Peux tu me dire l’ambiguïté que tu vois dans l'énoncé proposé, en effet je ne trouve pas le même résultat que toi ?
De toutes les façons ce qui compte plus que le résultat c'est la méthode pour y arriver, donc si tu pouvais décrire ton algorithme en quelques mots cela serait mieux. -
la notation $a \mod{n}$ ne signifie pas le reste dans la division euclidienne de $a$ par $n$.
J'ai mal lu la factorielle. :-D -
Je tente : 629631687561599003969942716417
-
J'aurais aimé que tu me résumes comment tu as procédé, inutile de rentrer dans les détailles trois phrases de moins d'une ligne chacune devrait être amplement suffisante.
Merci. -
Je n'ai même pas cherché de démo. J'ai regardé l'écriture binaire de $(2^n!)_2$ pour les premières valeurs de $n$, i.e j'ai décomposé $(2^n!)_2$ comme somme de puissances de $2$. Il est facile de conjecturer quelles sont les plus petites puissances de $2$ qui interviennent dans cette décomposition. Et pour les plus grandes, on s'en fiche, puisque pour $n=77$, elles dépasseront $2^{101}$.
En me basant sur ma conjecture, ça donne alors la valeur que j'ai postée. -
Bravo, je trouve la même chose que toi, mais pas par le même chemin.
Avant de donner ma solution (qui est simple), j'attends que ceux qui prétendent que cette exercice est classique, donne la solution classique.
A noter que par cette méthode on peut calculer des choses plus biscornues comme :
$(2^{77}!)_{2,3} \mod 2^{101}$ ou encore $\sum \limits_{i\in [0,2^k]} f^i(0) \mod 2^{101}$ avec $f$ un polynôme quelconque, avec $f^2(x)=f(f(x))$.
La seule limite semble être notre imagination ( : j'exagère un peu) -
Factorielle allégée=factorielle de Morita.
Gros classique -
Aurais-tu un lien vers ce classique ?
Merci. -
Et donc finalement, quelle est ta solution simple ?
-
Bonjour,
J'attends d'avoir un lien vers ce classique ou qu'on explicite clairement le procédé et alors je donnerais la solution que je crois connaître.
Bonne journée. -
Bon, il semblerait que cette solution simple n'existe pas. Peux-tu nous faire part de tes lumières, maintenant ?
-
Bonjour,
C'est bien ce que je me disais...
Mais laissons un jour à ceux qui prétendent que cette énoncé est un classique, pour produire la réponse classique...
Passer ce délai je publierai, la solution que je crois connaître.
Bonne journée. -
Bonjour,
Je t'ai envoyé la réponse par MP.
Bonne journée. -
Joaopa est un troll. Peux-tu rendre publique ta solution ? Ça ne sert à rien de la dissimuler... Et ça intéresse certains d'entre nous.
-
Ok, sans problème :
On pose $P_{n}(X)=X(X+1)...(X+n-1)$ on a pour tout $k\in \Z$, $n!|P_n(k)$, et $104! \mod 2^{101}=0$.
Alors pour tout $k \in\Z_{2^{101}}$ $P_{104}(k) \mod 2^{101}=0$.
On travaille dans l'anneau $\Z_{2^{101}}$, alors on pose :
$R_0(X)=2X+1$
$R_{k+1}(X)=R_k(X)\times R_k(X+2^{k}) \mod P_{104}(X)$
On calcule $R_{76}(X) \mod P_{104}(X)$ et $R_{76}(0)=(2^{77})_2 \mod 2^{101}$.
Si vous avez des questions n'hésitaient pas.
Bonne journée. -
Sans question et sans réfléxion:
Conséquence directe de Proposition 11.6.15 de Henri Cohen Number theory Vol.2
Signé: le troll -
Bonjour,
Quelqu'un peut-il nous dire ce qu'énoncerait cette proposition ?
Merci. -
Bonjour,
Non, personne ?
Même pas Joaopa ?
Bonne journée. -
Bonjour,
Il n'y a pas la p 374, partie 11.6.1.
Mais il parle de la fonction gamma sur les nombres p-adics donc approprie cela n'a qu'un rapport lointain avec la question initiale (calcul de la factorielle allégé).
Bonne journée. -
Bonjour,
En laissant de côté cette polémique avec Jaoapa, êtes vous d'accord pour qualifier de simple la solution proposée ?
PS : du coup c'est moi qui ait besoin de vos commentaires pour faire avancer mes recherches.
Bonne journée. -
Bonsoir,
à noter qu'ainsi on peut construire un protocole d'échange de clef secrète.
Bonne soirée. -
Bonjour,
Oui, mais alors il ne serait pas sûr.
Bonne journée. -
Bonjour,
Un nouveau résultat sur la factorielle allégée : http://www.les-mathematiques.net/phorum/read.php?43,1198849,1349360#msg-1349360
Bonne journée.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 31
+23 Invités