Contre-exemple à trouver

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.
DUET
Utilisateur confirmé
Utilisateur confirmé
Messages : 64
Inscription : mercredi 01 juin 2005, 08:14

Contre-exemple à trouver

Message non lu par DUET »

Bonjour à tous,
En m'amusant avec les nombres entiers de Gauss, je suis tombé sur une propriété qui est vraie pour tous les nombres testés jusqu'à au moins 10000 et qui semble pourtant trop simple pour être toujours vraie :

conjecture : $\forall p \in \N-\{0,1,2\} ,(1+2i)^p \equiv 1-2i [p] \Leftrightarrow p {\rm \; premier} \wedge \exists k \in \N ,p=4k+3$

$1+2i$, avec son conjugué, n'est pas spécifique dans la conjecture, qui marche aussi pour $1+3i$ avec son conjugué, mais c'est le plus simple que j'ai trouvé (la conjecture est facilement réfutable en prenant un entier, $4^{15} \equiv 4 [15]$, ou un imginaire pur et ne marche pas pour $1+i$.)

L'arithmétique modulaire reste à préciser : la division euclidienne existe avec les entiers de Gauss mais n'est pas unique pour un couple (dividende, diviseur) choisi (selon le couple, on peut avoir 2,3 ou 4 égalités possibles.) La conjecture enoncée fait l'hypothèse que le reste choisi est celui de norme (au sens des entiers de Gauss) minimale.

Par exemple, en admettant la conjecture, pour montrer que $p=3$ est un nombre premier
  • 1) on cherche le représentant de $a+ib=1-2i$ dans $\Z i /3 \Z i$:
    • a) dans $\Z$, $a=1=3q+r \Rightarrow (q,r) = (0,1)$
      b) dans $\Z$, $b=-2=3 \tilde{q} + \tilde{r}\Rightarrow ( \tilde{q}, \tilde{r}) = (-1,1)$ (résultat de divMod et non pas celui de quotRem qui retourne (0,-2) en Haskell)
      c) dans $\Z i/p \Z i$ avec $p$ entier (classique) positif comme c'est le cas ici, le reste minimum est donné par
      $a+ib-p(q+i \tilde{q})$ si $-p=\min (-p,-2r,-2 \tilde{r},p-2(r+ \tilde{r}))$
      $a+ib-p(q+1+i \tilde{q})$ si $-2r=\min (-p,-2r,-2 \tilde{r},p-2(r+ \tilde{r}))$
      $a+ib-p(q+i \tilde{q}+i)$ si $-2 \tilde{r}=\min (-p,-2r,-2 \tilde{r},p-2(r+ \tilde{r}))$
      $a+ib-p(q+1+i \tilde{q}+i)$ si $p-2(r+ \tilde{r})=\min (-p,-2r,-2 \tilde{r},p-2(r+ \tilde{r}))$
      Donc ici comme $-3=\min(-3,-2,-2,-1)$, on a $1-2i \equiv 1-2i -3(0-i)\equiv 1+i [3]$
    2) on cherche le représentant de $a+ib=(1+2i)^3=-11-2i$ dans $\Z i /3 \Z i$:
    • a) $(q,r)=(-4,1)$
      b) $( \tilde{q}, \tilde{r})=(-1,1)$
      c) $-3=\min(-3,-2,-2,-1)\Rightarrow (1+2i)^3 \equiv -11-2i-3(-4-i)\equiv 1+i [3]$
    3) on conclut que $p=3$ est premier car $p=4*0+3$ et que $(1+2i)^3 \equiv 1-2i [3]$
On peut également, d'après cette conjecture, montrer que $p=15$ n'est pas premier car $p=4*3+3$ alors que la congruence n'est pas vérifiée.

Connaissez-vous un contre-exemple dans un sens ou dans l'autre ou bien des références sur le sujet ?

PS J'aurais aimé mettre des crochets autour du $i$ des $\Z i$ comme c'est l'usage pour les entiers de Gauss mais je me heurte à un problème de conversion en balise italique qui a le même code.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Contre-exemple à trouver

Message non lu par balf »

La conjecture me paraît juste, pour une raison assez simple : si un nombre premier p de Z est congru à 3 modulo 4, il est inerte dans Z, c-à-d qu'il reste premier dans cet anneau Mais alors l'élévation à la puissance p est un morphisme d'anneau de Z dans lui-même (morphisme de Frobenius).Cela entraîne que, modulo p, on a
$(1+2i)^p =1^p+2^p i^p=1-2^pi$, puisque $i^p=-i$ si $p\equiv 3 \mod 4$. D'autre part, petit Fermat dit que $a^p\equiv a \mod p$. D'où le résultat.

