2

Let $a$ be a positive integer. Show that $\gcd(a, a-1) = 1.$

Let $d$ be the greatest common divisor of $a$ and $a-1.$ I.e. $\gcd(a, a-1) = d$

Therefore, $d$ must divide $a-(a-1),$ following the rule that if any number, when some number d divides two numbers, then d must also divide the difference.

In other words, $d\mid (a-(a-1)).$

If we simplify, d must divide $a-a+1= 1$.

I have shown that the $\gcd(a, a-1) = 1,$ since d = 1. QED.

b) Use the result of part a) to solve the Diophantine equation $a+2b=2ab,\,$ where $a, b \in \mathbb Z$.

Let $2b = 2k,$ where $k$ is an integer and therefore $2b$ is even.

Case 1: $a$ is even

If $a$ is even, then $a = 2k,$ where k is an integer.

$2k + 2k = 2(2k)(1)$

$4k = 4k$

Both sides equal each other...

This is where I stopped. I realized I wasn't using the previous proof to solve this equation. This is where I need help.

amWhy
  • 209,954
knowledge_is_power
  • 153
  • 1
  • 2
  • 13
  • 2
    The $k$ in $2b = 2k$ is different form the $k$ in $a = 2k$. Thus you cannot conclude that you have $2k+2k$. You should really use different letters. – Arthur Nov 08 '16 at 19:35
  • 1
    @Arthur Thanks for clarification! – knowledge_is_power Nov 08 '16 at 19:58
  • What do you mean by "Thanks for clarification"? You still did not clarify it. – Dietrich Burde Nov 08 '16 at 20:09
  • 1
    Why don't you read over what he said and see for yourself.. – knowledge_is_power Nov 08 '16 at 21:08
  • @Gabby I edited only to format your post...It took me time to get the hang of mathjax, here at MSE, when I first started. You can take a peak at the formatting syntax for each formatted expression by right-clicking on the formatted expression: then hover over "show as" to get a menu, from which you should click "TeX". In mathjax, "TeX" needs to be sandwiched by a dollar sign at each end. You can do that on any formatted question or answer on this site. – amWhy Nov 08 '16 at 21:56

3 Answers3

2

Note we can rewrite your equation as

$$a + 2b = 2ab \iff a = 2b (a - 1) $$

Both sides of the equation are integers so it follows that $a $ divides $2b(a -1) $. But because of your lemma we know $a $ and $a-1$ are coprime so $a \mid 2b \rightarrow 2b = ak $ for some integer $k $. Substituting we get that

$$a = 2b (a - 1) \iff a = ak(a - 1) \iff 1 = \frac {ak(a-1)}{a} \iff 1 = k(a-1)$$

Because both $a $ and $k $ are positive integers it follows that $a - 1 = 1 \rightarrow a = 2$ and $k = 1 \rightarrow b = 1$.

We divided by $a $ in our calculations so $a \not= 0$. A second of thought shows $a = b = 0$ would also be a possible solution.

Another way of going about it, without the lemma $gcd(a, a-1) = 1$:

$2b $ is always an even number and so is $2ab $ so it follows, from the equality $a + 2b = 2ab $ that $a $ is even.

If $a $ is even, then $a = 2k $ for some integer k. Substituting in first equality we get $2k + 2b = 2 (2k)b \iff 2 (k + b) = 4kb \iff k + b = 2kb $

Now we divide both sides by $b $ and $k $ separately to get

$$\frac{k + b}{b} = 2k \iff \frac{k}{b} + 1 = 2k$$

$$ \frac{k + b}{k} = 2b \iff \frac{b}{k} + 1 = 2b$$

From the left sides of the right equalities you get that both $\frac{b}{k}$ and $\frac{k}{b}$ must be integers so you conclude $b = k $.

Plugging in you get that

$$ k + b = 2kb \iff 2k = 2k^2 \iff k = k^2 \iff k = 0, 1$$

If you pick $k=0$ then $b = a = 0$. If you pick $k=1$ then $b = 1$ and $a = 2k = 2$.

RGS
  • 9,719
  • @GabbyQuattrone you can now see how, edited the answer – RGS Nov 08 '16 at 20:13
  • Did you not notice the new method added in your edit was already posted in my answer? – Bill Dubuque Nov 08 '16 at 21:07
  • 1
    Calm down, everyone is just trying to help. – knowledge_is_power Nov 08 '16 at 21:10
  • 1
    @BillDuduque you are absolutely right. The thing is: my first answer didn't use the hint and the OP pointed that out. So I started editing my answer. When I did start, no one else had posted anything else. Since I was following the lemma in a) it makes sense I end up saying something similar to you, but not only it was not the exact same thing but also I didn't see you saying that before my edit. Since I have been using my phone it takes a lot to edit questions. It is just that, really. – RGS Nov 08 '16 at 21:18
  • @Bill As a self-proclaimed expert in pedagogy and teaching, one's foremost goal must be for the questioner to understand the answer, and the reasoning behind it. That happened here. It's rather self-interested to insist upon getting credit for one component (among others) that led to that understanding. Also, please consider the fact that you do not have sole access to "the truth"; what you wrote is very accessible to any one with an undergraduate degree in math,. – amWhy Nov 08 '16 at 21:19
  • 1
    Nice work, @RSerrao.! Don't worry too much about Bill's indignation. I can't tell you how many times two, three, even four answerers, all working independently, post their nicely formatted answer, only to learn other users had the same idea. I can't even imagine trying to answer using a phone! – amWhy Nov 08 '16 at 21:28
0

To use the hint, rewrite the equation as $\ a = 2b(a\!-\!1).\,$ Thus $\ a\mid 2b\mid a\ $ by $\,\gcd(a,a\!-\!1) = 1$

Bill Dubuque
  • 272,048
  • 2
    @amWhy Not true. The OP asked for help, not for a complete soluion. I gave the key step following the given hint. If I write any more it will spoil the OP's learning experience. – Bill Dubuque Nov 08 '16 at 20:50
  • I agree with you. I'll delete my comment that was auto-posted. See? Many users can be rational and reconsider their actions,in response to a comment challenging the original actions. Work on it, yourself. – amWhy Nov 08 '16 at 21:08
  • 1
    Gabby: My comment was not directed at you, Gabby! Please forgive me, I was responding to Bill. Indeed, my comment was directed at @Bill. I was perhaps too quick to judge his answer; and of course, knowing Bill, he protested. So I replied to him, deleted my original comment, but forgot to name the addressee! – amWhy Nov 08 '16 at 21:10
  • Thank you , I'm sorry for the misunderstanding – knowledge_is_power Nov 08 '16 at 21:13
0

$1=2ab-2b-a+1=(2b-1)(a-1).$ Therefore, since $2b-1$ and $a-1$ are non-negative integers, we must have $2b-1=a-1=1.$

DanielWainfleet
  • 57,985