# Is there a method of proving that gcd(a, b) = c for values of a, b, and c that are not necessarily known?

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.

• I would try to prove that $$\text{gcd}(a, b)\mid c \text{ and }c\mid \text{gcd}(a, b)$$ – Dr. Mathva Mar 11 at 22:40
• $\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 – 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]
$$\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.