Proof of Bhaskara's lemma

Bhaskara's Lemma is an identity used as a lemma during the chakravala method. It states that:

$\, Nx^2 + k = y^2\implies \,N\left(\frac{mx + y}{k}\right)^2 + \frac{m^2 - N}{k} = \left(\frac{my + Nx}{k}\right)^2.$

[edit] Proof

We begin with an identity, verified by expansion (or substitution into the Brahmagupta-Fibonacci identity with $a=m,c=y,b=i\sqrt{N},c=ix\sqrt{N}$ ) :

$N(mx+y)^2-(my+Nx)^2=-(m^2-N)(y^2-Nx^2)\Longleftrightarrow \frac{N(mx+y)^2-(my+Nx)^2}{y^2-Nx^2}=-(m^2-N)$

Since $y 2 - N x 2 = k$ , we have that:

$\frac{N(mx+y)^2-(my+Nx)^2}{k}=-(m^2-N)\Longleftrightarrow\frac{N(mx+y)^2-(my+Nx)^2}{k^2}=\frac{-(m^2-N)}{k}$

Suitable re-arrangement of this equation yields Bhaskara's Lemma:

$N\left(\frac{mx + y}{k}\right)^2 + \frac{m^2 - N}{k} = \left(\frac{my + Nx}{k}\right)^2$

C. O. Selenius, "Rationale of the chakravala process of Jayadeva and Bhaskara II", Historia Mathematica, 2 (1975), 167-184.
C. O. Selenius, Kettenbruch theoretische Erklarung der zyklischen Methode zur Losung der Bhaskara-Pell-Gleichung, Acta Acad. Abo. Math. Phys. 23 (10) (1963).
George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics (1975).

v • d • e Number-theoretic algorithms

Primality tests	AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm

Other algorithms	Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.