We have two numbers $a$ and $b$ and $\gcd(a, b)$. We can multiply one of these numbers on any prime number. We need to get the most possible gcd. How can we do that?
I had an idea like take all the prime numbers between $1$ and $\max(a, b) / \min(a, b)$ and check all the gcd's with these prime numbers and take the biggest. But this theory is not working if we have for example $a = 100500$ and $b = 500100$ because $b / a = 4$, but the right answer is $1667$ because of $\gcd(500100, 100500\cdot 1667)$ is $500100$, but my answer is $1500$. How can I solve it?
$\gcd(1,5)=1$
$\gcd(2\cdot1,2\cdot5)=2$
$\gcd(3\cdot1,3\cdot5)=3$
$\gcd(4\cdot1,4\cdot5)=4$
$\gcd(5\cdot1,5\cdot5)=5$
$\gcd(69\cdot1,69\cdot5)=69$
$\gcd(420\cdot1,420\cdot5)=420$
$\gcd(1000000000000000\cdot1,1000000000000000\cdot5)=1000000000000000$
-but all of these numbers have the same value of the bigger one divided by the smaller one - 5!!!! Isn't that crazy? In other words, just knowing the ratio of two numbers tells you nothing about the size of their gcd. No matter how you try to get around it, arguments based off of ratios here will typically be based on a false premise. Instead, you have to find greatest common number, which divides both of the things. And in fact, it could be as high as the min of the two. For example, for a prime p, $\gcd(p,a)$ is always equal to $p$ as long as $p$ is a divisor of $a$.
Moreover, it isn't true that the $\gcd$ of two numbers, $a$ and $b$, is less than whatever $\frac{\max(a,b)}{\gcd(a,b)}$ is, because that would mean that for arbitrary numbers $a$ and $b$
$(\gcd(a,b))^2\le\max(a,b)$
however this isn't always the case. It's a bit weird, but you can even just check this for $a=b$. If $a=b$, $(\gcd(a,a))^2\le\max(a,a)$, $(a)^2\le a$, $a^2\le a$, but sike this doesn't work, since a number isn't generally greater that it's square, unless you're talking about $a=1$
What you can say is that $\gcd(a,b)\le\min(a,b)$, though, since any divisor of a number is less than it (or rather, less than or equal to it).
You can also basically "pull things out" of gcd's;
$\gcd(pa,pb)=p\gcd(a,b)$
Now I agree, searching all the way up to the minimum of the two numbers is tedious and stupid. But you can speed things up a bit I suppose by first prime-factoring both numbers. You start by asking if it's divisible by the first prime, 2, and if it is then divide that number by 2 and pull out a two in front of it. Then repeat with 3, 5, and so on. However, even this is still really arduous for large numbers. Once you have that prime factorization, you just look for the largest powers of each prime number that goes into both of them.
In practice, the counterintuive (ish) Euclidean algorithm (but you shouldn't just learn about this because its fast - it's also a lit algorithm) is faster for finding gcd's, or at least, so I'm told. The algorithm itself is probably quite simple to set up but it's such a great, interesting, deep result in math.
Method 1: The idea is as follows:
$\gcd(500100,100500)=100\gcd(5001,1005)=300\gcd(67,1667)$. Now, $\gcd(67,1667)=1$. If you keep "pulling out" common factors from the $\gcd$, you will inevitably hit a point where you have to stop and you can't do it anymore. When this happens, the $\gcd$ of the two numbers is 1, because if it weren't, then you could pull something else out of it.
Method 2: The Euclidean Algorithm;
$\gcd(500100,100500)=\gcd(500100\text{ mod }100500,100500)=\gcd(500100-402000,100500)=\gcd(98100,100500)=\gcd(98100,100500\text{ mod }98100)=\gcd(98100,100500-98100)=\gcd(98100,2400)=\gcd(98100\text{ mod }2400,2400)=\gcd(98100-96000,2400)=\gcd(2100,2400)=\gcd(300,2400)=\gcd(300,2400)=\gcd(300,0)$, and almost as an artifact, the GCD of anything with 0 is that number, so this is $\gcd(100500,500100)=\gcd(300,0)=300$.
You get the idea the euclidean algorithm just allows you to keep doing things by continuously taking mod's until you get down to something like $\gcd(a,0)$.
Method 3: So using prime factorizations: $100500=100\cdot1005=10^2\cdot\left(5\cdot\frac{1005}{5}\right)=10^2\cdot5\cdot201=(2\cdot5)^2\cdot5\cdot3\cdot\frac{201}{3}=(2\cdot5)^2\cdot5\cdot3\cdot\frac{201}{3}=2^2\cdot5^2\cdot5\cdot3\cdot67$ and 67's prime. So, $100500=2^2\cdot3\cdot5^3\cdot67$. We have the same thing for 500100, so I won't show all the steps. You get $500100=100\cdot5001=2^2\cdot3\cdot5^2\cdot1667$. Remarkably 1667 is prime. If we look at the largest power of 2 which divides both of them, that'd be $2^2$ which is 4. If we look at the largest power of 3 which divides both of them, that'd be $3^1$ which is 3. If we look at the largest power of 5 which divides both of them, that'd be $5^2$ which is 25. Finally, the largest prime powers of 67 and 1667 dividing both of them are to the zeroeth power technically, which is just 1. Multiply of these together, and you get $2^2\cdot3\cdot5^2=3\cdot4\cdot25=3\cdot100=300$.
I understand the point may not to be to use the most efficient algorithm, but one you can create and manage yourself. I respect that. I think you have some good ideas and you're on the right track. $\gcd$'s can be weird functions, and behave in strange ways.
I'll add to this as you ask me more things. I know I probably haven't answered this in the best way I can, but I will keep trying.