# How to check Diophantine equation modulo prime divisors

I have a Diophantine equation $$-900x^2 + y^2 + 1842300 = 0$$ and I would like to find if it has solutions (not the actual solutions, just check if a solution exists). I was told that all I need to do is check the equation modulo the prime divisors of $900$. The prime divisors are $2^2$, $3^2$, and $5^2$ but I'm not real sure how to "check" it.

It looks like $$y^2 + 1842300 \equiv 0 \mod 900$$ so do I start with $2$ and plug in $0$ and $1$ to see if I get $0$ (mod $2$), then go on to $3$ (trying $0$, $1$, and $2$) and then on to $5$ if it is not?

I'm trying to write a program that will determine if $-900x^2 + y^2 + a = 0$ has solutions for a given $a$.

• $(y-30x)(y+30x)=-a$, so I'd factor $-a$ and look among the factors for $c,d$ such that $cd=-a$ and $60\mid c-d$. – Gerry Myerson Oct 25 '16 at 6:24
• It isn't clear to me why checking modulo the prime factors of $900$ is sufficient. – Greg Martin Oct 25 '16 at 7:14

Since $900$ divides $1842300$, we know that $900$ divides $y^2$, so $30$ divides $y$. Say $y=30z$. Divide the equation by $900$ to get
$$z^2-x^2 = 2047.$$
Since every odd number is the difference of two squares, you are guaranteed solutions. Use the method of Fermat factorization on $2047$ to find them. I, also, don't understand the hint about prime divisors of 900.
$$y^2-900x^2+1842300=0\Rightarrow y=900k\text{ and }(x+k)(x-k)=23\cdot89$$ Proving with $$x+k=89\\x-k=23$$ we get $$2x=112\Rightarrow x=56\\2k=66\Rightarrow k=33$$ Now $$x+k=2047\\x-k=1$$ gives $$x=1024\\k=1023$$