Encontrar el valor mínimo de x tal que GCD (A + x, B + x) = C donde A, B, C se dan

Question

Necesito agregar un entero entero no negativo mínimo para poder obtener el GCD deseado (a + x, b + x)

Digamos que A = 12 y B = 26

Para GCD (12 + x, 26 + x) = 1, x debe ser 1

Para GCD (12 + x, 26 + x) = 2, x debe ser 0

Para GCD (12 + x, 26 + x) = 7, x debe ser 9

Para GCD (12 + x, 26 + x) = 14, x debe ser 2

Answer 1

Su pregunta título dice usted quiere encontrar el valor mínimo de un entero no negativo, $x$ tal que $\gcd(A + x, B + x) = C$, donde $A, B, C$ son dadas. Primero, nota que no hay tales entero en ciertos casos. En particular, desde la $C$ divide $A + x$ e $B + x$, también debe dividir su diferencia, es decir, $C \mid (A + x) - (B + x) = A - B$. Por lo tanto, un requisito mínimo es que

$$A \equiv B \pmod C \tag{1}\label{eq1}$$

A continuación, considere el caso especial de $A = B$. Si $A \le -C$, a continuación, $x = -C - A$ obras. De lo contrario, si $A \le C$, a continuación, $x = C - A$ obras. Por último, si $A \gt C$, entonces el mcd siempre se $A + x \gt C$, por lo que no hay soluciones.

Si \eqref{eq1} se cumple y se $A \neq B$, la siguiente nota: $A$ e $B$ puede escribirse como

$$A = mC + r, B = nC + r, \; \text{ where } \; m,n,r \in \mathbb{Z}, \; m \neq n, \; 0 \le r \lt C \tag{2}\label{eq2}$$

Por lo tanto, $A + x = mC + (r + x)$, lo $C \mid A + x$ requiere $C \mid r + x$. En general, esto requiere

$$x = kC - r, \; k \ge 0 \tag{3}\label{eq3}$$

El menor valor no negativo de $x$ que podría funcionar es $0$ si $r = 0$, otra cosa es $C - r$. Para $B + x = nC + (r + x)$, también es cierto que $C \mid B + x$ en cualquier caso general.

La una cosa que usted necesita tener cuidado es que no hay otros factores comunes, por lo que el MCD sería un múltiplo de $C$. En particular, \eqref{eq3}, da $A + x = C(m + k)$ e $B + x = C(n + k)$. Por lo tanto, usted quiere encontrar el menor entero no negativo, $k$ tal que $x$ desde \eqref{eq3} es no negativo y $\gcd(m + k, n + k) = 1$. Tenga en cuenta que no siempre va a ser un $k$. Para ver esto, el mcd de a$m + k$ e $n + k$ debe dividir la diferencia, es decir, $m - n$. Desde $m \neq n$, a continuación, $\left|m - n\right|$ es $1$, en cuyo caso el mcd es siempre $1$, o es un producto de $1$ o más de los números primos, es decir, $\left|m - n\right| = \prod_{i = 1}^j p_i^{e_i}$ para algunos $j \ge 1$, primos $p_i$ y enteros $e_i \ge 1$. En el último caso, para cada una de las $i$, tenga en cuenta que $m \equiv n \equiv r_i \pmod p_i$ para algunos $0 \le r_i \le p_i - 1$. Puesto que todos los números primos son $\ge 2$, siempre hay al menos $2$ valores posibles para cada una de las $r_i$. Para cada uno, elegir cualquier valor de su suma con $r_i$ no es congruente a $0$. No $p_i$ sería divide $n + k$ o $m + k$. Por lo tanto, cualquiera de los factores primos de a$\gcd(n + k, m + k)$ debe ser diferente a cualquier $p_i$. Sin embargo, puesto que todos los factores primos de la dpc debe dividir la diferencia, esto significa que no hay factores primos de la mcd, es decir, $\gcd(n + k, m + k) = 1$. Para cada posible combinación de estas congruencias, el método descrito para controlar más de $2$ números de sección en el algoritmo de Euclides Extendido demuestra que siempre se puede encontrar enteros no negativos $k$ satisfacer las necesidades de congruencias. Por lo tanto, elegir el menor entero no negativo, $k$ entre todos esos valores para que $x$ dado en \eqref{eq3} es no negativo.

Para demostrar cómo funciona esto, aquí es cómo aplicar esto a tus ejemplos con $A = 12$ e $B = 26$. En primer lugar, como $26 - 12 = 14 = 2 \times 7$, los únicos valores posibles de $C$ se $1, 2, 7, 14$, como lo he demostrado. Para $C = 1$, desde el $\gcd(12, 26) = 2$, $12 = 12 \times 1 + 0$ e $26 = 26 \times 1 + 0$, pero $\gcd(12 + 1, 26 + 1) = 1$, usted necesita usar $x = 1$. Para $C = 2$, sólo $x = 0$ obras. Para $C = 7$, desde el $12 = 1 \times 7 + 5$, $26 = 3 \times 7 + 5$, e $\gcd(1 + 1, 3 + 1) = 2$, no se puede usar $x = 7 - 5 = 2$. En su lugar, ya que $\gcd(1 + 2, 3 + 2) = 1$, usted necesita usar $x = 14 - 5 = 9$ lugar. Finalmente, para $C = 14$, desde el $12 = 0 \times 14 + 12$, $26 = 1 \times 14 + 12$ e $\gcd(0 + 1, 1 + 1) = 1$, sólo se puede utilizar $x = 14 - 12 = 2$.