0

Consider the following diophantine equation.

$$x^2 - a^2y^2 = -4n$$ $a$ and n are positive integers and $n$ is a large semi prime whose factors are not readily available. If the factors of n were known we could fairly quickly solve this equation. Could someone please shed some light on how to go about solving this problem assuming one can't quickly factor $n$.

One could reduce the original equation to (x+ay)(x-ay) = -4n but how to proceed from here assuming that n cannot be readily factored.

Ashwin Thyagarajan
  • 9
  • I am not that advanced, but couldn't you maybe substitute $a$ with $a^2$? It would make it a lot more clear. (Prior to that, maybe you could substitute $a^2y^2$ with $(ay)^2$?) Might work, might not. – Xetrov Mar 13 '17 at 16:24
  • please edit your comment with LaTeX, and correct any mistakes, or it will unfortunately have to be flagged as unclear. There are severe mistakes within it. – Xetrov Mar 13 '17 at 16:45
  • ok i just edited the question as per your suggest @simplest_mathematics – Ashwin Thyagarajan Mar 13 '17 at 16:47
  • Also, it doesn't matter, because a verified equation is valid for whatever other forms it takes. – Xetrov Mar 13 '17 at 16:47
  • The title needs editing as well. Also, I agree with your original comment, which you could also work in your answer. – Xetrov Mar 13 '17 at 16:48
  • Find x in terms of y and others. – Xetrov Mar 13 '17 at 16:55
  • How would that lead to a solution? @simplest_mathematics – Ashwin Thyagarajan Mar 13 '17 at 17:00
  • It would substitute into a single variabled equation. – Xetrov Mar 13 '17 at 17:03
  • There are two unknowns here x and y. How could you possibly reduce this to a single variable equation? @simplest_mathematics – Ashwin Thyagarajan Mar 13 '17 at 17:04
  • Solving this equation with $a=1$ is equivalent to factoring $-4n$, at least up to powers of $2$. So if $n$ cannot be readily factored, then there's no way to solve such problems (at least without a breakthrough in factorization algorithms). At best, you might be able to show that there are no solutions by looking modulo prime factors of $a$. – Greg Martin Mar 13 '17 at 17:44
  • That is a neat observation. How about when a =6 and if I already knew a solution. Could I derive more solutions from just simply knowing a single solution? I know this is possible when D is not a square but does not seem to hold when D is a perfect square. @GregMartin – Ashwin Thyagarajan Mar 13 '17 at 18:09
  • No, the Pell-equation machinery when $D$ is a nonsquare fails in this case (reducible and irreducible quadratics are genuinely different objects). Of course, knowing one solution gives you a partial factorization of $-4n$, which might make it easier to find fuller factorizations and thus additional solutions. – Greg Martin Mar 13 '17 at 19:13
  • Thanks for your answer. If n = 8051 and a =6, how would you obtain a partial factorization of 8051.One of the solutions of the equations is x = 8050, y = 1342. @GregMartin – Ashwin Thyagarajan Mar 13 '17 at 19:35
  • $-4n=x^2-a^2y^2=(x-ay)(x+ay)$. You're basically rediscovering Fermat's method of factorization, but with extra constraints. – Greg Martin Mar 13 '17 at 20:16

1 Answers1

0

Yes, you can solve it easy without the need to factor $n$ by simply factoring $-4 n$ which can be factored in pairs as $(-1,4 n)$ ,$(-2,2 n)$ ,$(-4,n)$,$(1,-4 n)$,$(2,-2 n)$ and $(4,-n)$, but surly without knowing the factors of $n$ you will miss a couple of valid answer, lets move on : for example , given $a=3 ,n =77 =7*11$ but we don't know that $77=7*11$ for the sake of giving you the answer you are looking for.

so you have two linear diophantine equation which can be solved using Extended Euclid algorithm which are :

$x + a y = 4*77$ and $x-a y=-1$ which have no integer solutions.

or

$x + a y = 2*77$ and $x-a y=-2$ which have a solution $x=76,y=26$

or

$x + a y = 1*77$ and $x-a y=-4$ which have no integer solutions.

or

$x + a y = -4*77$ and $x-a y=1$ which have no integer solutions.

or

$x + a y = -2*77$ and $x-a y=2$ which have a solution $x=-76,y=-26$

or

$x + a y = -1*77$ and $x-a y=4$ which have no integer solutions.

now if you do it for different $a$ and $n$ and the $6$ linear equations did not produces a solution, that does not necessarily mean the $x^2-a^2 y^2 =-4 n$ does not have a solution, it just say that we don't know how to factor integers in fast(polynomial time) way.

Ahmad
  • 1,380
  • 1
  • 18
  • 37