I'm trying to solve the following problem by induction but I'm getting stuck.

For positive integers $a$ and $b$, define $$f(a,b) = \frac{a}{b} + \frac{b}{a} + \frac{1}{ab}.$$ If $f(a,b)$ is an integer, prove that it is a multiple of 3.

Proof by induction on a:

Base case: $a=1$

$$f(1,b) = \frac{1}{b} + \frac{b}{1} + \frac{1}{b} = \frac{2}{b} + b$$ Since $f(1,b)$ is an integer than $\frac{2}{b}$ must be an integer and $b\in\{1,2\}$ . Then $f(1,b) = 3$.

Inductive hypothesis: Assume for some integer $k \ge 1,$ $$f(k,b) = \frac{k}{b} + \frac{b}{k} + \frac{1}{kb}$$ is an integer and is a multiple of 3.

I want to show that $f(k+1,b)$ is also a multiple of 3. Then

$$f(k+1,b) = \frac{k+1}{b} + \frac{b}{k+1} + \frac{1}{(k+1)(b)} = \cdots.$$

And this is where I get stuck. I know there are other ways to solve this problem but I wanted to try it by induction. Hope someone can help with this! Thanks.

  • 1
    $\begingroup$ I doubt there's an easy solution by induction because it won't necessarily be true that $f(k+1, b) \in \Bbb Z$. $\endgroup$ – Robert Shore Nov 22 '19 at 23:44
  • $\begingroup$ Darn. I am hoping there is some kind of clever trick that I am missing. $\endgroup$ – Jonathan Nov 22 '19 at 23:47
  • $\begingroup$ Actually, $f$ is exactly 3 en.wikipedia.org/wiki/… $\endgroup$ – Will Jagy Nov 23 '19 at 2:27

Note that $$f(a,b)=\frac{a^2+b^2+1}{ab}$$ So, if $ab\mid a^2+b^2+1$, then $f(a,b)$ is an integer.

Note that $a^2\equiv0,1\pmod3$.

If $3\mid a$, then $$a^2\equiv0\pmod3\to a^2+b^2+1\equiv1,2\pmod3$$so $3$ doesn't divide it, but $3\mid ab$. This implies that $f(a,b)$ is not an integer. The same analysis holds when $3\mid b$.

So, $f(a,b)$ can only be an integer if $3\not\mid a,b$. But, that implies that $a^2,b^2\equiv1\pmod3$, which implies that $$a^2+b^2+1\equiv3\equiv0\pmod3$$i.e., $a^2+b^2+1$ is divisible by $3$, but $3\not\mid ab$. So, $f(a,b)$, if it is an integer, divides $3$.

| cite | improve this answer | |

I don't see how to solve the problem by induction but there's a fairly simple solution without induction. Note that

$$f(a, b)= \frac{a^2+b^2+1}{ab}.$$

If either $3 \vert a$ or $3 \vert b$, then the numerator is not a multiple of $3$, but the denominator is, so the fraction can't be an integer.

If neither $a$ nor $b$ is a multiple of $3$, then $a^2 \equiv b^2 \equiv 1 \pmod{3}$ so the numerator is a multiple of $3$ and the denominator is not, so if the fraction is an integer it must be a multiple of $3$.

| cite | improve this answer | |

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.