Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
192 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Divertissement (4)

Envoyé par Sneg 
Divertissement (4)
il y a trois mois
Bonjour à toutes et à tous
Je propose à qui serait intéressé la petite énigme suivante.

Quel est ce quelque chose qui me permet de calculer l'ordre de $7$ modulo le produit de nombres premiers $499\times 997=497.503$ sans la moindre difficulté, mentalement même ?
(Et je n'ai pas d'aptitude particulière pour le calcul mental.)
Bon samedi.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Re: Divertissement (4)
il y a trois mois
avatar
499=490×10+9.
49×2=98 donc 997=980+17.
Ensuite je pense que ça va tout seul.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: Divertissement (4)
il y a trois mois
Ensuite, ça va tout seul ?
Re: Divertissement (4)
il y a trois mois
Apparemment, « tout qui », équivalent de « quiconque », serait un belgicisme, d’où la correction de AD au message initial.

Je ne savais pas.
Re: Divertissement (4)
il y a trois mois
2x3=6 ?
Re: Divertissement (4)
il y a trois mois
Salut Sneg,
Excuse mon ignorance, mais que signifie " l'ordre de 7 modulo..." ?
Re: Divertissement (4)
il y a trois mois
Bonjour, nodgim.

Tu n'as pas à t'excuser. C'est, au contraire, moi qui te remercie d'intervenir.

Par "calculer l'ordre de $7$ modulo $497.503$", je veux dire "Trouver le plus petit entier $m$ strictement positif tel que $7^m\equiv 1\pmod{497.503}$.

Le problème consiste à identifier "quelque chose", mettre la main sur quelque chose, permettant d'arriver à la solution par un simple calcul mental.

Bonne soirée !



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par Sneg.
Re: Divertissement (4)
il y a trois mois
Un rappel : $7\times11\times13=1001$. Je ne vois pas quoi en faire.

Edit: suppression d'une formule fausse...



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Math Coss.
Re: Divertissement (4)
il y a trois mois
Avec le théorème de Fermat on voit sans calculs que l'ordre de $7$ modulo $499\times 997$ est un diviseur de $996=2\times 498$.
Re: Divertissement (4)
il y a trois mois
avatar
Argl, j’ai compris l’inverse…

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: Divertissement (4)
il y a trois mois
@ Jandri :
Dans le petit théorème de Fermat, le module est un nombre premier.
Re: Divertissement (4)
il y a trois mois
Jandri a raison tout de même.

Puisque 499 et 997 sont premiers :

7 ^ 498 - 1 = 0 [499] et donc également 7 ^ (2*498) = 7 ^ 996
7 ^ 996 - 1 = 0 [997] et donc = 0 [499*997]

donc m est un diviseur de 996 = 2 * 2 * 3 * 83.

Mais ce petit quelque chose qui manque est il calculable mentalement ?
JLT
Re: Divertissement (4)
il y a trois mois
avatar
On peut aussi dire que $m$ est un multiple de $4$. En effet, s'il ne l'était pas alors pour $q=997$ on aurait $7^{(q-1)/2}\equiv 1\pmod{q}$, donc d'après la loi de réciprocité quadratique, $1=(\frac{7}{997})=(\frac{997}{7})=(\frac{3}{7})=-(\frac{7}{3})=-1$.
Re: Divertissement (4)
il y a trois mois
Bon dimanche à vous tous, les intervenants de ce fil. Merci à chacun.

Loin de moi l'envie de vous faire chercher trop longtemps. Alors, je vais vous donner un petit indice :

Soit $p$ un nombre premier et $a$ un entier strictement positif non multiple de $p$.
Quel élément de théorie relatif à $a$ (par rapport à $p$) vous fera connaître sur-le-champ l'ordre de $a$ modulo $p$ ?

Voilà.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Sneg.
Re: Divertissement (4)
il y a trois mois
Solution du problème posé dans le message initial.

Ce "quelque chose", le voici :

Si l'on vient à "découvrir" que $7$ est une racine primitive modulo $499$ ainsi que modulo $997$, alors l'affaire est dans le sac.

