Raisonnement sur les congruences : conjecture à démontrer ?

Discussions générales concernant les mathématiques.
[participation réservée aux membres inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
Noah

Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

D'abord en tant que petit nouveau sur le forum, bonjour à tous :D ! Je suis élève en école d'ingé et je me lance des petits défis mathématiques à mes heures perdues.

Ces derniers temps je me suis pris de passion pour la théorie des nombres, et les équations diophantiennes un peu tordues. Pour la résolution d'une d'entre elles, je suis arrivé à me pencher sur l'équation de congruence :

$$x^3\equiv x [p]$$
(p pas forcément premier).

Tout d'abord les premières constatations (faciles à démontrer) :
- (1) $0$, $1$ et $p-1$ sont toujours solutions (je les appelle triviales).
- (2) les solutions se répartissent symétriquement autour de $\frac{p}{2}$, c'est à dire que si $x$ est solution, $p-x$ l'est aussi.
- (3) pour $p > 6$, $x=2$ n'est jamais solution (et bien sûr, $x$ n'est pas solution si $p > x^3$ ).
- (4) si $p$ est premier alors les seules solutions sont les solutions triviales.
- (5) si $p=2^k$, on a en plus des solutions triviales, les solutions $x=\frac{p}{2}-1$ et $x=\frac{p}{2}+1$ .

(cette dernière mérite une petite explication : on a

$$(\dfrac{p}{2}-1)^3 = (2^{k-1} - 1)^3 = 2^{3(k-1)} - 3 \times 2^{2(k-1)} + 3 \times 2^{k-1} - 1$$
Or pour que $2^k$ divise $2^{n(k-1)}$ , il faut et il suffit que $n(k-1) \geqslant k$.
On met de côté les cas $k = 0$ ($p = 1$, tous les entiers congrus à 0) et $k = 1$ ($p=2$, pas beaucoup plus intéressants puisqu'on sait déjà que 0 et 1 sont solutions).
Donc pour $k>1$ , $2^k | 2^{n(k-1)} \Leftrightarrow n \geqslant \frac{k}{k-1}$ .

Or pour tout $k > 1$ :
$$1 < \dfrac{k}{k-1} \leqslant 2$$

Donc $2^k$ divise $2^{n(k-1)}$ pour tout $n \geqslant 2$.

Finalement : $$(2^{k-1}-1)^3 \equiv 3 \times 2^{k-1} - 1 [2^k]$$

et comme $3 \times 2^{k-1} = 2^k + 2^{k-1}$ :

$$(2^{k-1}-1)^3 \equiv 2^{k-1} - 1 [2^k]$$

donc $\frac{p}{2}-1$ est bien solution, et on peut faire le même raisonnement pour $\frac{p}{2}+1$. )


Bon, jusque là tout va bien, sauf que j'ai pu vérifier numériquement pour un grand nombre de cas ces deux conjectures :
- (6) si $p=2^k$ avec $k > 1$, les seules solutions éventuellement différentes des solutions triviales sont celles ci-dessus, $\frac{p}{2}\pm 1$ (elles sont effectivement distinctes des triviales pour $p \geqslant 8$ ).
- (7) si $q$ est une puissance d'un nombre premier $\ne 2$, alors les seules solutions sont les solutions triviales.

Et c'est justement là que le bât blesse .... Car pour prouver (4), je m'appuie sur le fait que la multiplication est intègre dans $\mathbb{Z} / p\mathbb{Z}$ quand $p$ est premier, en effet :

$$xy \equiv 0 [p]\Leftrightarrow \exists n \in \mathbb{Z} : xy = np$$

$p$ apparaît donc dans la décomposition en facteurs premiers de $xy$, donc dans au moins une de ces deux variables ; donc $p | x$ ou $p | y$ (ou les deux), c'est-à-dire :

$$\forall p \mbox{ premier, } xy \equiv 0 [p] \Rightarrow x\equiv 0 \mbox{ ou } y \equiv 0 [p]$$

et on généralise ensuite à plus de deux termes, par associativité du produit (jusque là rien de nouveau ...)

Donc $x^3 - x \equiv x(x-1)(x+1) \equiv 0 [p]$ ($p$ premier) si et seulement si $x \equiv 0$ , $x \equiv 1$ ou $x \equiv -1 \equiv p-1$ .

Mais ce raisonnement ne s'applique pas aux puissances de nombres premiers, on peut simplement dire que si un produit est congru à 0 modulo $p^k$, alors $p$ est multiple d'au moins un des termes du produit. La question est alors : pourquoi on constate que pour les puissances de nombres premiers $\ne 2$, les seules solutions sont triviales, et pourquoi pour les puissances de 2, les seules autres solutions sont $\frac{p}{2} \pm 1$ ? Et pourquoi ce statut particulier du 2 ?

Voilà, sur cette jolie entrée en matière je retourne chercher la réponse et un café... amusez-vous bien :wink:
Dernière modification par Noah le samedi 07 août 2010, 16:24, modifié 1 fois.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Bon béh ça y est j'ai ma réponse ... Mais le forum est trop petit pour la contenir :D
sérieusement, je la rédigerai demain, là je vais me mater un petit film. Bonne soirée a tutti !
Noah

Solution + autre question

Message non lu par Noah »

Re

Je continue mon monologue.

$p$ est un nombre premier. Quand un produit est nul modulo $p^k$, c'est que le produit est multiple de $p^k$ ou qu'il est simplement nul. Dans ce dernier cas, on trouve les solutions "triviales" ; intéressons-nous à l'autre cas.

Pour que celui-ci se produise, il faut qu'au moins un des termes soit multiple de $p$. Plus précisément, si on note $e(x)$ l'exposant (éventuellement nul) de $p$ dans la décomposition en facteurs premiers de $x$, on voit que $e(xy...z) = e(x)+ e(y) + ... + e(z)$, donc pour que $x$ soit solution du problème il faut (et il suffit) que :

$$e(x-1)+e(x)+e(x+1) \geqslant k \mbox{(*)}$$

Or, il est clair qu'un nombre premier $> 2$ ne peut diviser trois entiers consécutifs (par exemple, si $p|n$, alors $\frac{n+1}{p} \notin \mathbb{N}$, et $\frac{n+2}{p} \in \mathbb{N}$ si et seulement si $p=2$ ; on voit au passage d'où vient ce statut particulier du 2.)

