0
$\begingroup$

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$.

$\endgroup$
  • 3
    $\begingroup$ no, there really isn't . IF you can guess a pair of numbers so that $ax+by = 1,$ then you have confirmation. This formulation is usually given the name Bezout. $\endgroup$ – Will Jagy Jun 9 '18 at 22:37
  • 1
    $\begingroup$ No, there isn't. There are lots and lots of special cases, but mostly no. $\endgroup$ – Dzoooks Jun 9 '18 at 22:38
  • 1
    $\begingroup$ My experience with divisibility problems is that they are highly sensitive to a change of base and so trying to find patterns in the numeric representation tends to tell you more about the base than the numbers themselves. $\endgroup$ – CyclotomicField Jun 9 '18 at 23:10
  • 2
    $\begingroup$ What do you mean by "intuitive"? Can you give an exmaple of intuitive? $\endgroup$ – Somos Jun 9 '18 at 23:30
  • 1
    $\begingroup$ @SincerelyPrime No, in general there is no way. The numbers could share a large prime factor that cannot be seen by just looking at the numbers. $\endgroup$ – Peter Jun 9 '18 at 23:40
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Don’t forget casting out $11$’s for finding divisibility by $11$: take the alternating sum of the digits to find the congruence class modulo $11$. $\endgroup$ – Lubin Jun 9 '18 at 23:55
  • $\begingroup$ @Lubin I am aware that there are many other possibilities that can simplify the task, but I do not think that they can all be mentioned. $\endgroup$ – Peter Jun 9 '18 at 23:57
1
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ For numbers that are not too big, this is probably the fastest way, certainly if you’re limited to doing mental arithmetic. Say $237$ and $541$. The first is obviously $3\cdot79$, the second clearly not divisible by $3$, so you only need to check whether $79|541$. Since $541$ is obviously neither $6\cdot79$ nor $7\cdot79$, the two are relatively prime. $\endgroup$ – Lubin Jun 9 '18 at 23:52
  • $\begingroup$ I actually think that the only intuition that we can get in mathematics is what’s derived from extensive examination of examples. Put differently, there is no intuition in mathematics, till we get experience with phenomena. $\endgroup$ – Lubin Jun 10 '18 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.