# Number of positive integral solutions $(x,y)$ of $x^2-y^2=12345678$ [duplicate]

I have to find out the number of positive integral solutions $$(x,y)$$ of

$$x^2-y^2=12345678$$

Specifically, if $$S$$ is the set of all ordered pairs $$(x,y)$$ then $$S$$ -

A) is an infinite set

B) is the empty set

C) has exactly one element

D) is a finite set and has at least two elements.

Now, with a calculator capable of doing prime factorization, this is an easy question. However without a calculator, its very difficult to find the prime factors by inspection. What is the most efficient and fast solution to such a question.

This question was asked here (Q no. 4)

• @Travis Edited. I hope it is clearer now. – tatan Nov 1 '18 at 13:59
• math.stackexchange.com/questions/2191177/… – lab bhattacharjee Nov 1 '18 at 14:01
• @labbhattacharjee Thanks ;-) – tatan Nov 1 '18 at 14:03
• As a side note; clearly the number is congruent to $2$ mod $4$ and a multiple of $9$. Division yields $$123456789=2\times3^2\times685871.$$ A little patience with trial and error shows that $47$ is also a factor, and the remaining factor $14593$ will take a little more patience than I have right now. But it is doable in a few minutes; just check primes up to $119$. – Servaes Nov 1 '18 at 14:04
• But you don't have to find out the number of solutions, do you? You just have to decide whether there are at least 2. – TonyK Nov 27 '18 at 0:30

Hint: Note that $$12345678\equiv2\pmod{4}$$.

• Thanks a lot! Can you suggest me some general steps I should follow in questions like this. I mean like finding the number of integral solutions to given equations. I mean what intuition drove you to think like this? – tatan Nov 1 '18 at 14:03
• Experience: I've seen a few hundred questions concerning writing things as sums of differences of squares. The first thing to check is remainders mod $3$ and $4$, it solves or simplifies many such questions. – Servaes Nov 1 '18 at 14:05
• If we can counter what we get as mod $3$ or $4$ as in this case we get zero solutions. What if we can't counter? – tatan Nov 1 '18 at 14:06
• This does not make sense; we can counter. If we can't then the question is different, and what approach to take depends heavily on the way the question is different. – Servaes Nov 1 '18 at 14:13
• Thanks for your input ;-) – tatan Nov 1 '18 at 14:15

Hint.

$$12345678 = 1\times 2\times 3^2\times 47\times 14593 = \prod_i a_i^{b_i}$$

then checking the feasible solutions for

$$x+y = \frac{\prod_i a_i^{b_i}}{m_k}\\ x-y = m_k$$

for $$m_k$$ in all possible combinations between the factors, will give us the solution.