$p > 2$ devant diviser au moins un des trois entiers $x$, $x+1$ et $x-1$ (on note $x_0$ cet entier), il ne peut diviser les deux autres. Donc $e(x_0) \geqslant k$ si l'on veut satisfaire l'inégalité (*), c'est-à-dire que $p^k$ doit diviser $x_0$, ou que $x_0 \equiv 0 [p^k]$ (ce qui correspond aux solutions triviales), donc ce sont les seules solutions possibles.

Maintenant le cas $p=2$ : soit $x$ une solution ; si $x$ était pair, $x-1$ et $x+1$ seraient impairs, donc on aurait $e(x-1)=e(x+1)=0$, soit $e(x) \geqslant k$, donc $x \equiv 0 [2^k]$, ce qui ne nous donne que des solutions triviales. Supposons donc $x$ impair.
Soit $i=e(x-1) \geqslant 1$ : on a $x-1=2^i q$ avec $q$ impair, d'où $x+1 = 2^i q + 2 = 2(2^{i-1}q + 1)$.

Si $i>1$, $2^{i-1}q+1$ est impair, donc 2 n'apparaît qu'à la puissance 1 dans $x+1$ .
Si $i=1$, $2^{i-1}q+1=q+1$ est pair car $q$ est impair, donc 2 apparaît au moins au carré dans $x+1$.

Pour résumer : $e(x-1) > 1 \Rightarrow e(x+1)=1$ et : $e(x-1)=1 \Rightarrow e(x+1)>1$.

