Elementary question about a fake-proof and greatest common divisors I have a question to an excercise - for which I have a wrong solution - and I wanted to ask you to help me understand my thinking error. The excercise was as follows:

Let $a, b, n \in \mathbb{N}$. Show that $\gcd(a,b) = \gcd(a,b+na)$.

My solution was (in a nutshell):


Let $d := \gcd(a,b)$.
Then I showed that $d$ is a common divisor of both $a$ and $b + na$
Then I showed, that any common divisor $c$ of $a$ and $b+na$ is smaller-or-equal than $d$
After that, I concluded that by definition $d = \gcd(a,b+na)$, and with the definition of $d$ I would have $\gcd(a,b) = \gcd(a,b+na)$, so my proof was completed.


However, my tutor did not accept the proof. He showed me the 'correct' proof, in which I woould have $d := \gcd(a,b)$ and $e := \gcd(a,b+na)$ and then demonstrate $d \leq e \leq d$.

Anyway, I do understand his proof. But I still do not understand where my thinking error is. After all, if my starting line would be, let's say, $d := 9$ and I would have been able to show the steps afterwards, then I would be able to conclude $9 = \gcd(a,b+na)$, no?

Any comments would be welcome, thank you very much in advance!

EDIT
Wow, you guys answered fast! Thank you very much. I will ask my tutor on thursday again. For completeness sake, I will formulate my complete proof (my original proof is in german, so maybe there will be something lost in translation, the [Reference] are references to our script).

Let $a,b,n \in \mathbb{N}$. Let $d := \gcd(a,b)$. By definition it means $d \mid a$ and $d \mid b$, so with [Reference] the following holds true: $d \mid (b + na)$. Therefor, $d$ is a common divisor of both $a$ and $b + na$. We will show now, that $d$ is the greatest common divisor.

Let $c$ be any common divisor of $a$ and $b + na$. Therefor $c$ divides $a$, and as such $c \mid na$ und therefor $c \mid ((b + na) - na) = b$ (again because of [Reference]). So $c$ divides $b$, and therefor $c$ is a common divisor of both $a$ and $b$. Since $d$ was the greatest common divisor of $a$ and $b$, we have $c \leq d$.

By definition of the greatest common divisor we get $d = \gcd(a,b+na)$.

End of Proof. My tutor wrote, that I only showed $\gcd(a,b+na) \leq \gcd(a,b)$ and also need to show the other direction. Then he showed me the 'correct'/'ideal' proof today. But I will ask him again on thursday!
Your proof is perfectly correct.  Either you have misunderstood what your tutor said, you communicated your proof to your tutor incorrectly, or your tutor is just wrong.
End of Proof. My tutor wrote, that I only showed $\gcd(a,b+na) \leq gcd(a,b)$ and also need to show the other direction.


I am pretty sure, that $\gcd(a,b+na) \geq gcd(a,b)$ follows from $d:=\gcd(a,b)$ and $d\mid(b+na)$ (plus the definition of $\gcd$).