# Given $a + \sqrt{b}$ with positive integer $a,b$, find $a$ and $b$?

Suppose I had $n = a + \sqrt{b}$ as a decimal of arbitrary precision, but didn't know $a$ or $b$, except that they are positive integers.

If I had just $\sqrt{b}$, I could just square it and end up with something very close to an integer, so I'd have $b$.

If I take $n^2 - 2an$, I get $(a^2 + b + 2a\sqrt{b}) - (2a^2 + 2a\sqrt{b}) = b - a^2$ which will be an integer, but I don't have $a$...

Is there some way to take the sum of the integral and decimal portion of $n$ and do some integer voodoo there?

Thanks for any ideas.

-
What does it mean to know something "as a decimal of arbitrary precision"? –  Chris Eagle Nov 26 '12 at 11:27
Just that I can acquire it, perhaps through Newton's method, to any place value. For example 5+sqrt(3) = 6.7320508.... and I can keep going. –  Dan Nov 26 '12 at 11:29
Could you give us an explicit $n$ that you have in mind? –  lhf Nov 26 '12 at 11:58
What about $n = 3 = 2 + \sqrt{1} = 1 + \sqrt{4}$? Do you assume that $b$ is not a square? –  huon-dbaupp Nov 26 '12 at 15:03

You can calculate its continued fraction. Being a quadratic irrational, its continued fraction will be periodic. Once you have the period, you can work out $a$ and $b$ exactly.

EDIT: Probably a better method is to calculate the square of your number and then use an algorithm like PSLQ to look for a vanishing integer-linear combination of $1$, the number, and its square.

-
How exactly do you know when you have the period? –  Chris Eagle Nov 26 '12 at 11:32
When you see a repetition, you assume you have the period, you calculate $a$ and $b$ based on this assumption, then you check to see whether you were right by computing a few hundred more decimal places. Look, the problem is clearly not a terribly practical one, we have to make some assumptions to make a go of it. –  Gerry Myerson Nov 26 '12 at 11:37
Is this a special solution? Or would it work for other powers and more complex combinations, a/b + c*d^e etc? –  Dan Nov 26 '12 at 11:39
Yes, the Inverse Symbolic Calculator is essentially an algorithm for finding these integer-linear combinations, supplemented with some table look-up. –  Gerry Myerson Nov 26 '12 at 11:55
since a,b are positive integers the continued fraction will have period $< 2n$. –  user50336 Nov 26 '12 at 14:03

Using that $\sqrt{b}=\lfloor\sqrt{b}\rfloor+\{\sqrt{b}\}$, we get that $\{\sqrt{b}\}$ satisfies the following: $$\{\sqrt{b}\}^2+2\{\sqrt{b}\}\lfloor\sqrt{b}\rfloor+\lfloor\sqrt{b}\rfloor^2=b$$ and in particular it satisfies a relation of the form $\{\sqrt{b}\}^2+m\{\sqrt{b}\}=k$ for some positive integers $m,k$ (you can just check all $m$ up to $2n$ to find the solution). By irrationality of $\sqrt{b}$ (if it's not irrational, then the problem is unsolvable anyway), there is only one solution and once you have it, $\lfloor\sqrt{b}\rfloor$ must be $\frac{m}{2}$ and $k$'ll be $b-\lfloor\sqrt{b}\rfloor^2$, so $b$'ll be $k+\frac{m^2}{4}$.

-

Clearly $a \leq n$ and $b \leq n^2$ so you have only got finitely many possibilities to try. Compute the value of $x+\sqrt{y}$ to 100 decimals (say) for all positive integers $x,y$ such that $x\leq n$ and $y \leq n^2$. (You only need an upper bound for $n$ and $n^2$ here.) Also compute $n$ to 100 decimals. If you are lucky there is now only one combination of $x,y$ such that $x+\sqrt{y}$ could be equal to $n$. Then $a=x$ and $b=y$. Otherwise you double the number of digits you compute. Repeat as long as necessary.

-

Assuming that the integer part of $n$ is $N$, then you need to try the following

for $k=1$ to $N$

store smallest fractional part of ${(N-k)}^2$

(note if the smallest fractional part is $>0$ for example, $0.001$, then you would store that, and if it is close to $1$, for example, $0.998$, you would store $1-0.998=0.002$)

The $k$ that gave you the smallest value is your $a$.

-