Et l'on peut "découvrir" cela en consultant, entre autres, la suite $A001918$ de l'OEIS ou plus simplement encore en consultant la page Wikipédia intitulée "Racine primitive modulo $n$" et son tableau donnant la plus petite racine primitive modulo chacun des nombres premiers inférieurs à $1000$, comme $499$ et $997$.
JLT
Re: Divertissement (4)
il y a trois mois
avatar
Sauf que déterminer si un nombre est une racine primitive modulo 499 ne peut pas se faire mentalement, sauf aptitudes exceptionnelles.
Re: Divertissement (4)
il y a trois mois
Bonjour à tous,

la réponse de Sneg ne me plaît pas du tout.
C'est un peu comme s'il avait proposé une grille de mots croisés pas facile en assurant l'avoir résolue en quelques minutes. Ben oui, nous dit-il : il suffit de recopier la solution qui est donnée à la dernière page du journal!

Notons qu'il suffit de savoir que $7$ est racine primitive modulo $997$ pour conclure que l'ordre de $7$ modulo $499 \times 997$ est $996$: ça ne sert à rien de savoir que, de plus, $7$ est racine primitive modulo $499$: en effet, l'ordre de $7$ modulo $499 \times 997$ est le ppcm des ordres de $7$ modulo $499$ et modulo $997$; l'ordre de $7$ modulo $499$ divise $498$ et donc $996$ et donc,quel qu'il soit (i.e. $498$ ou un de ses diviseurs stricts), son ppcm avec $996$ sera $996$.



l'ordre $m$ de $7$ modulo $499 \times 997$ est, comme il a été déjà expliqué, un multiple de $4$ et un diviseur de $4 \times 3 \times 83$.

$83$ est premier.

Donc $m \in \{4, 4 \times 3, 4 \times 83, 4 \times 3 \times 83\}$.

$4$ et $12$ sont éliminés "de tête".

$m=4 \times 3 \times 83$ SSI $7$ n'est pas un cube modulo $499$ ou modulo $997$.

Je sais qu'il existe une loi de réciprocité cubique mais je ne la connais pas.

Je tente de m'en sortir "de tête" en visant le $1000$ ou ses petits multiples ( en vérité le $997$) et en le ratant de "peu" à plusieurs reprises. J'utilise ces ratages de "peu" pour montrer que $7$ n'est pas un cube modulo $997$ et que donc $m=4 \times 3 \times 83$.

Ma méthode n'est sûrement pas celle de Sneg vu qu'il précise qu'il est une quiche en calcul mental, alors que j'utilise des compétences telles que $2^{10}=1024, 7^3=343, 7 \times 11\times 13=1001$...

Je montre que $2, 3, 5$ sont des cubes modulo $997$, puis que si $7$ était aussi un cube modulo $997$, ça ferait trop de cubes modulo $997$.

Bien entendu, je m'autorise l'usage du stylo winking smiley

Paul
Re: Divertissement (4)
il y a trois mois
Bonsoir,

En mettant en avant la grande simplicité des calculs, j'espérais mettre quelqu'un sur la voie des racines primitives puisque l'ordre d'une racine primitive modulo un nombre premier $p$ présente la particularité d'être facile à calculer : il est égal à $p-1$. L'indice que je vous avais donné plus tard allait dans ce sens.

Une fois l'hypothèse des racines primitives échafaudée, déterminer si le nombre $7$ - le nombre qui est au centre de ce problème - est bien une racine primitive modulo $499$ et $997$ pouvait se faire simplement en consultant le tableau mentionné dans mon message précédent, car rien ne vous en empêchait dans l'énoncé du problème. Ce n'est pas de ma faute si vous vous interdisez vous-mêmes le recours à ce genre d'information mise à la disposition de tout un chacun.

Sachant, grâce au tableau dont la consultation est contestée par depasse, que $7$ est une racine primitive modulo $499$, on en déduit aisément que l'ordre multiplicatif de $7$ modulo $499$ est égal à $498$.

Sachant d'autre part, grâce au même tableau, que $7$ est une racine primitive modulo $997$, on en déduit tout aussi facilement que l'ordre multiplicatif de $7$ modulo $997$ est égal à $996$.

Par conséquent, l'ordre de $7$ modulo $499\times 997$ est égal au ppcm(498;996), calcul qui, je l'espère, est mentalement à la portée de tous ici, et pas seulement de moi.

Cela dit, si ce problème a causé des nuits blanches à l'un d'entre vous, je le prie de bien vouloir m'en excuser.



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par Sneg.
JLT
Re: Divertissement (4)
il y a trois mois
avatar
Etre une racine primitive modulo $p$ est équivalent à être d'ordre $p-1$. On avait bien remarqué que c'était ça qu'il fallait démontrer, mais on ne savait pas que la solution était sur un tableau de Wikipedia.