Donc pour vérifier (*), sachant que $e(x)=0$, il faut $e(x-1)+e(x+1) \geqslant k$, ce qui implique $k \geqslant 3$ d'après ce qui précède (car $x-1$ et $x+1$ sont supposés pairs, et on vient de montrer que si l'un est pair, l'autre admet le facteur 2 à un exposant $>1$). Ceci veut simplement dire qu'il n'existe une solution impaire non triviale que si $p \geqslant 8$, ce qu'on a déjà vu.

On a donc ou bien $e(x-1)=1$ et $e(x+1) \geqslant k-1$, ou bien la même chose en échangeant $x+1$ et $x-1$. Supposons $e(x-1)=1$ : alors il existe un entier non nul $q$ (pas forcément impair) tel que $x+1=2^{k-1}q$ ; si $q$ est pair, $2^k |x+1$ donc on retombe sur une solution triviale ; si $q$ est impair, $x+1 \equiv 2^{k-1} [2^k]$.
Symétriquement, on peut faire exactement le même raisonnement en supposant $e(x+1)=1$.
Donc $x$ ne peut être solution non triviale que si $x \pm 1 \equiv 2^{k-1}$.
Réciproquement, on a déjà montré que pour $p=2^k$, $2^{k-1} \pm 1$ sont solutions. Donc ce sont bien les seules non-triviales.

Et comme j'adore écrire ça à la fin d'une démo : CQFD :lol: (rah ça fait du bien).

Bon maintenant, plus costaud : qui pourra me trouver un critère permettant de résoudre cette équation pour n'importe quel modulo ? Si possible sans factoriser celui-ci, car les systèmes avec lesquels je travaille n'ont pas de limites dans leurs coefficients... Mais je doute que ça soit possible, étant donné qu'à un facteur près ça ressemble à de l'extraction de racine carrée modulo, et que je sais plus qui a dit que c'était équivalent du point de vue algorithmique à la factorisation ... Bref encore du pain sur la planche. Ciao !
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par balf »

Le théorème chinois permet de se ramener au cas $p^k$ en décomposant le module en produit de facteurs premiers.

B.A.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

... ah oui d'accord. J'ai mis un petit moment mais je viens de comprendre (merci au passage :wink: )

