Integer factorization: What is the meaning of $d^2 - kc = e^2$

Question

I found an interesting behavior when placing the integer factorization problem in to geometry, I call it pyramid factoring.

Lets assume we have $c$ boxes and we want to order them in to rectangle. The rectangle sides needs to be $$x>=y$$ $$xy=c$$

Here is an illustration of $23*19$ rectangle

Now look what happened when I cut a pyramid from the bottom.

And adding half of it to the rite side

Lets call the pyramid height $a$ and the reminder $b$, such that: $$x =2a-1$$ $$y =a+b$$

So now we can say:

$$c = (2a-1)(a+b)$$

And if we extract $a$, we will get

$$a = \frac{1-2b+\sqrt{4b^2 + 4b + 8c + 1}}{4}$$

I ignored the negative solution here. But we can keep going. Lets see for what $b$ values the determinate will be an integer value? $$4b^2 + 4b + 8c + 1 = d^2$$

• $d$ is the determinant integer value we are searching for

When extracting $b$ we are getting

$$b = \frac{-1+\sqrt{d^2 - 8c}}{2}$$

And as before, lets see when the determinant is a positive value?

$$d^2 - 8c = e^2$$

And in our example

$$61^2-8*19*23 =15^2$$

Solving this equation is as hard as finding the factors of $c$, or at least this is what I though...

What we know about $d$?

• it's easy can be seen that $d$ is a odd value

Also if we compare $d$ to $a$ we get the next thing

$$a = \frac{1-2b+d}{4}$$ $$d = 2(a + b) - (2a-1)-2$$ $$d = 2y - x - 2$$

So we can say

$$0<2y-d-1<y<=\sqrt{c}<=x$$ $$0<d<3\sqrt{c}$$

And considering all we can say

$$8c<d^2<9c$$

I been lucky to find this equation, so I been trying to see if there are such relationships with different multiplier of $c$, and I found few examples for that

$$d^2 - kc = e^2$$ $$kc<d^2<(k+1)c$$

for $k = 32$

$$c = 423107= 523* 809$$ $$3710^2 - kc = 474^2$$

for $k = 15$

$$c = 590917= 643* 919$$ $$2986^2 - kc = 229^2$$

So what is the rule here? How can I select a multiplier? And how can I extract the x,y from it if I find $d$?

Answer 1

It seems you are studying a version of Pell's equation:

Around AD 250, Diophantus considered the equation

$a^2 x^2 + c = y^2 $, where a and c are fixed numbers and x and y are the variables to be solved for. This equation is different in form from Pell's equation but equivalent to it. Diophantus solved the equation for (a,c) equal to (1,1), (1,−1), (1,12), and (3,9)

Pell's equation (in your version and in the standard version) has been studied extensively and has numerous interesting geometric and number-theoretic properties, including the ability to use one or more solutions to get more solutions. For more background, read: http://www2.math.ou.edu/~kmartin/nti/chap5.pdf

and this page with some nifty tools: http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/pell4.html

Answer 2

If $k = 1$, you've got:
$$d = \frac{c+1}{2}$$
$$e = \frac{c-1}{2}$$

As well as:
$$d = \frac{x+y}{2}$$ $$e = \frac{x-y}{2}$$

More generally, for $k = f1*f2*f3...fn$:
Make two numbers $m_1$ and $m_2$ as products of all factors of $k$ and $c$.

Taking appropriate $m_1$ and $m_2$, such that $m_1m_2 = kc$ then:
$$d = \frac{m_1+m_2}{2}$$
$$e = \frac{m1-m2}{2}$$

For example, taking $c = 590917$ and $k = 15$, we can make $m_1 = 643*5$ and $m2 = 919*3$.
From this we get:
$$d = \frac{643*5 + 919*3}{2} = 2986$$ $$e = \frac{643*5 - 919*3}{2} = 229$$