# If $(a,b)=1$ then prove $(a, b+1)=1$

So far I have,

• Let $d = (a,b)$
• Which implies $d\mid a$ and $d\mid b$
• Which implies there exist $x$ and $y$ such that $d\mid (a)(x) + (b)(y)$
• So I want to find an $x$ and $y$ that can make the equation, $ax+by$ into $(a+1)(x)+(ab)(y)$
-
what if you let $a = 5$ and $b = 6$? –  user51427 Dec 9 '12 at 20:36
I don't think that the statement is true. Try $a =2$ and $b = 3$. Then $(2,3) = 1$ but $(2+1, 2\times3) = (3,6) = 3$. Am I missing something? –  Tom Oldfield Dec 9 '12 at 20:37
What about $(6,7)=1$ while $(7,42)=7$? (well, I was too late...) –  Hendrik Jan Dec 9 '12 at 20:38
Maybe you mean $(a+b,ab)=1$ in the conclusion? –  Andres Caicedo Dec 9 '12 at 20:39
Anna: I edited your question. I tried to make the formatting more like what I think you had intended it to be. –  Thomas Dec 9 '12 at 20:40

if $b=a+1$ then the second gcd is $a+1$

-
what i mean is you square it and then you get a^2*x^2 + 2abxy +b^2y^2 and continue to manipulate it –  Cindy Dec 9 '12 at 20:47
@Anna, the statement you are trying to prove is false. At this point, you should go back and check the source of the problem very carefully. –  Will Jagy Dec 9 '12 at 20:51
Anna = Cindy?${}$ –  Gerry Myerson Dec 11 '12 at 6:05
@GerryMyerson, yes, she changed it not long after I wrote this answer. I'm pretty sure she had time to see this. And, she has gone on to ask a bunch of questions at this level. I don't think she pays much attention after she posts things...I get it, also unregistered. –  Will Jagy Dec 11 '12 at 6:12

This answer gives $u,v$ with $abu+(a+b)v=1$, given $ax+by=1$.

Start with $ax=1-by$, subtract $ay$ from both sides, and get $$a(x-y)=1-(a+b)y.$$ Now start with $by=1-ax$, subtract $bx$ from both sides, and get $$b(y-x)=1-(a+b)x.$$ Now multiply these equations to get $$ab(x-y)(y-x)=1-(a+b)x -(a+b)y + (a+b)^2 xy,$$ which may be rearranged as $$ab(x-y)(y-x)+(a+b)(x+y-(a+b)xy)=1.$$ With $u=(x-y)(y-x)$ and $v=x+y-(a+b)xy$ this is $abu+(a+b)v=1.$

-