Recherche d'unités

stfj

Bonjour

Je cherche, dans $\Z/210\Z$, des unités $u$ telles que $u+6$ soit une unité, mais pas $u^{-1}+6$.  Ce problème est motivé par un de mes posts récents ici.

J'ai essayé $41$ mais $41^{-1}=41$. J'ai essayé $73$ mais $73^{-1}=187$. J'ai essayé $163$ mais $163^{-1}=67$. Et je viens d'essayer $137$ mais $137^{-1}=23$. Je ne vois nulle raison pour laquelle $u+6\in (\Z/210)^\times\implies u^{-1}+6\in (\Z/210)^\times$.

Cordialement,
Stéphane.

bisam

Une petite expérimentation en Python montre que les seules unités $u$ de $\Z/210\Z$ qui ne vérifient pas que $u+6$ est une unité sont les idempotentes... Par conséquent, ta recherche est vouée à l'échec.

Je ne sais pas le prouver arithmétiquement (à vrai dire, je n'ai pas cherché), mais la recherche exhaustive est une forme de preuve, même si elle est assistée par ordinateur.

stfj

@bisam : Peux-tu voir dans $\Z/2310$ le même problème ? J'ai commencé d'étudier et je n'en trouve pas non plus .

NicoLeProf

stfj a dit :

Je ne vois nulle raison pour laquelle $u+6\in (\Z/210)^\times\implies u^{-1}+6\in (\Z/210)^\times$.

Bonjour à toi,

je crois que c'est vrai pour ce groupe . En effet, il me semble qu'un élément de $(\mathbb{Z}/210\mathbb{Z})^{\times}$ doit être premier avec $210$ donc ne doit avoir aucun des facteurs premiers de $210=2 \times 3 \times 5 \times 7$ .

Ainsi, un élément de $(\mathbb{Z}/210\mathbb{Z})^{\times}$ est premier soit il n'est pas premier et dans ce cas, le facteur premier le plus petit possible de cet élément est $11$ .

Dans le cas où l'élément considéré $a$ n'est pas premier, cet élément possède deux facteurs premiers $p$ et $q$ éventuellement égaux.

On écrit : $a=pq$ et $p$ et $q$ vérifient : $p \geq 11$ et $q \geq 11$ mais $pq \leq 210$ donc $q \leq \dfrac{210}{p}$ ainsi, $q \leq \dfrac{210}{11}$ et il en est de même pour $p$ .

Je trouve donc comme possibilités lorsque l'élément du groupe n'est pas premier : $11 \times 11=121$ ; $11 \times 13 = 143$ ; $13 \times 13 = 169$ ; $11 \times 17=187$ et $11 \times 19=209$ .

Voici ce que j'ai fait en y réfléchissant davantage :

pour $u \in \{121 ; 143 ; 187\}$, on a bien : $u+6$ et $u^{-1}+6$ inversibles.

Pour $u \in \{169 ; 209\}$, $u+6$ n'est pas inversible dans le groupe considéré.

Si $u$ est premier alors pour que $u+6$ soit inversible, $u+6$ est premier ou $u+6 \in \{121 ; 143 ; 169 ; 187 ; 209 \}$ soit $u \in \{137 ; 163 ; 181 \}$ (en éliminant les cas où $u+6=121$ et $u+6=209$ car $u$ est inversible. Peut-être que cela aiderait à conclure par des disjonctions de cas . C'est tout de même pas complètement clair... Je vais encore y réfléchir.

raoul.S

Pour $\Z/210\Z$ on peut le montrer avec le th. des restes chinois. On a $\Z/210\Z\simeq \Z/6\Z\times \Z/35\Z$. Par conséquent il suffit de vérifier l'affirmation dans $\Z/6\Z$ et dans $ \Z/35\Z$.

- Dans $\Z/6\Z$ c'est évident car si $u$ et $u+6$ sont dans $\Z/6\Z^{\times}$ alors $u^{-1}+6=u^{-1}$ l'est également.

- Dans $\Z/35\Z$ on a $6=6^{-1}$ de sorte que $(6u+1)6=u+6$ donc si $u+6$ et $u$ sont inversibles, $u^{-1}+6$ aussi car $u^{-1}+6=u^{-1}(1+6u)$ est produit d'inversibles.

bisam

Dans $\Z/2310\Z$, on trouve $30$ valeurs de $u$ qui conviennent : \[31, 53, 97, 163, 251, 317, 361, 383, 493, 647, 691, 713, 823, 977, 1021, 1087, 1153,\\ 1241, 1307, 1417, 1483, 1571, 1637, 1703, 1747, 1901, 2011, 2033, 2077, 2231\]

stfj

@bisam : merci . Je viens de tester à la main $31$ : $31^{-1}=2161$ et $2167=0[11]$.

@raoul.S, @NicoLeProf : merci.

NicoLeProf

Pour $\Z/2310\Z$, je m'empare de la preuve de raoul.S que je trouve géniale ! On a $\Z/2310\Z\simeq \Z/6\Z\times \Z/35\Z \times \Z/11\Z $. Sauf qu'ici, dans $\Z/11\Z$, le problème est que si $u=9$ (inversible d'inverse $5$ dans $\Z/11\Z$ ) alors $u+6=15$ (inversible) mais $5+6=11$ n'est pas inversible !

Donc on peut trouver un élément $u$ de $\Z/2310\Z$ vérifiant $u$ inversible, $u+6$ inversible et $u^{-1}+6$ non inversible . Il suffit de trouver un $u$ congru à $9$ modulo $11$ .

Prenons $u=53 \equiv 9 \pmod{11}$ . Dans $\Z/2310\Z$, $53$ est inversible d'inverse $1787$ et $53+6=59$ est inversible également mais $1787+6=1793$ n'est pas inversible dans $\Z/2310\Z$ car $1793 \equiv 0 \pmod {11}$ .

D'ailleurs, je pense que le programme informatique de Bisam a permis de trouver tous les éléments $u$ de $\Z/2310\Z$ congrus à $9$ modulo $11$ donc tels que $u$ inversible, $u+6$ inversible mais $u^{-1}+6$ non inversible.

bisam

Mon "programme" est juste une utilisation de l'algorithme d'Euclide étendu pour calculer les inverses et des facilités de Python.

def gcd(a: int, b: int) -> int:
    """Renvoie le pgcd de a et b"""
    while b:
       a, b = b, a % b
    return a

def inverse(a: int, b: int) -> int:
    """Renvoie l'inverse de a modulo b si a et b sont premiers entre eux"""
    u0, v0, u1, v1 = 1, 0, 0, 1
    while b:
        a, (q, b) = b, divmod(a, b)
        u0, v0, u1, v1 = u1, v1, u0 - q * u1, v0 - q * v1
    return u0

def all_unites(n: int) -> set[int]:
    """Renvoie l'ensemble des unités de Z/nZ"""
    return {u for u in range(n) if gcd(u,n) == 1}

def candidats(n: int) -> list[int]:
    """Renvoie la liste des unités u de Z/nZ
    telles que u+6 est une unité mais pas u^-1+6"""
    unites = all_unites(n)
    return [u for u in unites if (u+6)%n in unites and (inverse(u,n) + 6)%n not in unites]