B.A.
DUET
Utilisateur confirmé
Utilisateur confirmé
Messages : 64
Inscription : mercredi 01 juin 2005, 08:14

Re: Contre-exemple à trouver

Message non lu par DUET »

merci de ta réponse.
J'ai le sentiment que tu ne traites que de la partie directe de la conjecture.
Que penses-tu de la partie réciproque ? Est-ce implicite dans ta réponse ?
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Contre-exemple à trouver

Message non lu par balf »

À vrai dire, je n'ai pas pris le temps de réfléchir à la réciproque, j'ai juste jeté quelques remarques qui me paraissaient aller de soi.
Pour cette réciproque, il y a plusieurs points : il faudrait d'abord traiter le cas p premier. On pourrait procéder par contraposition. Si p est congru à 1 mod. 4, il est totalement décomposé, c.-à-d. qu'il est le produit de deux éléments irréductibles (et conjugués) de Z, q et r. La cngruence mod. p équivaut, par le théorème chinois aux deux congruences simultanées, mod. q et mod. r. On pourrait chercher à vérifier qu'une de ces congruences n'est pas vérifiée.

B.A.
DUET
Utilisateur confirmé
Utilisateur confirmé
Messages : 64
Inscription : mercredi 01 juin 2005, 08:14

Re: Contre-exemple à trouver

Message non lu par DUET »

Bon, j'ai le cas $p$ premier, je crois.
Je n'ai pas utilisé les restes chinois car le $q$ et le $r$ dont tu parles ne sont pas entiers classiques et j'ai préféré une solution plus simple:

Supposons donc que $p$ est premier, qu'il est de la forme $4k+1$ et que $(1+2i)^p \equiv 1-2i\mod p$, et cherchons la contradiction.
On généralise tout d'abord en disant qu'on est dans un cas particulier de $(a+ib)^p \equiv a-ib \mod p$ c'est-à-dire qu'on admet qu'$\exists (x,y), (a+ib)(x+iy)\equiv a-ib \mod p$.
Cette hypothèse mène au système $\left\{\begin{matrix}ax-by\equiv a \mod p\\ay+bx\equiv -b \mod p\end{matrix}\right.$ qui a pour conséquence que $-y(a^2+b^2)\equiv 2ab \mod p$.
L'existence d'$y$ dépend donc de l'inversion de $a^2+b^2$ :
$\exists z, (a^2+b^2)z\equiv 1 \mod p$
$\exists z(\forall t,(a^2+b^2)z+pt=1)$ qui n'est possible que si PGCD($p , a^2 + b^2$)$=1$. Dans notre cas $a^2+b^2=5$ donc il y a contradiction car $p$ peut par hypothèse être égal à n'importe quel élément premier de $\{4k+1,k\in \N\}$ notamment 5.

Conclusion : si $(1+2i)^p \equiv 1-2i\mod p$ et que $p$ est premier, alors $\exists k\in \N, p=4k+3$.

Cette démonstration montre aussi que l'implication peut être étendue à n'importe quel couple $(a,b)$ tel que $a^2+b^2$ soit premier sauf 2 car $\{2\} \cup\{4k+1 / k\in \N, 4k+1{\rm \; premier}\}=\{a^2+b^2 / (a,b) \in \N^2, a^2+b^2{\rm \; premier}\}$. Le couple $(1,1)$ est embêtant car, $(1+i)^2 \equiv 0 \mod 2$.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4053
Inscription : mercredi 02 janvier 2008, 23:18

Re: Contre-exemple à trouver

Message non lu par balf »

Ça marche, mais je trouve que c'est très calculatoire. je propose d'utiliser avant tout calcul le fait que, si p est un nombre premier, $(a+b)^p\equiv a^p+b^p \mod p$, dans n'importe quel anneau d'entiers algébriques. En particulier $(1+2\mathrm i)^p\equiv 1+2^p \mathrm i^p$. Si c'est aussi congru à $1-2\mathrm i$, on a donc $2^p\mathrm i^p\equiv -2\mathrm i$.
D'autre part, si p est premier, $2^p\equiv 2$. De plus, si p est impair, 2 est inversible modulo p. En fin de compte, on obtient $\mathrm i^p\equiv -\mathrm i$, d'où nécessairement $p\equiv 3\mod 4$. Si p=2, la congruence est trivialement vérifiée.

B.A.