¿Cuál es el orden multiplicativo de un producto de dos enteros$\mod n$?

Question

Textos estándar demostrar que $\textrm{ord}_n(ab)=\textrm{ord}_n(a)\,\textrm{ord}_n(b)$ al $\textrm{gcd}(\textrm{ord}_n(a),\textrm{ord}_n(b))=1$. Lo que si que no son relativamente primos? Aquí $\textrm{ord}_n(b)$ es la multiplicación de la orden de $b$, es decir, el menor entero positivo $m$ tal que $b^m=1 (\textrm{mod}\,n)$.

La ingenua suposición de que $\textrm{ord}_n(ab)$ $\textrm{lcm}(\textrm{ord}_n(a),\textrm{ord}_n(b))$ no puede ser correcta, ya que le da $\textrm{ord}_n(b^k)=\textrm{ord}_n(b)$, mientras que en realidad $\textrm{ord}_n(b^k)=\frac{\textrm{ord}_n(b)}{\textrm{gcd}(\textrm{ord}_n(b),k)}$. De modo que el orden de los productos debe depender más que de las órdenes de los factores, tal vez algo en su primer factorizations?

¿Qué dependerá exactamente? Existe una formula para el caso general? Si no, hay fórmulas para algunos casos especiales, por ejemplo, cuando se $a,b$ son relativamente primos, plaza libre, el primer poderes, al $n$ es primo, etc.? Existen útil límites? Ya que el producto de los pedidos es siempre un límite superior límite inferior sería interesante. Referencias apreciado.

Answer 1

Esta es una respuesta larga, así que siéntase libre para saltar a la fórmula. $\def\ord{\text{ord}}\def\div{\text{ divides }}\def\v#1#2{v_{#1}(#2)}$

---

Deje $G$ ser un grupo abelian con dos elementos $a,b$. Supongamos $a$ orden $m$ $b$ orden $n$. Denotar $l=\text{lcm}(m,n)$$g=\text{gcd}(m,n)$. También se definen $H=\langle a\rangle,K=\langle b\rangle$$s=|H\cap K|$.

Nuestro objetivo es determinar el orden de $ab$.

Desde $H\cap K$ es un subgrupo de $H$ $H$ es cíclica, sabemos $H\cap K$ debe ser generado por $a^{m/s}$. Del mismo modo $H\cap K$ es generado por $b^{n/s}$. Por lo tanto, hay algunos $k_0$, que es relativamente primer a $s$ tal que $a^{m/s}=b^{nk_0/s}$.

---

Lema. $$\frac ls\div\ord(ab)\div l.$$

Prueba.

Deje $x=\ord(ab)$. Desde $(ab)^x=e$, vemos $a^x\in H\cap K=\langle a^{m/s}\rangle$, lo $m/s\mid x$, es decir,$m\mid xs$. Del mismo modo, $n\mid xs$. Por lo tanto $l\mid xs$, es decir, $l/s\mid\ord(ab)$.

También, $(ab)^l=e$, lo $\ord(ab)\mid l$.

---

Teorema. $$\ord(ab)=\frac l{\gcd(s,\frac{m+nk_0}g)}.$$

Prueba.

Desde el anterior lema sabemos $\ord(ab)=lk/s$ algunos $k$.

Ahora consideremos $(ab)^{lk/s}=e$. $$ \eqalign{ (ab)^{lc/s}&=(a^{m/s})^{lc/m}b^{lc/s}\cr y=(b^{nk_0/s})^{lc/m}b^{lc/s}\cr y=b^{lc/s(1+nk_0/m)}\cr y=b^{lc(m+nk_0)/ms} } $$ Por lo $(ab)^{lk/s}=e$ es equivalente a $n\mid lk(m+nk_0)/ms$, es decir,$mns\mid lk(m+nk_0)$.

Tenga en cuenta que $mns=lgs$, por lo que es más equivalente con $s$ dividiendo $k(m+nk_0)/g$.

Deje $g_1=\gcd(s,\frac{m+nk_0}g)$. Entonces es equivalente con $s/g_1$ dividiendo $k\frac{m+nk_0}{g}/g_1$. Pero sabemos $s/g_1$ $\frac{m+nk_0}{g}/g_1$ son relativamente primos, así que esto es equivalente con $s/g_1$ dividiendo $k$, es decir, al menos tal $k$$s/g_1$.

Por lo tanto, $\ord(ab)=lk/s=\frac{l(s/g_1)}s=\frac l{g_1}$ como se desee.

---

A partir de esta fórmula podemos obtener una condición necesaria y suficiente para $\ord(ab)=l$: $\gcd(s,\frac{m+nk_0}g)=1$. No trivial caso especial es cuando, para cada divisor primo $p$ de $s$, $p$ no divide $\frac{m+nk_0}g$, por ejemplo, cuando se $p$ divide $m$ $n$ a diferentes grados.

---

Espero que esto ayude.

Answer 2

Tenga en cuenta el caso extremo$b \equiv 1/a \mod n$, donde$\text{ord}_n(a) = \text{ord}_n(b)$ pero$\text{ord}_n(ab) = 1$.

Lo que es cierto es que$\text{ord}_n(ab) \mid \text{lcm}(\text{ord}_n(a), \text{ord}_n(b))$, ya que si$\text{ord}_n(a) | m$ y$\text{ord}_n(b) | m$ entonces$(ab)^n = a^n b^n \equiv 1 \mod n$.

Además, usando$a = b^{-1} (ab)$ obtenemos$\text{ord}_n(a) \mid \text{lcm}(\text{ord}_n(b), \text{ord}_n(ab))$, y de manera similar$\text{ord}_n(b) \mid \text{lcm}(\text{ord}_n(a), \text{ord}_n(ab))$. Por lo tanto, si para algún primer$p$% y un entero positivo$k$,$p^k$ divide$\text{ord}_n(a)$ pero no$\text{ord}_n(b)$, debemos tener$p^k | \text{ord}_n(ab)$.