[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
(http://www.alpertron.com.ar/QUAD.HTM) we find that:
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.
More information about the SeqFan
mailing list