Ways to find one number in a pair given another number and their greatest common di

Question

I would like to know if there is a way to find number in a pair of number given another number and their greatest common divisor.

Example: find all n values given n <= 50 and gcd(n,50) =5.

Answer 1

In your example, we can find $n$ values by first factoring the given integer ($50$ in this case) as $$50 = 2\cdot 5^2$$ Then, $n$ must have exactly one multiplier $5$, and it must have no power of $2$, i.e. $2, 2^2, 2^3,...$ But it may have powers of other primes such as $3^k,7^k,11^k,13^k,...$, $k \in \mathbb{Z^+}$ but notice that not all them satisfies the condition $n < 50$ when multiplied by $5$ (like $5 \cdot 11 = 55$ or $5 \cdot 3^3 = 135$, etc.), which $n$ must have as a multiplier. So we can have

• $n = 5$,

• $n = 5\cdot 3 = 15$, $n = 5 \cdot 3^2 = 45$,

• $n = 5 \cdot 7 = 35$

When $n$ or the given numbers gets larger, this algorithm may be hard to use but for small numbers as in this case, this algorithm should work.