0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i tried but i couldn't get what you mean by 'whether an additional factor of A is also a factor of k' $\endgroup$ – viru Dec 10 '16 at 10:29
  • $\begingroup$ @viru Well a common factor of $A$ and $A-kB$ cannot be a factor of $B$ so must be a factor of $k$. $\endgroup$ – Mark Bennet Dec 10 '16 at 10:31

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.