In one step of Chakravala's method, it is necessary to find some positive integer m such that (a+bm)/k is an integer, and |m^2-N| is minimal. a,b,k, and N are known integers.
How do I find m?
I think it's possible to use Bezout's identity for this, but I haven't completely convinced myself.
Rephrase "$(a+bm)/k$ is an integer" to "$(a+bm)/k = g$, and $g$ is an integer". Then rearrange terms to get $kg - bm = a$.
I think we can apply Bezout's identity to that equation if $gcd(k,-b) = a$, but I'm not sure what to do if $gcd(k,-b)\neq a$. This is where I'm stuck now. I thought it might be possible to apply the identity to $kg - bm = gcd(k,b)$, and then multiply the result by a/gcd(k,b), but I think I am missing some valid solutions. For example, 3g-m=8. The Bezout pairs for 3g-m=1 are {-t, -1-3t} for any integer t. So shouldn't the pairs for 3g-m=8 be {-8t, -8-24t}? But then the pair {5,7} isn't among them, even though it is a valid solution. So simply multiplying the formula by 8 is insufficient.
From there, I think we can inspect the Bezout coefficient pairs and derive a linear equation that expresses the valid integral values of m. Then we can determine which value makes |m^2-N| minimal. I suspect this last step is simple, although I haven't done the work yet.
