Forma eficaz de encontrar $a$ $c = 6a\mod n$

Question

Dado $c$$n$$c = 6a\mod n$, ¿cómo puedo encontrar el menor entero positivo valor de $a$?

Podía encontrar de forma iterativa mediante la reescritura como $\displaystyle a = \frac{c + xn}{6}$ y el aumento de la $x$ hasta $a$ es un número entero, pero yo preferiría una solución más eficiente. Hay otra manera de hacer esto?

Edit: se Combinan dos variables.

Aquí está un ejemplo: $3 = 6a\mod 11$

Answer 1

En primer lugar, las observaciones generales.

La congruencia $$Ax\equiv c \pmod{n}$$ tiene una solución $x$ si y sólo si $\gcd(A,n)|c$. Si lo hace, el método estándar es utilizar el algoritmo de Euclides extendido a encontrar enteros $r$ $s$ tal que $$d = Ar + ns$$ (donde $d=\gcd(A,n)$); luego se multiplica por $\frac{c}{d}$ (un número entero, ya que $d|c$) para obtener $$c = A\left(\frac{rc}{d}\right) + n\left(\frac{sc}{d}\right).$$ Así que una solución es $a=\frac{rc}{d}$. Encontrar el resto de $\frac{rc}{d}$ modulo $n$ se puede hacer de forma directa de la división. Si $d\gt 1$, entonces usted todavía necesita para asegurarse de que no hay más pequeños de la división comparando con $\frac{n}{d}$, ya que dado cualquier solución particular a $Ax\equiv c\pmod{n}$, $x\pm\frac{n}{d}$ es también una solución.

El algoritmo de Euclides extendido es bastante eficiente, pero aún así hay un par de ajustes que se pueden realizar para hacer aún más (por ejemplo, en lugar de requerir siempre que el saldo sea positivo, se puede requerir que el resto se encuentran entre $-\frac{n}{2}$$\frac{n}{2}$). Los otros pasos son bastante eficiente.

---

Añadido. Si, como indican en los comentarios, el módulo es primo, también se puede utilizar de Gauss método. Escribe la fracción que quieras (en este caso, $\frac{c}{A}$), y multiplicar el numerador y el denominador por el menor $k$ tal que $Ak\gt n$ (o que $Ak$ tiene un pequeño resto en valor absoluto modulo $n$); a continuación, reducir y repita hasta llegar a un denominador igual a $1$.

---

Ahora, tu problema en particular.

Sin embargo, el caso de $A=6$ y el primer módulo es particularmente simple, ya que cada primer distinta de $3$ es congruente a $1$ o a $-1$ modulo $6$. Así que escribe $n=6k\pm 1$, y el uso de $k$: Para el ejemplo que escribir, tenga en cuenta que $11 = 2\times 6 - 1$: $$a\equiv \frac{3}{6} = \frac{2\times 3}{2\times 6} = \frac{6}{12} \equiv \frac{6}{1} \equiv 6\pmod{11}.$$ Por otro, dicen que usted quiere resolver $$7\equiv 6a\pmod{43}.$$ Desde $43 = 6\times 7 + 1$, luego tenemos $$a \equiv \frac{7}{6} =\frac{7\times 7}{7\times 6} \equiv \frac{49}{42}\equiv \frac{6}{-1}= -6 \equiv 37\pmod{43}.$$ Etc.

En resumen. Para un primer módulo de $n\gt 3$, divida $n$$6$, y escribir $n=6k\pm 1$. Si $n=6k-1$,$a\equiv ck\pmod{n}$, por lo que entonces usted sólo tiene que dividir $ck$ $n$ para obtener el resto. Si $n=6k+1$,$a\equiv -ck$, por lo que encontrar el resto de $-ck$ lugar.

Answer 2

SUGERENCIA $\:$ Si es solucionable, entonces usted puede cancelar $\rm\:gcd(6,n)\:,\:$ rendimiento $\rm\: d\:a\ = b\ (mod\ m)\:$ $\rm\:d\:$ dividiendo $6\:.\:$ Ahora simplemente multiplicar por $\rm\:1/d\ (mod\ m)\:,\:$ que es fácilmente directamente computable, es decir,

$\rm\displaystyle\qquad\qquad\quad\: m\:\equiv\: \pm 1\ \ (mod\ d)\ \ \Rightarrow\ \ \frac{1}d\:\equiv\: \frac{1\mp m}{d}\ \ (mod\ m)\:.\ $

E. g. $\rm\displaystyle\qquad\ {\color{red}{25}}\:\equiv\: {\color{red}+1}\ \ (mod\ 6)\ \ \Rightarrow\ \ \frac{1}6\:\equiv\:\frac{1{\color{red}{-25}}}6\:\equiv -4\ \ (mod\ 25)$

E. g. $\rm\displaystyle\quad\ \ \ \ {\color{red}{23}}\:\equiv {\color{red}{-}}1\ \ (mod\ 6)\ \ \Rightarrow\ \ \frac{1}6\:\equiv\:\frac{1{\color{red}{+23}}}6\:\equiv\ \ 4\ \ \ (mod\ 23)$

Tenga en cuenta que la razón de esto funciona, así que simplemente es debido al hecho de que los únicos números coprime a $6$ los $\rm\:\equiv \pm 1\ (mod\ 6)\:.$