1
$\begingroup$

I'm trying to prove the following:

No positive integers $a,b$ exist such that $7ab = 17(a+b)$

I've been struggling on this problem for the last hour and a half, and I keep running in circles. I've tried four or five different approaches, mostly revolving around divisibility / fundamental theorem of arithmetic, but I can't quite get the proof. I know that if this relationship held, then $ab = 17k$ and $a+b = 7k$ for some $k \in \mathbb{Z}^+$, but I can't seem to derive a contradiction from this. Can someone please help me finish this thing?

$\endgroup$
  • $\begingroup$ Adding to @farruhota's answer: since $\gcd(7, 17)= 1$ then $17\mid ab$ and $7\mid a + b$. Now according to Euclid's Lemma, if a prime number $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ must divide one of those integers $a$ and $b$. Since $17$ is a prime number, let $p = 17$. Then, for some integer $k$, either $a$ or $b$ is equal to $17k$. Let $a = 17k$, then $\ldots$ $\endgroup$ – Mr Pie Feb 21 '18 at 8:28
1
$\begingroup$

Without loss of generality, assume $a=17k$, then: $$7\cdot 17k\cdot b=17(17k+b) \Rightarrow k=\frac{b}{7b-17} \Rightarrow b\ge 7b-17 > 0 \Rightarrow b\in \emptyset.$$

$\endgroup$
1
$\begingroup$

$$a=\dfrac{17b}{7b-17}$$

Now if integer $d$ divides both $17b,7b-17;$

$d$ must divide $7(17b)-17(7b-17)=17^2$

So, $7b-17$ must divide $17^2$ to keep $a$ an integer

So, $7b-17$ must be one of $0,\pm1,\pm17,\pm17^2$ which is untenable.

$\endgroup$
  • $\begingroup$ "$d$ must divide $17^2$, so $7b-17$ must divide $17^2$ to keep $a$ an integer" --- Can you explain how you made this step? $\endgroup$ – Möbius Dickus Feb 21 '18 at 7:58
  • $\begingroup$ @MöbiusDickus, GCD$(17b,7b-17)$ must divide $289$ right? $$\implies17b,7b-17$$ cannot have any other common factor which doesn't divide $289$ $\endgroup$ – lab bhattacharjee Feb 21 '18 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.