Exo intéressant
dans Arithmétique
Bonjour
Soit n un nombre pair.
P = {p_1, p_2, ..., p_m} l'ensemble des nombres premiers inférieurs à n et premiers avec n.
Montrer qu'il existe p_i et p_j de P qui ont le même carré modulo n.
Merci de votre aide.
Soit n un nombre pair.
P = {p_1, p_2, ..., p_m} l'ensemble des nombres premiers inférieurs à n et premiers avec n.
Montrer qu'il existe p_i et p_j de P qui ont le même carré modulo n.
Merci de votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
J'ai oublié de préciser que n est supérieur à 10
Merci
[Corrigé dans le titre. AD]
Je pensais à un raisonnement du style principe des tiroirs mais il faudrait connaitre le nombre de carrés modulo $n$, et je ne me souviens pas du résultat...
en tout c'est intéressant je suis d' accord
Je laisse à d'autres le plaisir de chercher avant de dévoiler la réponse !
[Au passage, de manière plus générale, il est facile d'exprimer le cardinal de l'ensemble des carrés de $(\Z/n\Z)^*$ en calculant le noyau du morphisme (on trouve qu'il y en a $\psi(n)$, où $\psi$ est la fonction arithmétique multiplicative donnée par $\psi(p^k)=\phi(p^k)/2$ pour $p$ premier impair et $\psi(2^k)=\sup(1,2^{k-3})$).]
Du coup, le résultat paraît quand même heuristiquement difficile à croire (suivant l'idée que les nombres premiers sont censés être répartis « au hasard »), même si expérimentalement il semble vrai, en fait pour tous les entiers $n\geq 8$, pairs ou non, qui ne sont pas puissances d'un nombre premier impair. D'un autre côté, il n'est pas impossible que ce soit une simple coïncidence numérique (la probabilité que $2p/\ln(p)$ éléments choisis au hasard dans $p/2$ cases tombent dans des cases 2 à 2 distinctes doit être assez faible tant que $p$ n'est pas {\it très} grand).
L'exo a une source précise (autre qu'expérimentale, je veux dire)?
Si l' on admet l' hypothèse de Goldbach c'est bon par exemple : on trouve la décomposition du nombre pair comme somme de 2 nombres premiers et ces nombres là conviennent :
par exemple : $10=3+7$ et $7^2=49=9=3^2 \ [10]$
et cela marche car si $p_i+p_j=n$ alors $p_i+p_j=0 \ [n]$ donc $(p_i-p_j)(p_i+p_j)=0 \ [n]$ donc $p_i^2=p_j^2 \ [n]$.
Donc peut être l' exo a t-il été construit à l'aide ce cette hypothèse, et puis cela marche informatiquement car Goldbach a été vérifié très loin...
Peut être mt-i a t -il vu les choses différemment...
Par exemple : 32 = 29 + 3 (= 19 + 13).
SadYear
17'5 n1c3 70 83 1mp0r74n7, 8u7 17'5 m0r3 1mp0r74n7 70 83 n1c3.
J' aimerai bien que gadget agrég nous dise d' où vient l' exo...
Au fait Sad Year je ne comprend pas ton exemple?
D'ailleurs ça doit fonctionner avec Goldbach du moment que la décomposition n'est pas $n = p + p$ puisque si $n = p_i + p_j$ avec $p_j$ premier avec $n$ alors $p_i$ est aussi premier avec $n$.
Je cherche à m'éloigner de la 'piste' Goldbach en espérant que Gadget-agrég possède bien une démo ne reposant pas sur une conjecture... mais je reste désespérement sec. Encore un coup de la chaleur ?
SadYear
17'5 n1c3 70 83 1mp0r74n7, 8u7 17'5 m0r3 1mp0r74n7 70 83 n1c3.
Néanmoins, j'imagine que comme le résultat annoncé a l'air vrai pour tous les nombres non primaires, et pas seulement pairs, il y a peut-être une vraie preuve.
Si tu veux mon avis il y a de bonne chance pour que cette hypothèse de Goldbach un peu modifiée soit vérifiée heuristiquement :
" Tout nombre pair est la somme de deux premiers disctincts".
Dans ce cas on est d' accord que cela implique le résultat de l' exo.
Donc deux solutions soit :
-Gadget agrég a remarqué ce fait pour pondre un exo à partir de Goldbach
-Soit il existe une vrai solution qui ne fait pas appel à Goldbach ( puisqu' évidemment l' exo n' est pas équivalent à Goldbach)
J' avoue que je préfère si c'est la seconde solution...à suivre