0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ $(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$. $\endgroup$ – Gerry Myerson Oct 25 '16 at 6:24
  • $\begingroup$ It isn't clear to me why checking modulo the prime factors of $900$ is sufficient. $\endgroup$ – Greg Martin Oct 25 '16 at 7:14
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$$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$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.