If we do not know a number's factors, what is the algorithm (if there is one) to write it as a difference of two squares?

Question

For example, if we have a number like 29873412895, is there an algorithm that can find it as a difference of two squares? Or must you need the factors of the numbers? And what might be the algorithm? Thanks!

Apologies for my previous post, in which I acted very callous.

Answer 1

You don't need to factorise anything. Every positive integer can be expressed as one of the following:

• $2n+1$
• $4n+2$
• $4n$

The first and third are differences of two squares:

• $2n+1=(n+1)^2-n^2$
• $4n = (n+1)^2-(n-1)^2$

Numbers of the second form can't be expressed as the difference of two squares (because every square is equal to $0$ or $1$ mod $4$, so we can't subtract one from another to get $2$ mod $4$).

Answer 2

If $k=2n+1$ is an odd number, then $k=(n+1)^2-n^2$. Finding other ways is esentially the same as factoring the number.