# 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?

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!

• You need to be more specific with your proof. From the outline there should be no objection, so either your tutor is wrong or you made an error. We can't determine which. – Matt Samuel Oct 30 '18 at 2:36
• Possibly the confusion arises because you used two different proofs to show that neither gcd exceeds the other, but you can just repeat the same proof replacing $b$ and $n$ with $b+na$ and $-n$. – Neil Oct 30 '18 at 9:24
• This has been the way I have understood things: The following is true $\forall k \in \mathbb N$, for any pair of integers $(n,j)$: $$n\gcd(j,k)-\gcd(j,n)\Bigl\lfloor \frac{n\gcd(j,k)}{\gcd(j,n)}\Bigr\rfloor=0$$ $$j\gcd(j,k)-\gcd(j,n)\Bigl\lfloor \frac{j\gcd(j,k)}{\gcd(j,n)}\Bigr\rfloor=0$$ – Adam L Nov 3 '18 at 17:14
• The above two equalities can be summed only in integer multiples of $n$ and $j$,ie $\forall a,b \in \mathbb Z$ $$(an+bj)\gcd(j,k)-\gcd(j,n)\Bigl\lfloor \frac{(an+bj)\gcd(j,k)}{\gcd(j,n)}\Bigr\rfloor=0$$ – Adam L Nov 3 '18 at 17:14

The outline of the proof that you have explained is correct.

More than likely the problem was with the detail in one of the intermediate steps.

I would check each step carefully again and there is always room for skipping a point in writing a proof.

You want to know where the error is in your proof. Given no details no one can give the answer. All we can do is give only our opinion, so do not treat this as an answer.

The sketch given is correct, but it is merely a restatement of what is required to be proved. Possible that both you and your tutor are correct, but tutor did not understand the proof and misjudged it. But given that you expect people to be able to analyze your "proof" without providing details I am inclined to believe you are wrong. (IT IS AN OPINION!)

• Yes, I also did assume that I was wrong. This is why I provided only the outline sketch since I thought my thinking error would have been with my 'proof-strategy'. I translated now my complete proof and my tutors response as an edit to the original question. – DaGoddyMan Oct 30 '18 at 3:18

Ok well firstly, if your tutor has not mentioned to you something by the name of the Euclidean Algorithm, then he or she isn't being very forthcoming about their level of expertise in the subject it's as simple as that. But follow the link I provided there, and apply the method to both greatest common divisor expressions, and this might be able to help you reach a better level of understanding on the subject, the process is clearly explained in the link.

Also important to note that you shouldn't worry about studying a modern day definition of an algorithm,don't start to think this has anything to do with programming or a need to learn a programming language, this algorithm was invented over 2300 years ago, there was no necessity to update java at that point.

Secondly if your tutor's final step is to demonstrate that $$d \leq e \leq d$$, then it is in fact their solution that is completely bogus and circular, since this statement is equivalent to the original equality that we are trying to prove!

I recommend purchasing a hard cover book in Analytic Number Theory, one that provides the solutions for every exercise it contains, so that if you really are unable to find a proof you are confident with, you can look at the one the book has provided.

I currently use one that I have found to be priceless, "Problems in Analytic Number Theory" Second Edition, written by M.Ram Murty. But do ask your supervisors at your college what they recommend.

• Proving that $d=e$ by proving that $d\leq e\leq d$ is a standard approach and there is nothing bogus in it. – Ister Oct 31 '18 at 7:40
• It's the same question. If you asked me to prove dragons are real and I replied "I shall do so by proving dragons are real, hence proving dragons are real" would you be satisfied? – Adam L Oct 31 '18 at 18:49
• No, it's entirely different thing. You have a single statement to prove ($d=e$) but instead you prove two separate statements usually following different approaches ($d\leq e$ is one proved statement and $e\leq d$ is another one). Only now you apply a not so obvious implication that if $d\leq e\leq d$ holds then $d=e$ so if we've proved the former then the latter is truth indeed. As I said - this method is pretty common, especially when calculating limes but also in some other cases. – Ister Nov 2 '18 at 20:54
• $d=e$ is just an abbreviation for $d \leq e \leq d$. $e \leq d$ means $e$ is less than or equal to $d$. $d \leq e$ means $d$ is less and or equal to $e$. $d=e$ is equivalent to the statement $e \leq d$ and $d \leq e$, since $e \lt d=\lnot(e \gt d)$ – Adam L Nov 3 '18 at 9:09
• I totally disagree that it's just an abbreviation. You define $\leq$ as equal or less (you need to have at least weak order in order to write something like that at all) so equality precedes weak inequality. Of course proving that $d\leq e \leq d \iff d=e$ is trivial but still it's a property of weak inequality. That's why it is worth and can be used as a proof method to separately show each of the weak inequalities and then conclude that it means equality in the end. – Ister Nov 5 '18 at 9:51

