¿Cómo puedo encontrar un número $n$ tal que $(c + d \times n)$ es múltiplo de $(a + n)$ ?

Question

Por ejemplo $a=5$ , $c=246$ y $d=316$ . Mi objetivo es encontrar un entero positivo $n$ tal que

$$(a + n) | (c + d \times n)$$ $$(5 + n) | (246 + 316 \times n)$$

Sé que una solución es $18$ ya que

$$(5 + 18) | (246 + 316 \times 18)$$ $$23 | 5934$$ $$23 \times 258 = 5934$$

El número $24$ también es una solución, así como algunos otros números.

¿Cómo puedo encontrar directamente soluciones a este problema? Hasta ahora, la única forma en que he encontrado soluciones es a través de la fuerza bruta (probar todos los números posibles en orden), pero eso es terriblemente ineficiente.

Además, si cambiara la restricción de "ser un múltiplo" a "tener un GCF $> 1$ ", ¿facilitaría el problema?

Answer 1

Hacer el ansatz

$$d\cdot n + c = (d+k)\cdot(n+a).$$

Ampliando el lado derecho, se obtiene

$$\begin{align} d\cdot n + c &= d\cdot n + k\cdot n + d\cdot a + k\cdot a\\ c - d\cdot a &= k\cdot (n+a). \end{align}$$

Así que hay que factorizar $\lvert c - d\cdot a\rvert$ (si eso es $\neq 0$ si $c = d\cdot a$ entonces todos $n$ trabajo), y luego puede comprobar qué factorizaciones dan lugar a una $n$ (el segundo factor debe ser $> a$ ).

En su ejemplo, tiene $d\cdot a - c = 5\cdot 316 - 246 = 1334 = 2\cdot 23\cdot 29$ .

Así se obtienen las factorizaciones

$$\begin{align} c - d\cdot a &= -1\cdot 1334 \leadsto n = 1334-5 = 1329\\ &= -2\cdot 667 \leadsto n = 667-5 = 662\\ &= -23\cdot 58 \leadsto n = 58-5 = 53\\ &= -29\cdot 46 \leadsto n = 46-5 = 41\\ &= -46\cdot 29 \leadsto n = 29-5 = 24\\ &= -58\cdot 23 \leadsto n = 23-5 = 18\\ &= -667 \cdot 2 \leadsto n = 2-5 = -3 < 0\quad\text{ invalid}\\ &= -1334 \cdot 1 \leadsto n = 1-5 = -4 < 0\quad\text{ invalid}. \end{align}$$