For example, there is already a method of showing that gcd(a,b) = gcd (c,d) in general if you show that, say, gcd(a,b) being divisible by k is equivalent to gcd(c,d) being divisible by k. Why? Because the set of all common divisors of a and b is equal to the set of all common divisors of c and d. Thus, the greatest elements are therefore going to be equal.

However, I want to know if there is a similar approach for doing gcd(a,b) = c where you cannot just use the Euclidean Algorithm.

Let's say you something like wanting to show that gcd($ab - 1, bc^2 - 2$) = $ba^{gcd(a,b)} - c$ where you have absolutely no idea what the values are. I'm just using it as a completely made up example. I thought at first the anti-symmetric principle of relation | (division) would've worked, but it turned out it didn't.

  • 1
    $\begingroup$ I would try to prove that $$\text{gcd}(a, b)\mid c \text{ and }c\mid \text{gcd}(a, b)$$ $\endgroup$ – Dr. Mathva Mar 11 at 22:40
  • 2
    $\begingroup$ $\gcd(a,b) = c\,$ is equivalent to $\, d\mid a,b \iff d\mid c,\ $ and the first to $\ e\mid a,b\iff e\mid c,d,\ $ see the GCD Universal Property $\endgroup$ – Bill Dubuque Mar 11 at 22:40

Using standard notation $\ (x,y) := \gcd(x,y),\, $ we have the following universal gcd characterization

$\quad\ (a,b) = c\,\ $ is equivalent to: $\ d\mid a,b\iff d\mid c,\, $ and $\, c\ge 0\ \ \ $ [GCD Universal Property]

As you surmised, this proves handy for proving equality of gcds, e.g. that below (like your template)

$\quad \bmod d\!:\ \underbrace{a^{\large b}\!\equiv 1\equiv a^{\large c}}_{\large d\ \mid\ a^{\Large b}-1,\ a^{\Large c}-1\ \ }\!\!\!\iff\! {\rm ord}\,a\mid b,c\!\iff\! {\rm ord}\,a\mid (b,c)\!\iff\!\! \underbrace{a^{\large (b,c)}\!\equiv 1}_{\large d\ \mid\ a^{\Large (b,c)}-1\ \ }$

Therefore $\ \, (a^{\large b}-1, a^{\large c}-1)\, =\, a^{\large (b,c)} - 1.\,$ This is a prototypical example of such proofs.

Similarly $\, (a,b) = (c,d)\,$ is equivalent to $\ e\mid a,b\iff e\mid c,d,\, $ and this extends in the obvious way to any number of gcd arguments.


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.