Your proof is indeed correct. It can be reorganized more symmetrically as follows.

Notice that if $$\ c\mid a\$$ then $$\ c\mid b \!+\! na \iff c\mid b.\,$$ Therefore $$\,a,\, b\!+\!na\,$$ and $$\,a,\, b\,$$ have exactly the same set $$\,\cal C\,$$ of common divisors $$\,c,\,$$ so they have the same greatest common divisor $$(= \max \,\cal C)$$

• @Ister Please read more carefully. The answer says nothing at all about "invalidating OP's proof". Nor is there any such mistake. Analyzing (e.g. simplifying) proofs is an important part of teaching. I often point out such simplifcations arising by exploiting innate symmetry, e.g. yesterday using reflection (negation) symmetry to simplify sum computation, and many others. – Bill Dubuque Oct 31 '18 at 16:15
• I must have had bad day, sorry. My comment removed. – Ister Nov 2 '18 at 20:55

In my opinion your tutor is plainly wrong, too much focused on the proof he's accustomed to. It's often a problem. Let me say I faced this issue all the time since I tended to think out of the box and find my own, correct solutions, different to the canonical one.

You proved by definition, which is a fully valid proof. Thus technically you don't have to prove anything else.

Yet, since your tutor apparently don't understand this basics, you have to be smarter than him and be able to counterargument him (i.e. explain why his statement is plainly wrong).

My tutor wrote, that I only showed $$gcd(a,b+na)\leq gcd(a,b)$$ and also need to show the other direction.

In the first part of your proof by showing that $$d$$ is a divisor of both $$a$$ and $$b$$ you've proved that $$gcd(a,b) = d \leq gcd(a,b+na)$$. By definition of $$gcd$$ (name even represents that!) for any given divisor $$z$$ of both $$x$$ and $$y$$ we have $$z\leq gcd(x,y)$$. By substituting $$x=a$$ and $$y=b+na$$ you have the statement that your tutor claims to be missing.

Let me emphasise it once more - you don't need that explanation in your proof, which is perfectly valid. This is only to show that your tutor's claim is wrong.

As an anecdote...

In the course of probabilistic we once had some simple homework task from combinatorics. I don't remember details now but it's actually irrelevant. I had done my calculation, verified them and as a result got a nice looking solution.

On the next lesson I was presenting the solution on the blackboard. Imagine my surprise when I heard my solution is wrong. Someone else had done the task on the blackboard the right way and indeed the results didn't look alike at all. If I remember correctly there were even different powers used in it! Of course, the new solution was correct and in accordance to the key, yet I was sure mine was correct as well (despite all odds and apparent difference) so I stood up for it and asked to point out where had I made an error. No-one, including the tutor could find anything. Eventually the tutor said it might be that the two polynomials are equivalent and if I was able to prove that equivalence I will have the whole course passed with maximum grade.

Needless to say it took me 3 months of work, some horrible calculations and some peculiar theorem from number theory but I did it. The two results are equivalent.

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

• Can whoever downvoted this please explain, what my error is. If it was due to my bad formatting, I fixed it. – Nathrat Oct 30 '18 at 11:26
• I didn't downvote but your answer may not be clear. You are trying to give a counterargument to tutor's wrong quoted statement. You should though be more firm in your statement (do the math and make sure you are right) plus add a clear explanation that it means OP is correct in his proof. Note - you are right, but gap in your proof might be to difficult to fill. Try making it more complete (or check my answer as it is actually filling this gap. – Ister Oct 31 '18 at 8:01