GCD(a,b) = GCD(a,b+a): Clarifying My Error

[Vorde]

I just got back a test and I received 0 for the following problem. I am (somewhat) comfortable with the idea that my justification isn't good enough, but I'm a little unsure where my error is so I would love to have someone illuminate that for me.

The problem was to show that the gcd(a,b) = gcd(a,b+a).

We know from the textbook (I'm allowed to do this; I cited the theorem) that if a|b and a|c then a|b+c. From that we then know that gcd(a,b) is A divisor of (a,b+a), but we don't yet know it is the greatest divisor. I believe my mistake is somewhere in the next line of reasoning: However we also know that gcd(a,b+a), whatever it is, cannot exceed gcd(a,b), because if it did then it would be a divisor of a (and by symmetry in the argument, a divisor of b) greater than the gcd(a,b), which contradicts the definition. It also cannot be less than gcd(a,b) because then it is no longer the greatest common divisor of (a,b+a). Thus gcd(a,b) = gcd(a,b+a).

Thank you very much, and I'll be happy to clarify if I need to.

 

[economicsnerd]

However we also know that gcd(a,b+a), whatever it is, cannot exceed gcd(a,b), because if it did then it would be a divisor of a (and by symmetry in the argument, a divisor of b) greater than the gcd(a,b)...

You correctly pinpointed the leap in logic.

The expression gcd(a,b+a) isn't symmetric in a,b. They play different roles there.

In general, employing "symmetry" in a proof is just a way of saying: "... and if I rewrote everything above, switching a & b, I would obtain..." You've noticed that gcd(a,a+b) is a divisor of a, and a symmetric observation would have been that gcd(b,a+b) is a divisor of b.

 

[economicsnerd]

Though posed in terms of the gcd, this isn't really a question about the gcd. Consider the two sets $$D=\{k\in\mathbb N:\enspace k \text{ is a divisor of both } a \text{ and } b\}$$ and $$D'=\{k\in\mathbb N:\enspace k \text{ is a divisor of both } a \text{ and } a+b\}.$$ If you can show that these two sets are equal, then they have the same greatest element.

 

[Vorde]

Though posed in terms of the gcd, this isn't really a question about the gcd. Consider the two sets $$D=\{k\in\mathbb N:\enspace k \text{ is a divisor of both } a \text{ and } b\}$$ and $$D'=\{k\in\mathbb N:\enspace k \text{ is a divisor of both } a \text{ and } a+b\}.$$ If you can show that these two sets are equal, then they have the same greatest element.

I see that, and many people (including me after I'd left the test) did it that way or thought about doing it that way.

I still don't quite see why a and b aren't symmetric though? Where is the asymmetry?

 

[economicsnerd]

What theorem are you invoking when you say, "by symmetry"?? The burden isn't on the reader to overturn the prover's claimed symmetry.

At the level of courses you're currently taking, whenever somebody says, "And by symmetry..." what they really mean is "And a similar argument can also be used to show..." If you don't know what the similar argument is, then you shouldn't cite a result under some claim of symmetry.

In your example, you pointed out the (tautological) fact that gcd(a,a+b) is a divisor of a, and then you claimed that "by symmetry" gcd(a,a+b) is also a divisor of b. But if you try to actually prove that gcd(a,a+b) is a divisor of b, you'll notice that it requires a new argument.