# How many integer solutions to a diophantine equation

Starting with the equation:

$\frac{1}{a}+\frac{1}{b}=\frac{p}{10^n}$,

I reached the equation:

$10^{n-log(p)} = \frac{ab}{a+b}$.

Now given the positive integer $n$, for what integer values of $p$ would the value of:

$10^{n-log(p)}$,

be rational?

Also, given positive integers $n$ and $p$, how would we find positive integer solutions to $a$ and $b$ that satisfy the second equation, where:

$a ≤ b$,

And is it possible to determine, given $n$ and $p$, how many $a$ and $b$ solutions exist?

• $10^{n - \log p} = \frac{10^n}{p}$ is always rational. – Qiaochu Yuan Aug 18 '12 at 7:00
• This is Project Euler problem 157 – Mike Aug 18 '12 at 7:48
• And we have been asked not to discuss Project Euler problems. (base-10 logarithms? really??) – Gerry Myerson Aug 18 '12 at 10:23
• Yes it is, but no where in my question did I ask for an answer to the problem, I asked specifically for integer solutions when given $n$ and $p$. My actual question is purely mathematical. – Khaled Aug 18 '12 at 12:02
• We care because we are decent human beings. All I can do is point you to the discussions we've had. If they don't convince you, nothing I add is likely to convince you. Anyway, this isn't the place to discuss it. Open a thread on meta, if you want to pursue these questions. – Gerry Myerson Aug 18 '12 at 13:17

As @Qiaochu Yuan noted, $10^{n-\log p}=\dfrac{10^n}{p}$ is always a rational number.

Suppose that a positive integer $n$ and an integr $p$ are given, and let $a$ and $b$ to be integers satisfying the above relation:

$$\dfrac{1}{a}+\dfrac{1}{b}=\dfrac{p}{10^n} \Longleftrightarrow \\ pab = 10^na + 10^nb \Longleftrightarrow \\ p^2ab = 10^npa + 10^npb \Longleftrightarrow \\ p^2ab - 10^npa - 10^npb = 0 \Longleftrightarrow \\ p^2ab - 10^npa - 10^npb + 10^{2n} = 10^{2n} \Longleftrightarrow \\ (pa - 10^n) (pb - 10^n) = 10^{2n} .$$

notice that both of the factors $(pa - 10^n)$ and $(pb - 10^n)$ are (positive or negative) divisor of $10^{2n}$, so we can conclude that there is a (positive or negative) divisor $d$ of $10^{2n}$; such that:

$$(pa - 10^n)=d \ \ \ \ \ \ \text{and} \ \ \ \ \ \ (pb - 10^n)=\dfrac{10^{2n}}{d} \ \ \ \ \ \ \Longleftrightarrow$$

$$a = \dfrac {d+10^n} {p} \ \ \ \ \ \ \text{and} \ \ \ \ \ \ b = \dfrac { \dfrac{10^{2n}}{d} +10^n} {p} \ \ \ \ \ \ .$$

• divisors of $n$, or of $10^{2n}$ ? – G Cab Aug 17 '17 at 15:35
• @G Cab , Yes; you are right, it must be $10^{2n}$; not $n$. I have been edited that. Thank you so much. – Davood KHAJEHPOUR Aug 17 '17 at 15:38

First of all we shall reduce the RHS fraction, so $$\bbox[lightyellow] { {1 \over a} + {1 \over b} = {p \over {10^{\,n} }} = {{p/\gcd (p,10^{\,n} )} \over {10^{\,n} /\gcd (p,10^{\,n} )}} = {q \over A} }$$

Then we have that \bbox[lightyellow] { \eqalign{ & {A \over a} + {A \over b} = q\quad \Rightarrow \cr & \Rightarrow \quad \left\lfloor {{A \over a}} \right\rfloor + \left\lfloor {{A \over b}} \right\rfloor + \left\{ {{A \over a}} \right\} + \left\{ {{A \over b}} \right\} = q\quad \Rightarrow \cr & \Rightarrow \quad \left[ \matrix{ \left( {\left\{ {{A \over a}} \right\} = 0} \right)\; \wedge \;\left( {\left\{ {{A \over b}} \right\} = 0} \right)\; \wedge \;\left( {\;\left\lfloor {{A \over a}} \right\rfloor + \left\lfloor {{A \over b}} \right\rfloor = q} \right)\quad \quad (1) \hfill \cr \quad \quad \vee \hfill \cr \left( {\left\{ {{A \over a}} \right\} + \left\{ {{A \over b}} \right\} = 1} \right)\; \wedge \;\left( {\;\left\lfloor {{A \over a}} \right\rfloor + \left\lfloor {{A \over b}} \right\rfloor = q - 1} \right)\quad \quad \quad \;\;(2) \hfill \cr} \right. \cr} } where $x = \left\lfloor x \right\rfloor + \left\{ x \right\}$ is the decomposition into floor and fractional part

Now the first condition gives $$\bbox[lightyellow] { \left( {c\backslash A} \right)\; \wedge \;\left( {d\backslash A} \right)\; \wedge \;\left( {\;c + d = q} \right)\quad \Rightarrow \quad \left\{ \matrix{ a = A/c \hfill \cr b = A/d \hfill \cr} \right .\quad\quad (1) }$$ i.e., if there are divisors of $A$ summing to $q$, then we can get $a$ and $b$ as thei quotient of $A$ with such divisors.

The second condition translates to $$\bbox[lightyellow] { \left( {{{A\bmod a} \over a} + {{A\bmod b} \over b} = 1} \right)\; \wedge \;\left( {\;\left\lfloor {{A \over a}} \right\rfloor + \left\lfloor {{A \over b}} \right\rfloor = q - 1} \right)\quad \quad \quad \;\;(2) }$$ and there is not much more to manage.