# [seqfan] Re: Help with sequence

andrew at nevercenter.com andrew at nevercenter.com
Wed Aug 26 00:38:38 CEST 2009

```Sorry, allow me to clarify. The idea is to do something like this: take
these equations:

4x^2 + n = y^2
9x^2 + n = y^2
25x^2 + n = y^2

where a = 2^2, 3^2, 5^2, etc.

and solve them mod some number p for a particular value of n. The goal is
to find the right p that demonstrates whether or not each equation has
solutions (i.e., apply the Local-Global principle). Thus we are not
solving the equation directly, just trying to determine if integer
solutions exist for these equations.

For example, let n = 62275151937671. Then, using Dario Alpern's calculator

4x^2 + 62275151937671 = y^2 has no solutions (no solutions mod 16, thus p
= 16)

9x^2 + 62275151937671 = y^2 has no solutions (no solutions mod 3, thus p = 3)

25x^2 + 62275151937671 = y^2 has solutions

49^2 + 62275151937671 = y^2 has solutions

121^2 + 62275151937671 = y^2 has no solutions (no solutions mod 11, thus p
= 11)

and so on.

By doing so we also find out information about the properties of x
(indeed, 5 and 7 are divisors of allowable x values, while 2, 3, and 11
are not). I haven't shown here how you can conclude this, but it's fairly
trivial (it relates to the figurate nature of square numbers).

-Andrew Plewe-

> I don't think you are going to find what you want.
>
> If, for any given a and n, you were quickly able to solve
>
> 	n = y^2 - a^2x^2
>
> then by choosing a = 1, you could quickly solve
>
> 	n = y^2 - x^2
>
> which is the same as solving
>
> 	n = (y + x)(y - x)
>
> This translates to a quick factorization algorithm for n.
>
> In other words, your problem is equivalent to the factorization of n you
> wish to avoid.

```