This question already has an answer here:

$b$ is an integer where $b > 1$ and $a, c$ are integers.

Prove: $\gcd(b,a) = \gcd(b,c)$ if $c \equiv a \pmod{b}$

I am completely stumped on where to start. Any help is appreciated.


marked as duplicate by Eevee Trainer, Javi, Leucippus, Bill Dubuque modular-arithmetic Apr 22 at 21:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Apr 22 at 9:44

Let $d= \text {gcd} (a,b)$ and $d'= \text {gcd} (b,c).$ Then $d \mid a$ and $d \mid b.$ Again $b \mid c-a \implies d \mid c-a.$ Since $d \mid c-a$ and $d \mid a$ so it follows that $d \mid c.$ Therefore we have $d \mid b$ and $d \mid c.$ So $d \mid d'.$

Now $d' \mid b$ and $d' \mid c.$ Again $b \mid c-a \implies d' \mid a-c.$ Since $d' \mid c$ and $d' \mid c-a$ it follows that $d' \mid (c-(c-a)) \implies d' \mid a.$ Therefore $d' \mid a$ and $d' \mid b.$ Hence $d' \mid d.$

This shows that $d=d',$ as required.


step 1. $c\equiv a\pmod b$ implies $c=bd+a$ for some $d$ (an integer).

step 2. $\gcd(a,b)$ is ...

  • $\begingroup$ So, gcd(a,b) => a = b*q + r ? $\endgroup$ – Sherin Apr 22 at 7:29
  • $\begingroup$ Nope @Sherin. That implies $\text {gcd} (a,b) = \text {gcd} (b,c).$ $\endgroup$ – Dbchatto67 Apr 22 at 8:15

Another approach:

$c ≡a \mod b$$c=k.b + a$; $ k∈Z$

Euclidean algorithm shows that there is always numbers like $a_1$ and $b_1$ such that following relation is hold:


Multiplying both sides by c we get:

$k(b_1 c)+ a_1 c=c

This means $b=b_1 c$ and $a=a_1 c$ which results:

$gcd(a, b)=gcd(b, c)=c$

The reverse procedure shows that if $gcd(a, b)=gcd(b, c)=c$, then we can have an equation like $c=k.b + a$ and a congruence like $c≡a \mod b$.


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