The maximum valued integer X such that X divides A i.e. A % X = O and X and B are co-prime

Question

I came across this question while practicing coding questions -

You are given two positive numbers A and B. You need to find the maximum valued integer X such that:

• X divides A i.e. A % X = 0

• X and B are co-prime i.e. gcd(X, B) = 1

I could only think of a brute force approach where I check for all the factors of A and test if that is coprime with B. Is there any faster way to do this?

Answer 1

This is certainly a faster way; I'm not sure if we could do better though. Here's the pseudocode:

X = A
While gcd(X,B) != 1:
    X = X/gcd(X,B)

For instance, if $A = 108$ and $B = 75$, we find $$ X = 108 \to 36 \to 12 \to 4 $$ As far as intuition goes, it's helpful to note that we could produce the value $X$ by multiplying all prime factors of $A$ which do not divide $B$.

Answer 2

This seems like more of a CS question than a math question, but:

X = A
for prime in primes:
    if ((prime > X) | (prime>B)): break
    if B%prime ==0:
        while X%prime == 0:
            X = X//prime