Does it possible to show that the Diophantine equation $X^2-Y^2=N$ (N - odd)has no non-trivial solution?
Asked
Active
Viewed 280 times
0
-
No. $(t+1)^2-t^2=2t+1$ is odd. Did you mean maybe $N^2$ instead of $N$? – coffeemath Oct 15 '15 at 15:52
-
For more cases, if $k$ is odd then $(t+k)^2-t^2=2tk+k^2$ is also odd. By the way what does "trivial" mean, does it mean that say $Y=0$? – coffeemath Oct 15 '15 at 16:00
-
1By trivial I mean &X=(N+1)/2; Y=(N-1)/2& – Boris Sklyar Oct 15 '15 at 16:05
-
Boris. OK, see answer below, it seems it may have nontrivial solutions. – coffeemath Oct 15 '15 at 16:13
2 Answers
0
Suppose $N=CD$ where $C,D$ are odd and greater than $1$ and $C<D.$
Then setting $X-Y=C,\ X+Y=D$ gives $X=(D+C)/2,\ Y=(D-C)/2.$ Since these are not $(N \pm 1)/2$ the solution is not "trivial" in the sense of your last comment.
coffeemath
- 29,884
- 2
- 31
- 52
-
-
@Boris Your question didn't say $N$ was a prime. But if it is an odd prime $p,$ then given $X^2-Y^2=(X-Y)(X+Y)=p$ the only possibility is $X-Y=1,X+Y=p$ which leads to the "trivial" situation you formulate in your comment. – coffeemath Oct 15 '15 at 16:24
-
My aim is to use the following statement:
Odd number N is a prime if and only if the Diophantine equation $X^2−Y^2=N$ has no non-trivial solution, for checking primality of N
– Boris Sklyar Oct 15 '15 at 16:33 -
@Boris Then your statement is valid, as shown by the example in my answer a non-prime odd has nontrivial solutions, and if $N$ is prime there is only the trivial solution as just noted. So if that's your aim it is proved. – coffeemath Oct 15 '15 at 16:35
-
But I need to show that for given N there is no non-trivial solution (N - prime) or to show that for given N there is non-trivial solution (N - composite). Does such algorithm exist? – Boris Sklyar Oct 15 '15 at 16:43
-
@Boris Your last question in comment seems strange.. Are you asking if there is an algorithm to decide whether an odd $N$ is prime or composite? If so yes, some algorithms being faster than others. But the above answer and discussion has already shown the question of nontrivial solutions for $N$ is completely equivalent to the question whether $N$ is composite or prime. – coffeemath Oct 15 '15 at 16:55
0
Basically, the equation $$x^2-y^2=N$$ is such that the set of integer solutions $(x,y)\in {\mathbb Z}^2$ has a bijection (given in older posts) with the set of integer solutions $(a,b)$ such that $a \pm b\equiv N (\mbox{mod }2)$ and $$ab=N.$$
Thus, a natural number $N>0$ has no nontrivial solutions if and only if $N$ is a prime number (odd case) or a number $\equiv 2 (\mbox{mod }4)$.
I am merely rephrasing what's been done above, i.e. clearly $a=x-y$, and $b=x+y$.
Theon Alexander
- 1,425