Integer solutions to $c=a^2-b^2$

Question

I have been working on the following problem:

For a given $c\in \Bbb Z^+$, find $a,b \in \Bbb Z^+: c=a^2-b^2$.

I have already figured out and proved a number of things:

A way to directly determine if a particular instance is solvable: $\exists a,b \in \Bbb Z^+: c=a^2-b^2 \iff c \not\equiv 2 \mod 4$
An upper bound on the values for a (and b): $b \lt a\le\lfloor\frac{c-1}{2}\rfloor$
And a simple algorithm to find a solution:

$$ \begin{align*} (a_0, b_0) &= (0, 0) \\ (a_{n+1}, b_{n+1}) &= \begin{cases} (a_n+1, &b_n&)&\text{if } a_n^2-b_n^2 < c\\ (a_n, &b_n+1&)&\text{if } a_n^2-b_n^2 > c\\ \end{cases} \end{align*} $$

This can be iterated until a solution is found or the upper bound is reached.

I am currently trying to work out a more direct way to find an answer, but I have been unable to figure out any other ways to approach the problem.

How can I more directly find values for $a$ and $b$ for a given value of $c$?

The number of solutions $(a,b)$ can be found,$$\sum_{a^2-b^2=n}{(a,b)\in \mathbb{Z^2}}1=2(-1)^n\sum{d\mid n}(-1)^d$$ — Ethan Splaver, Dec 01 '13 at 20:11
Why do you say "the solution"? Aren't there multiple solutions? — DanielV, Dec 01 '13 at 20:15
Surely this is straight forward...$c = (a-b)(a+b)$ then look at the possible factor pairs $(a\pm b)$ of $c$. — fretty, Dec 01 '13 at 20:25
@fretty you posted the same time I did, I agree this seems very straight forward. — DanielV, Dec 01 '13 at 20:27

score 2 · Accepted Answer · answered Dec 01 '13 at 20:26

2

$$c = a^2 - b^2 = (a - b)(a + b) = X \cdot Y$$

which implies

$$ a = \frac{Y + X} 2$$

$$ b = \frac{Y - X} 2$$

which implies

$$X \equiv Y \pmod 2$$

which is why you get that $X\cdot Y \not \equiv 2 \pmod 4$ by just enumerating the possible values for $X$ and $Y$.

So to find a solution $(a,b)$ given $c$, first factor $c$. Then:

Foreach $X|c$
Y = $\frac c X$
If $X < Y \land X \equiv Y \pmod 2$ Then
<blockquote>
  <p>$ a = \frac{Y + X} 2$<BR>
     $ b = \frac{Y - X} 2$</p>
</blockquote>

answered Dec 01 '13 at 20:26

DanielV

23,556

Thank you! I have learned new things! Most interesting, that for semiprime $c$ that this problem is equivalent to finding its prime factors. – AJMansfield Dec 04 '13 at 00:41
This is the method Fermat used to factor primes. Euclid expanded it to finding $a^2 - b^2 = k\cdot c$, and computing $\gcd(a, c)$. It is the basis of almost all modern factoring algorithms. – DanielV Dec 04 '13 at 17:43

score 1 · Answer 2 · answered Dec 01 '13 at 20:41

If $c=a^2-b^2$, then clearly $a>b$ otherwise $c$ would be negative, so we can write $a=b+k$

Where $k$ is also a positive integer,

Thus we want solutions to $(b+k,b)$ to $c=(b+k)^2-b^2=k(2b+k)$

Now if divide both sides by $k$ we get $\frac{c}{k}=(2b+k)$, so clearly $k|c$

Now subtracting $k$ we get $\frac{c}{k}-k=2b$

Thus all solutions to $(a,b)$ to $c=a^2-b^2$ are given by

$$(a,b)=(\frac{c}{2d}+\frac{d}{2},\frac{c}{2d}-\frac{d}{2})$$

Where $d<\sqrt{c}$ is a divisor of $c$ with $\frac{c}{d}\equiv d \text{ mod 2}$

So once you have run through all such divisors, you will have all the solutions.

Integer solutions to $c=a^2-b^2$

2 Answers2

Linked

Related