Bon donc le théorème chinois nous dit que, pour un nombre quelconque $p$ dont la décomposition s'écrit $p=\prod_i p_i^{\alpha_i}$, l'application :
$$\phi : \prod_i |[0,p_i^{\alpha_i}|[ \rightarrow |[0,p|[$$
$$(x_1,...,x_n) \mapsto \mbox{ l'unique entier } x \mbox{ solution de } \forall i, x \equiv x_i [p_i^{\alpha_i}]$$

est bijective, c'est bien ça ? (avec la précision qu'on doit prendre les facteurs premiers avec leur exposant, car les modules $m_i=p_i^{\alpha_i}$ du théorème chinois doivent être deux à deux premiers entre eux).

Donc si je poursuis le raisonnement, on a $x \equiv x^3 [p] \Leftrightarrow \forall i, x\equiv x^3 [p_i^{\alpha_i}]$ , c'est-à-dire :

$x \equiv 0, \pm 1, 2^{\alpha_i-1} \pm 1$ pour $p_i=2$ ;
$x \equiv 0, \pm 1$ pour tous les autres facteurs premiers de $p$.

Ainsi on distingue le cas où $8 | p$ et celui où $8 \nmid p$ (car si 2 fait partie des facteurs premiers de $p$ on a vu qu'il n'y a de solutions non-triviales que si 2 est à la puissance au moins 3).

$n$ étant le nombre de facteurs premiers distincts de $p$, on obtient toutes les solutions en faisant agir $\phi$ sur l'ensemble des suites $(x_1,...,x_n)$ où :

- $x_1 = 0, \pm 1, 2^{\alpha_1-1} \pm 1$ et $x_{i>1} \in \{-1,0,1\}$ si $8 | p$ , soit $3^{n-1} \times 5$ solutions distinctes ;

- $\forall i, x_i \in \{-1,0,1\}$ sinon, soit $3^n$ solutions distinctes .

J'en ai profité pour me rafraîchir la mémoire sur le théorème chinois, et j'ai réalisé que la démonstration d'existence de la solution pouvait se faire de manière constructive, c'est-à-dire qu'on peut expliciter l'application $\phi$.

En effet, soit $p = \prod_{i=1}^n p_i^{\alpha_i}$, on pose comme précédemment $m_i=p_i^{\alpha_i}$, on se donne une suite $(x_1, ..., x_n)$ où $0 \leqslant x_i < m_i$, et on cherche donc à résoudre le système de congruences $\forall i, x_i \equiv x [m_i]$.

On a $m_i$ premier avec $\frac{p}{m_i} = \prod_{j \ne i} m_j$ , donc d'après Bachet-Bézout : $\exists a_i, b_i : a_i m_i + b_i \frac{p}{m_i} = 1$ (il suffit d'appliquer l'algorithme d'Euclide étendu pour trouver $a_i,b_i$). On voit en posant $e_i = b_i \frac{p}{m_i}$ que $e_i \equiv 1 [m_i]$ et $e_i \equiv 0 [m_{j \ne i}]$ (en fait $e_i \equiv \delta_{ij} [m_j]$ ). Donc $x = x_1 e_1 + ... + x_n e_n$ est solution (pour l'unicité c'est une autre histoire, mais bon, tout le monde sait ça :P ).

Donc pour résumer : revenons au problème initial, $x^3 \equiv x [p]$ ; on factorise $p$, on applique l'algorithme d'Euclide étendu à tous les couples $m_i, \frac{p}{m_i}$ obtenus, et on en déduit les $e_i$ comme indiqué. Puis on parcourt les suites $(x_1,...,x_n)$ décrites plus haut, et on calcule $\sum_{i=1}^n x_i e_i$ , et voilà, on a toutes nos solutions (et on n'est même pas obligé de parcourir toutes les suites, vu que si on a la moitié des solutions, on a l'autre moitié, voire premier post).

Bon allez encore une petite dernière chose pour la route : il semblerait que dans tout module premier, tout nombre admet une unique racine cubique (ie que l'application $m \mapsto m^3 mod. p$ soit bijective). C'est le cas aussi dans certains modules composés, comme 15, mais pas 9, par exemple, où 8 admet pour racines cubiques 2 et 8, mais où par exemple, 3 n'en admet pas. Et quand dans un module composé l'application "cube" est bijective, il semble également que si $x^3 \equiv y$ (avec $y \ne x$) alors $y^3 \equiv x$. Je n'ai pas vérifié ces conjectures pour beaucoup de cas, mais ce sera mon prochain sujet de réflexion ... Je penche pour l'hypothèse que les modules composés qui ont cette propriété ne sont divisibles par aucun carré (donc par aucune puissance > 1 d'un nombre premier).

Ciao ! (et merci à balf)
Dernière modification par Noah le samedi 07 août 2010, 03:24, modifié 1 fois.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par balf »

Que dans $\mathbf Z/p\mathbf Z$ un élément n'ait qu'une racine cubique (si p est premier) est faux dans $\mathbf Z/7\mathbf Z$, les éléments non nuls sont ±1, ±2, ±3, et les cubes de ces éléments sont ±1.

B.A.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Ah bin oui alors ! Pourtant on le voit dès 2 :oops:

Pourtant j'ai essayé une poignée de nombres au hasard, j'ai plus le papier mais ça marche avec 15, 6, 11, 10 ... J'ai essayé de sentir un critère mais apparemment je me suis planté en beauté. Mais effectivement je n'ai pas poussé assez loin sinon j'aurais trouvé le cas du 7. Pourtant la question reste entière : qu'est-ce qui fait que ça marche avec certains nombres et pas d'autres, si ce n'est pas leur caractère premier ou composé ? Pourquoi avec 3, 6 mais pas 9 ni 12 ? Avec 2 et 5 mais pas 10 ? 11 mais pas 13 ni 7 ???

Je maintiens la deuxième conjecture : pour les moduli où ça marche, la racine cubique d'un nombre est aussi son cube (tiens ça me rappelle le principe du RSA... faudra que je regarde ça).
Dernière modification par Noah le samedi 07 août 2010, 04:00, modifié 1 fois.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Voici la liste des premiers nombres :

- modulo lesquels tout nombre admet une racine cubique :
2,3,5,6,10,11,15,17,22,23,29,30 .

- les autres :
4,7,8,9,12,13,14,16,18,19,20,21,24,25,26,27,28.

A part que les multiples des nombres de la deuxième liste semblent y être également, ainsi que les carrés (36 y est aussi), pour l'instant aucun indice...
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par balf »

Que si $x^3=y$, alors $y^3=x$ ma paraît faux en général : ça implique que $x^9=x$ et, si $x\neq 0$ que $x^8=1$. Ainsi toute racine cubique serait fatalement une racine huitième de l'unité.
Dans $\mathbf Z/11\mathbf Z$, les éléments non nuls ont une racine cubique unique, mais, p.ex. $2^3=-3$ et $-3^3=-5$. D'ailleurs les seules racines huitièèmes de l'unité sont ±1.

B.A.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Caramba je suis nul en conjectures !!

D'accord pour les racines huitièmes de l'unité à condition que $x$ soit inversible ! Bon mais sinon mea culpa, je vais arrêter de conjecturer dans le vent...

J'ai un peu rallongé la liste des moduli dans lesquels l'élévation au cube est bijective :

2,3,5,6,10,11,15,17,22,23,29,30,33,34,41,46,47,51,53,55,58,59 (et pas 60).

Effectivement ma "conjecture" $x^9=x$ ne marche parmi ces nombres que pour 2,3,5,6,10,15 et 30 (11 est effectivement le plus petit contre-exemple, où par élévations au cube successives on a des cycles du genre (3,5,4,9) et (2,8,6,7). ) Aucun autre entier jusqu'à 2^20 n'a cette propriété.
On rencontre ce genre de cycles dans 17 : (3,10,14,7),(5,6,12,11) où ils côtoient des cycles de longueur 2 : (4,13),(2,8),(9,15).
Dans 22 on n'a que des cycles de longueur 4 (sorti des solutions de $x^3=x$ ) ; dans 23, de longueur 5.
Pour 29 : 4 "pentacycles" et un cycle (12,17).
Pour 33 : 6 "tétracycles".
Pour 34 : 4 tétracycles et 6 dicycles.
Pour 41 : 8 tétracycles, 3 dicycles.
Pour 47 : 4 cycles de longueur 11 (!).
Pour 46 : 8 cycles de longueur 5.

49, qui figure dans la liste des modules où le cube n'est pas bijectif, ne contredit pas la thèse des carrés. (sans compter que 64 et 81 y figurent également).
Il semblerait que le produit de deux nombres de cette liste y soit également (mais j'ai eu la flemme de programmer donc je ne l'ai pas vérifié très loin ... donc cette fois je refuse d'appeler ça une conjecture car je sens que balf va me trouver un petit contre-exemple ^^).
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Up !! Bon alors personne pour me trouver un critère sur $p$ pour que l'application $x \mapsto x^3$ soit bijective dans $\mathbb{Z}/p \mathbb{Z}$ ? J'ai tenté quelques trucs mais je rame.

Alors déjà l'injectivité suffit, puisqu'on travaille dans des ensembles de cardinal fini, donc injectif => surjectif.

Ensuite il faut rechercher à quelle(s) condition(s) on a $x$ non congru à $y$ et $x^3 \equiv y^3$ .
En particulier, $x \ne y$ donc $x^3 \ne y^3$ : ainsi, si on a $x^3 \equiv y^3$ , alors c'est que $x^3 - y^3$ est un multiple non nul de $p$ .

Ainsi, si $p$ se décompose en $\prod_{i=1}^n p_i^{\alpha_i}$, alors (en reprenant la notation $e_i(x)$ pour l'exposant du facteur premier $p_i$ dans l'écriture de $x$ ) :

$$x^3 \equiv y^3 \Leftrightarrow \forall \mbox{ }1 \leqslant i \leqslant n , e_i(x-y) + e_i(x^2 + xy + y^2) \geqslant \alpha_i$$
En sachant que comme $x-y$ n'est pas multiple de $p$ :

$$\exists \mbox{ } i_0 : e_{i_0}(x-y) < \alpha_{i_0}$$
C'est-à-dire que pour qu'on ait $x^3 \equiv y^3$ il doit nécessairement exister un facteur premier $p_{i_0}$ commun à $p$ et à $x^2 + xy + y^2$ , dont l'exposant dans cette dernière expression doit être supérieur ou égal à $\alpha_{i_0} - e_{i_0}(x-y)$ (mais ce n'est pas une condition suffisante). En tout cas, il est clair que si $p$ et $x^2 + xy + y^2$ sont premiers entre eux, on aura $x^3$ et $y^3$ non congrus.

Une des pistes que j'ai suivies mais pas encore jusqu'au bout est d'écrire cette relation sous la forme $\exists a,b : ap + b(x^2+xy+y^2) = 1$, mais ça devient vite très calculatoire, et en plus on ne sait pas si c'est la seule manière d'avoir le cube bijectif.

Il s'agit donc d'étudier les congruences $(x-y)(x^2 + xy + y^2) \equiv 0 [p_i^{\alpha_i}]$ en sachant que $x-y$ est non-congru à 0 modulo au moins un des $p_i^{\alpha_i}$ .

Si $p$ est un carré : prenons $x = a \sqrt{p}$ et $y = b \sqrt{p}$ de façon que $|a-b| < \sqrt{p}$ , par exemple, $a = 0$ et $b = 1$ : alors $x - y$ ne sera pas congru à 0 modulo $p$, mais on aura $x^3 - y^3 = - p \sqrt{p}$ , c-à-d $x^3 \equiv y^3$ . Et voilà pourquoi le cube n'est jamais bijectif modulo un carré parfait ! Bon, ça fait un peu avancer le schmilblick, mais pas des masses non plus.

Si $p$ est premier, on est ramené à l'étude de $x^2 + xy + y^2 \equiv 0$, soit en posant $X = x+y$ et $Y = x-y \ne 0$ (et en se limitant, sans perte de généralité, au cas $p > 0$ ) :

$$x^3 \equiv y^3 \Leftrightarrow \exists k \in \mathbb{N}^* : 3 X^2 + Y^2 = 4kp$$
(en effet, $x^2 + xy + y^2 = kp > 0$ est l'équation de l'ellipse centrée sur l'origine, de demi-axes de longueurs $2/\sqrt{kp}$ et $2 / \sqrt{3kp}$ et tournée de $\pi/4$ , et $k$ ne peut être nul que si $X=Y=0$ ce qui est contre l'hypothèse).

On peut prendre X et Y comme nouvelles variables, en leur imposant la même parité, puisqu'il est alors clair qu'à chaque couple $(X,Y)$ de $(\mathbb{Z} / p \mathbb{Z})^2$ vérifiant cette condition, on peut associer $(x,y)$ tel que $X = x+y$ et $Y = x-y$, et réciproquement. La non-nullité de $x-y$ modulo $p$ se traduit alors simplement par la non-nullité de $X$ et de $Y$ modulo $p$ (car si $p \nmid x-y$ alors $p \nmid x+y$ ).

Pour résumer, si $p$ est premier, alors le cube n'est pas bijectif dans $\mathbb{Z} / p \mathbb{Z}$ si et seulement si on peut trouver $m$ et $n$ tels que :
- $2m$ et $2n$ non-multiples de $p$ et $3m^2+n^2 \equiv 0$ ;
- ou $2m+1$ et $2n+1$ non-multiples de $p$ et $3m(m+1)+n(n+1)+1 \equiv 0$ .

Bon voilà l'état actuel de mes recherches, et j'ai bien peur que ceci sorte du domaine des preuves "élémentaires" en théorie des nombres, notamment qu'il faille se servir de la théorie des courbes elliptiques ou je ne sais quoi pour s'en tirer... Je n'ai pas non plus réfléchi sur la conjecture "le cube n'est pas bijectif modulo le produit de deux nombres où il n'est pas bijectif" .
Dernière modification par Noah le mardi 10 août 2010, 14:53, modifié 1 fois.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

En progrès ... Désolé pour le côté brouillon du dernier mail, je n'ai fait que recopier mes brouillons .

Dans l'idée du théorème chinois, on a :

$$x \mapsto x^3 \mbox { bij. dans } \mathbb{Z}/p\mathbb{Z} \Leftrightarrow \mbox{ bij. dans chaque } \mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}$$

(où "bijectif" peut indifféremment être remplacé par "surjectif" ou "injectif", les trois termes étant ici équivalents) .

Dans $\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}$ où $\alpha_i \geqslant 1$ , prenons $x=0$ et $y=p_i^{\alpha_i - 1}$ : on a $x^3 - y^3 = - p_i^{3(\alpha_i-1)}$ . Or pour $\alpha_i > 1$ , on a $3(\alpha_i - 1) > \alpha_i$ donc $x^3 \equiv y^3 [p_i^{\alpha_i}]$ alors que $x$ et $y$ ne sont pas congrus .

Donc dans tout module divisible par un carré il n'y a pas bijectivité du cube .

On voit également par le théorème chinois, pourquoi le produit de modules où le cube n'est pas bijectif ne l'est pas non plus, et l'on voit même que le cube n'est pas bijectif dans tout multiple d'un nombre où il ne l'est pas .
On voit également que le cube est bijectif modulo le produit de nombres premiers distincts où il l'est (ces nombres étant tous pris à l'exposant 1).

Il reste donc seulement à étudier la bijectivité dans un module premier.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Bon bah ça a pas l'air de vous stimuler des masses dites moi.

Nouvelle hypothèse de travail :

- le cube est bijectif dans les nombres premiers de la forme 6k-1 (en plus de 2 et 3) ;
- il est non-bijectif dans ceux de la forme 6k+1 .

(en sachant que tous les nombres premiers sont d'une de ces deux formes ...)

PS : j'ai saboté mon fil, je pense que je vais en ouvrir un nouveau pour exprimer en deux lignes mon énigme, parce que là ça devient imbitable pour les rares qui passeraient par là ... Les modos en pensent quoi ?
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par balf »

La réponse est en liaison avec le problème des racines de l'unité dans un corps fini. Je renvoie p.ex. à ce document :
http://www-groups.mcs.st-and.ac.uk/~neu ... fchap4.pdf
L'outil est le théorème 8.2 , d'où il ressort (avec n=3) que,si p $\neq$ 3, il y a 3 racines cubiques de l'unité, et donc tout élément qui a une racine cubique en a 3. Ce n'est donc certainement pas bijectif. En fait, les élémentnon nuls qui sont des cubes forment un sous-groupe d'indice 3 du groupe multiplicatif des éléments non nuls du corps.Si p=3, il n'y a qu'une racine cubique de l'unité, qui est racine triple du polynôme $X^3-1$, et c'est bijectif.

Bon, d'accord, c'est un peu le pavé de l'ours pour écraser une mouche...

B.A.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Merci pour cet intéressant document.

Etant données mes lacunes théoriques en la matière, je ne suis pas sûr de saisir toutes les implications du sujet. Mais si il est vrai que la caractéristique de $\mathbb{Z}/p\mathbb{Z}$ est l'entier $p$, si je comprends bien la notion de groupe cyclique d'ordre n - ce qui est loin d'être sûr - , est-ce à dire que l'unité possède trois racines cubiques dès lors que $p>3$ ? Car 11 est un contre-exemple ... Donc quelque chose doit m'échapper, et je serais reconnaissant qu'on puisse m'éclairer sur le sujet ...

J'ai testé jusqu'à $k = 10000$ que l'unité ne possède qu'une racine cubique dans les premiers de la forme $6k-1$ , et trois dans ceux de la forme $6k+1$, grâce au programme maple suivant :

Code : Tout sélectionner

myconj := proc()
local flag1, flag5, i, j;
    flag1 := 0;
    flag5 := 0;
    for i to 10000 do
        j := 6*i - 1;
        if isprime(j) then
            if ArrayTools:-Size(Roots(x^3 - 1) mod j, 2) <> 2
            then flag5 := 1
            end if
        end if;
        j := j + 2;
        if isprime(j) then
            if ArrayTools:-Size(Roots(x^3 - 1) mod j, 2) <> 6
            then flag1 := 1
            end if
        end if
    end do;
    [flag1, flag5]
end proc
(l'instruction Roots(x^3-1) mod j , qui calcule les racines de l'unité modulo j, renvoie une matrice de 2m éléments lorsqu'il y a m solutions distinctes).

La procédure renvoie flag1 = 0 , et flag5 = 0 .
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par balf »

Autant pour moi : j'avais oublié qu'il s'agissait du corps premier $\mathbf Z/p\mathbf Z$, et nondu corps engendré sur celui-ci par les racines cubiques de l'unité. Donc, en réalité, il faut tester selon les valeurs de p si le polynôme X²+X+1 est irréductible ou pas. Je ne sais pas, ex abrupto s'il y a une réponse générale.
Ce qui est sûr, c'est que les racines de l'unité forment un sous-groupe du groupe multiplicatif $\mathbf Z/p\mathbf Z^\times$, qui est d'ordre p-1. S'il y a trois racines cubiques, le théorème de Lagrange entraîne que p-1 est divisible par 3, et si p est impair, on en déduit en effet que nécessairement $p\equiv 1\mod6}$.

B.A.
MC
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 399
Inscription : jeudi 24 avril 2008, 16:59

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par MC »

Effectivement, l'irréductibilité de $X^2+X+1$ sur $\Z/p\Z$ est équivalente au fait que $p$ est irrédutible dans l'anneau des entiers d'Eisenstein $\Z[j]=\Z[X]/(X^2+X+1)$.
Il est connu que les premiers $p$ congrus à 2 modulo 3 sont ceux qui sont irréductibles dans $\Z[j]$.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par balf »

En effet, mais je me demandais s'il existe une démonstration élémentaire, je veux dire sans utiliser la loi de réciprocité quadratique ?

B.A.
MC
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 399
Inscription : jeudi 24 avril 2008, 16:59

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par MC »

Qui a parlé de réciprocité quadratique? Il n'y en a pas là-dedans.

Si la question est de déterminer les premiers $p$ pour lesquels l'application $x\mapsto x^3$ est une bijection de $\Z/p\Z$ sur lui-même, la réponse est très facile si on sait que le groupe multiplicatif du corps $\Z/p\Z$ est cyclique, d'ordre $p-1$ forcément. L'élévation au cube est une bijection si et seulement si 3 est premier avec $p-1$, c.-à-d. si et seulement si $p$ n'est pas congru à 1 modulo 3.
Noah

Re: Raisonnement sur les congruences : conjecture à démontrer ?

Message non lu par Noah »

Bon et bien que dire sinon merci de vos réponses...