Let $ a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. use the result of par t $ a)$ to solve the Diophantine equation $ a+b=ab$

Question

Not sure if I did part a right, not sure how to complete part $b)$

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

Proof by contradiction suppose $\text{gcd}(n, n-1) = p > 1$.

Then $n$ is a multiple of $p$, so $n = ap$ for some integer $a$. Similarly, $n-1 = bp$ for some integer $b$.

Next multiple of $p$ after $n$ will be $(a-1)p = n-p$, which is greater than $n-1$. We have $n=ap < n-1=bp < n-p=(a-1)p$

Dividing everything by $p$ we get $a < b < a-1$ meaning that $b$ is an integer sandwiched between $a$ and $a-1$. This is impossible.

$b)$ Use the result of part $a)$ to solve the Diophantine equation $a+b=ab$ where $(a,b)$ are positive integers.

Answer 1

Let $d = \text{gcd}(a,a-1) \to d\mid a, d\mid (a-1) \to d\mid [a-(a-1)] = 1 \to d = 1$.

$a+b = ab \to a = ab - b = (a-1)b \to b = \dfrac{a}{a-1} = 1 + \dfrac{1}{a-1}$. Can you go from here?

Answer 2

(a) Suppose $\gcd(n,n-1)>1$. $\exists p|\gcd(n,n-1)$, then $p|n$ and $p|n-1\Rightarrow p|n-(n-1)$ i.e. $p|1$. Contradiction!

(b) $a+b=ab\Rightarrow a=b(a-1)\Rightarrow a|b$ (Since, $\gcd(a,a-1)=1$) $\Rightarrow b=aq$

Solve $bq+b=b^2q\Rightarrow b(q+1)=b^2q\Rightarrow(q+1)=bq\Rightarrow q(b-1)=1$

Answer 3

We have $$a+b=ab \implies ab-a-b = 0 \implies (a-1)(b-1) = 1$$ Now obtain $a$ and $b$.