# Prove by induction that $f(a,b) = \frac{a}{b} + \frac{b}{a} + \frac{1}{ab}$ is a multiple of 3 if it is an integer

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.

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

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$$.