¿cómo resolver problemas matemáticos de módulos?

Question

[prefacio, usaré '%' como el operador de modulo o resto, como es en C y muchos otros lenguajes de programación, donde por ejemplo 10 % 7 == 3]

Estoy buscando un algoritmo para resolver n en

(A*n + B) % C == 0

donde A, B y C son números enteros positivos.

Tengo restricciones adicionales en mi problema particular que no creo que sean importantes para la solución. (a saber, A es menor que C, A es una potencia de 3, C es una potencia de 2, y B es impar, todo lo cual creo que implica que n debe ser impar). (y sí, estoy jugando con Collatz aquí)

Puedo hacer fuerza bruta (probar todos los n posibles de 0 a C-1), pero eso consumirá mucho tiempo a medida que aumente C. También podría intentar una búsqueda binaria, lo que mejoraría el rendimiento, pero estoy buscando un algoritmo más eficiente.

Answer 1

Traduciendo a una teoría de números más estándar, quieres una solución a $$ An\equiv-B\pmod C $$ El primer paso para una solución es resolver $$ Am\equiv 1\pmod C $$ Entonces obtenemos $n=-Bm$ multiplicando ambos lados por $-B$ .

El algoritmo euclidiano ampliado da dos números enteros $m, m'$ tal que $$ Am+Cm'=1 $$ (ya que sus limitaciones adicionales nos dicen que $\gcd(A,C)=1$ ). Así termina la solución. Una solución entre $0$ y $C$ no está garantizada en este caso, por lo que tomar $n\%C$ al final te lo dará.