Si je raisonne comme toi, je pourrais donner comme énigme : "déterminer la 1000e décimale de $\pi$ sans la moindre difficulté, mentalement même ? (Et je n'ai pas d'aptitude particulière pour le calcul mental.)"
Re: Divertissement (4)
il y a trois mois
@ Sneg :

Pardon, mais je partage entièrement les réactions de Dépasse et JLT. Effectivement, si on sait que l'ordre de 2 modulo 997 est 996 ( ce qui revient à dire que 2 est racine primitive) alors oui le problème se résout mentalement. Je m'attendais à une réponse plus intéressante.
Re: Divertissement (4)
il y a trois mois
@ tous :

Si je vous avais sérieusement - c'est-à-dire pas dans le cadre d'un simple divertissement - demandé de m'aider à trouver, sans recourir à un logiciel de calcul, l'ordre de $7$ modulo $497.503$ et que l'un d'entre vous avait eu l'idée de résoudre le problème au moyen de la méthode "sans calculs" que j'ai détaillée dans mon message précédent, il ne se serait pas privé d'employer cette méthode, car, en mathématiques, plus un moyen de résoudre un problème est expéditif, meilleur il est.

Donc, je ne comprends pas vos critiques.

Ce n'est pas de ma faute si vous ignoriez qu'il existe une liste OEIS des plus petites racines primitives modulo un nombre premier.

Le but de la question initiale - posée dans le cadre d'un simple divertissement, je le répète - était précisément de savoir si vous saviez.

La réponse est manifestement non et je déplore un peu que personne n'ait eu au moins la courtoisie de me remercier pour lui avoir, très modestement, appris un petit quelque chose.



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par Sneg.
JLT
Re: Divertissement (4)
il y a trois mois
avatar
Si, je connaissais la notion de racine primitive modulo p, et j'avais bien vu le lien avec ta question, mais je n'en avais pas parlé car je considérais que c'était une reformulation triviale de ton problème.
Re: Divertissement (4)
il y a trois mois
D’accord, JLT.
Merci d’être intervenu sur ce fil. Comme à chacun.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Sneg.
Re: Divertissement (4)
il y a trois mois
Bonjour à tous,

quelques précisions sur ma(?) technique du "ratage de peu" dont j'ai bien conscience qu'elle est un gadget car elle n'est employable mentalement que pour des petits nombres.

Un exemple: " $7$ est-il un cube modulo $499$" ?
On calcule dans $\mathbb {F_{499}}$ tout en utilisant la décomposition en facteurs premiers dans $\mathbb N$.

$500=1=2^25^3$ donc $2$ est un cube.
$512=2^9=13$ donc $13$ est un cube.
$81 \times 6= 3^5 2 =486=-13$ donc $3$ est un cube.
$1001=7 \times 11 \times 13=3$ donc $7$ et $11$ sont dans la même classe (i.e. tous deux sont cubes ou tous deux non-cubes).
$495=11 \times 45 =11 \times 3^2 \times 5=-4$ donc $5$ et $11$ sont dans la même classe.

Finalement $2,3,13$ sont des cubes et $5,7,11$ sont tous trois cubes ou tous trois non-cubes.

Mais ces trois derniers ne peuvent être des cubes à cause de la proposition suivante que Sneg trouvera aisément sur Internet:

Si $p$ premier est congru à $1$ modulo $6$, le plus petit entier qui n'est pas un cube modulo $p$ est un nombre premier inférieur à $\sqrt{\frac{p-1}{2}}$.

En l'occurrence $17^2>249$ et donc $5, 7, 11$ ne sont pas des cubes.

Remarque: la propositon se généralise:

Pour tout premier impair $d$ et tout premier $q$ congru à $1$ modulo $d$, le plus petit entier qui n'est pas une puissance $d$ème modulo $q$ est un nombre premier inférieur à $\sqrt{\frac{p-1}{2}}$.

sauf erreur, comme d'hab

Cordialement

Paul



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par depasse.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 136 655, Messages: 1 321 417, Utilisateurs: 24 147.
Notre dernier utilisateur inscrit Topos.


Ce forum
Discussions: 5 062, Messages: 61 300.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page