¿Cómo calcular la inversa del GCD? por ejemplo si tenemos GCD(a,b) = 7 como determinamos los valores de a,b . nota : a,b tienen un límite dado y el resultado dado del GCD es siempre un primo.
estoy tratando de resolver este problema y la inversión de GCD es la primera idea que me vino a la mente ya que a,b límite son < $10^7$
No lo hace, porque no tiene una inversa. Por ejemplo, hay infinitos pares $(a,b)$ con GCD $(a,b) = 1$ (estos números se denominan "relativamente primos" o "coprimas").
EDIT: Quizás más al punto, hay infinitos pares $(a,b)$ con GCD $(a,b) = 7$ . Por ejemplo, $(7a, 7b)$ para cada par de enteros coprimos $a$ y $b$ .
$gcd(21, 3*14) = 21$ . Más bien deberías haber dicho que como hay infinitos enteros coprimos y $gcd(a, b) = 1 \implies gcd(7a, 7b) = 7$ hay infinitas parejas para cualquier $n$ .
En general, $\text{gcd}(a,b) = d$ (con $d \in \mathbb{Z}^+$ ) si y sólo si existe $x,y \in \mathbb{Z}$ que son coprimas y tales que $ax+by=d$ . Así que toma cualquier coprime $x,y \in \mathbb{Z}$ entonces podemos calcular $a,b \in \mathbb{Z}$ tal que $ax+by=d$ utilizando algún tipo de algoritmo, como el algoritmo euclidiano inverso. Sin embargo, $a,b$ no son únicos.
Si sólo quieres una solución (en lugar de todas las soluciones), dado $d$ y un límite, entonces como $\left| a \right|$ y $\left| b \right|$ debe ser $\ge d$ , podrías simplemente tomar $a=b=d$ (a menos que el límite sea $<d$ en cuyo caso no existen soluciones). Esta es la solución correspondiente a $x=1, y=-1$ arriba.
Editar: Este es un algoritmo para encontrar todos los $a,b$ con gcd $d$ dado un límite $M>0$ .
Dejemos que $S=\varnothing$ . Para cada $-M \le a \le M$ y $-M \le b \le M$ , calcule $\text{gcd}(a,b)$ (utilizando, por ejemplo, el algoritmo euclidiano). Si $\text{gcd}(a,b) = d$ , añadir $(a,b)$ a $S$ Si no es así, descártalo. El conjunto resultante $S$ contiene todos los pares $(a,b)$ dentro del límite dado tal que $\text{gcd}(a,b)=d$ .
He añadido un enlace a la pregunta espero que me puedan ayudar con eso,, gracias de antemano ^^
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Acabo de darme cuenta de que has dicho " $a$ y $b$ tienen un límite dado". ¿Querías decir que teníamos un límite?
0 votos
Tomar cualquier límite u gustaría en cualquier número primo resultado Sólo quiero saber si hay una forma sistemática general de resolver este .