Is there an intuitive way to tell if some integers are relatively prime?

117 Views Asked by At

Suppose I have $a,b \in\mathbb Z$ such that $$\gcd(a,b)=1$$ My question is this:

Is there a way to intuitively know if $(a,b)$ are relatively prime without having to preform the Euclidean Algorithm and without knowing beforehand that $\gcd(a,b)=1$.

2

There are 2 best solutions below

2
On BEST ANSWER

In some special cases, we do not need the Euclidean algorithm, for example when both numbers are even or divisble by $3$. Consecutive numbers can immediately be detected to be coprime. Possibly, we see immediately that one number is a multiple of the other.

Ignoring such or similar cases, without the Euclidean algorithm, we won't be able to distinguish between coprime numbers and numbers sharing only one large prime factor.

2
On

The other way would be prime decomposition of $a$ and $b$.

If they do not share any primes, they are relatively prime, otherwise $ \gcd(a,b)>1$