Common divisors of $a , b$ and $a$ mod $b$

Question

Euclid's algorithm for finding gcd is as follows

gcd(a,b)=gcd(b,a mod b) gcd(a,0)=a

It follows from the fact 'every' common divisor of a and b must be common divisor of a mod b

prove or disprove the gcd can be given by gcd(a,a mod b) // used (a,a mod b) instead of (b,a mod b)

a simple examaple like this may disprove above statement

a=54

b=27

a mod b= 0

So, gcd(54,27)=gcd(54,0)=0 which clearly is not true or intuitively gcd(a,b)<=min(a,b) since min(a,b) is b. i think we first should propagate b for first parameter (which i think would be the reason why gcd(b,a mod b) is right one ... correct me if am wrong)

could someone give more formal proof for why gcd(a,b)!=gcd(a, a mod b)

and which of following statements is true

1. every common divisor of a and a mod b is a divisor of b

2. every common divisor of b and a mod b is a divisor of a

I think 1 is false and 2 is true ... the fact that ('1 is false') there may be common divisor of a and a mod b which may not be divisor of b would be enough for disproving.

Answer 1

Here is a start:

Let $d$ be the greatest common divisor, so that $a=dA$ and $b=dB$ with the gcd of $A$ and $B$ equal to $1$.

We can write $m=a\bmod b$ as $m=a-kb$ for some unknown integer $k$

Then $m=dA-kdB=d(A-kB)$ is divisible by $d$

Because $A$ and $B$ are coprime, the only issue is whether an additional factor of $A$ is also a factor of $k$ (you should justify this).

I always find that writing these things in terms of basic arithmetic clarifies what is going on. You should be able to complete your problem from here.