Producto de primer poderes igual a $1$ en el anillo de los enteros modulo $2^{127}$

Question

Estoy trabajando con el multiplicativo anillo de los enteros modulo $2^{127}$.

Consideremos el conjunto a $E=\{(k,l) \mid 5^k \cdot 3^l \equiv 1\mod 2^{127}, k > 0, l> 0\}$. Me pregunto si alguien sabe o tiene una idea de dónde buscar un resultado relacionado con un límite inferior de $M=\min\{k+l \mid (k,l)\in E \}$.

Tenemos que $0<M\leq \mathrm{ord}_{\mathbb{Z}_{2^{127}}}(5)+\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(3)$ donde $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(5)=2^{125}$ $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(3)=2^{125}$ (órdenes de estos números primos en la multiplicativo anillo de $\mathbb{Z}_{2^{127}}$).

También me gustaría generalizar el anterior para otros primos de 5 y 3.

Hay un resultado en una mayor límite inferior de $M$?

Answer 1

Deje $k=l=n$, de modo que $5^k3^l=15^n=(16-1)^n=(2^4-1)^n$. Ahora tome $n=2^{123}$ y aplicar el teorema del binomio, el cual da a todos, pero los dos últimos términos claramente divisible por $2^{127}$ y los dos últimos términos son $$-2^{123}\cdot 2^4 +1,$$ que es $1$ mod $2^{127}.$ Así que aquí $k+l=2^{124},$ que es un cuarto del valor ord(3)+ord(5).

Tal vez un menor valor puede ser obtenido en el uso de otros imponen las relaciones entre los exponentes $k,l.$

Answer 2

Reclamo:

Deje $c=40647290924413185736448652556727923386$, entonces el conjunto de solucioneses dada por $$A = \{(k,l) \(\Bbb Z/2^{126} \Bbb Z)^2 \mid 5^3^l \equiv 1\bmod 2^{127}\}= \{(cn, 2 n) \mediados n \in \Bbb Z\}$$

Esto da una fórmula explícita para todas las soluciones de $0\leq l+k < 2^{126}$, es decir,$$l+k = (2n \bmod 2^{126})+(cn \bmod 2^{126})$$ with $0< n<2^{125}$. Me resulta difícil calcular el mínimo de la expresión.

Razón:

El conjunto $A = \{(k,l) \mid 5^k3^l \equiv 1\bmod 2^{127}\}$ puede ser interpretado como un subespacio de $(\Bbb Z/2^{126} \Bbb Z)^2$. Sólo necesitamos encontrar un generador de que el subespacio para dar una caracterización explícita de $A$.

Esto es difícil en general, pero en el caso de que el módulo $2^{n}$ podemos hacer lo siguiente: Dado $k,l \in \Bbb Z/ 2^{n-1} \Bbb Z$ tal que $5^k3^l \equiv 1 \bmod 2^{n}$ también sabemos que $5^k3^l \equiv 1 \bmod 2^{n-1}$. A la inversa, dada una solución a la segunda ecuación, podemos tratar de levantar $(k,l)$$ \Bbb Z/ 2^{n-2} \Bbb Z$$ \Bbb Z/ 2^{n-1} \Bbb Z$.

Ahora por consideración a $\bmod \,2^3$ es evidente que tanto la $k$ $l$ son incluso. Por lo tanto, podemos levantar una solución de $5^k3^2 \bmod 2^3$ (mi pequeño código en python hizo que casi al instante) para encontrar que $$5^{c}3^2\equiv 1 \bmod 2^{127}$$ which is of order $2^{125}$ in $\Bbb Z/2^{126} \Bbb Z$ and therefore a generator of $$.

---

EDIT: se puede usar fracciones continuas de $c/2^{m}$ para obtener pequeños los valores de $(cn \bmod 2^{m})$ y por lo tanto también de $l+k$. El más bajo que he encontrado hasta ahora es de $$\begin{eqnarray} l&=&11726533429350798020\\ k&=&\;\,\;\;391079140617450804\\l+k&=&12117612569968248824<\sqrt{2^{127}}<2^{64}. \end{eqnarray}$$

Answer 3

A mi carne 'paradoja de cumpleaños' heurística de un comentario en al menos una respuesta parcial:

El concepto central es que entre los primeros a $m$ valores de $5^k$ y el primer $n$ valores de$3^{-l}$, $mn$ diferentes posibles colisiones, y si el tratamiento de estas interacciones como eventos independientes, entonces deberíamos esperar que cada uno de ellos para producir una verdadera colisión con probabilidad $2^{-127}$; esto significa que dentro de aproximadamente $2^{127}$ posibles colisiones debemos esperar que un choque. Desde $m+n$ es mínimo para un valor dado de a $mn$ al $m=n$, entonces deberíamos esperar que el valor mínimo de $m+n$ a ocurrir donde $m\approx n$. Conectando a $mn\approx 2^{127}$ rendimientos $m\approx n\approx 2^{64}$ $m+n\approx 2^{65}$ (hasta relativamente pequeño de factores constantes).

Por supuesto, este es un argumento heurístico, no un exacto; pero en la medida en $m\gg \log_5 2^{127}\approx 55$$n\gg\log_3 2^{127}\approx 80$, entonces yo esperaría que los conjuntos de $\{5^k\ |\ 0\leq k\lt m\}$ $\{3^{-l}\ |\ 0\leq l\lt n\}$ aproximadamente equidistributed mod $2^{127}$; ya que los números de los que estamos hablando son muchos órdenes de magnitud más grandes que esta hipótesis parece razonable.

Tenga en cuenta que si el objetivo de minimizar $|k|+|l|$, a continuación, esta heurística argumento puede ser extendido para proporcionar una explícita límite superior de $2\lceil\sqrt{2^{127}}\rceil$: entre la $2^{127}$ valores de $5^k3^l\bmod 2^{127}$ $1\leq k\leq \lceil\sqrt{2^{127}}\rceil$, $1\leq l\leq \lceil\sqrt{2^{127}}\rceil$ no debe (por el principio del palomar) ser un choque, es decir $5^{k_0}3^{l_0} \equiv 5^{k_1}3^{l_1}$. A continuación, dividir, obtenemos $5^{k_0-k_1}3^{l_0-l_1}\equiv 1$, donde claramente $0\leq |k_0-k_1|\leq\lceil\sqrt{2^{127}}\rceil$, e igualmente para la $l$ valores. (Este argumento no sirve para el problema real, por supuesto, porque no hay ninguna garantía de que $k_0-k_1$ $l_0-l_1$ tienen los mismos signos.)