# [seqfan] Re: Help with sequence

David Wilson dwilson at gambitcomm.com
Wed Aug 26 14:54:45 CEST 2009

```Ok. Not being well-versed in the local-global principle, I will cease to
contribute here.

andrew at nevercenter.com wrote:
> 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.
>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>

```