I have the following problem that I am struggling with. The problem is this:

Let $a,b,c$ be integers. Prove that if $ab+c = a^2c-b+a$ then $\gcd(a,c)=\gcd(b,c)$

I tried lots of rearranging of the above formula to get it into a form that resembles: $ax+cy = bi+cj$ which is $\gcd(a,c)=\gcd(b,c)$ by $\gcd$ characterization but have had little success.

Any help would be appreciated! Thanks!

  • 1
    $\begingroup$ Notice that $ab + c - a = a^2c - b$. So now, if we let $g = \gcd(a, c)$ and $h = \gcd(b, c)$. Then we have that $g$ divides left hand side and $h$ divides ring hand side, so $h$ divides $ab + c - a$ and $g$ divides $a^2c - b$. Thus by the first part, $h \le g$ and by the second $g \le h$ so must be equal. $\endgroup$ – mdave16 Jun 6 '17 at 23:36
  • $\begingroup$ I am starting to doubt you did lots of rearranging... my solution is $x = b-1, y = 1, i = -1, j = a^2$. And many other solutions are available, including $x= 1, y = a^2, i = a +1, j=1$ $\endgroup$ – mdave16 Jun 6 '17 at 23:40

Actually, $D(a,c)=D(b,c)$, where $D(u,v)$ is the set of common divisors of $u$ and $v$.

Indeed, if $d \in D(a,c)$ then $d$ divides $ab+c$ and so $d$ divides $b=a^2c+a-(ab+c)$. Therefore, $D(a,c) \subseteq D(b,c)$.

Conversely, if $d \in D(b,c)$ then $d$ divides $ab+c$ so $d$ divides $a=ab+c-(a^2c-b)$. Therefore, $D(b,c) \subseteq D(a,c)$.

In particular, $\gcd(a,c)=\max D(a,c)=\max D(b,c)=\gcd(b,c)$.


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.