[seqfan] Re: Congruence question

[Max Alekseyev]

Andrew,

For odd b, we have

(2x+a)^2 - (2y)^2 == a^2 (mod b)

or

(2x+a+2y)(2x+a-2y) == a^2 (mod b)

If a and b are co-prime, all solution to this congruence can be given
in parametric form:

x == (t + a^2*t^(-1) - 2a)/4 (mod b)
y == (t - a^2*t^(-1))/4 (mod b)

where t runs over all residues modulo b.

The other cases are solved similarly.

Regards,
Max

On Mon, May 18, 2009 at 6:35 PM,  <andrew at nevercenter.com> wrote:
> While working on some sequences, I've run into congruences that look like
> this:
>
> x^2 + ax == y^2 mod (b)
>
> where a and b have a known factorization. Are there a.) any "easy"
> (computationally speaking) ways to find solutions for this kind of
> congruence, and b.) does knowing the factors of a and b help at all?
> Thanks!
>
>    -Andrew Plewe-
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>