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

$$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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 22 at 21:07

• Please read this tutorial on how to typeset mathematics on this site. – 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 ...

• So, gcd(a,b) => a = b*q + r  ? – Sherin Apr 22 at 7:29
• Nope @Sherin. That implies $\text {gcd} (a,b) = \text {gcd} (b,c).$ – 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:

$$k.b_1+a_1=1$$

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