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


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)

  • $\begingroup$ @Travis Edited. I hope it is clearer now. $\endgroup$ – tatan Nov 1 '18 at 13:59
  • $\begingroup$ math.stackexchange.com/questions/2191177/… $\endgroup$ – lab bhattacharjee Nov 1 '18 at 14:01
  • $\begingroup$ @labbhattacharjee Thanks ;-) $\endgroup$ – tatan Nov 1 '18 at 14:03
  • $\begingroup$ 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$. $\endgroup$ – Servaes Nov 1 '18 at 14:04
  • $\begingroup$ 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. $\endgroup$ – TonyK Nov 27 '18 at 0:30

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

  • $\begingroup$ 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? $\endgroup$ – tatan Nov 1 '18 at 14:03
  • $\begingroup$ 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. $\endgroup$ – Servaes Nov 1 '18 at 14:05
  • $\begingroup$ 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? $\endgroup$ – tatan Nov 1 '18 at 14:06
  • $\begingroup$ 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. $\endgroup$ – Servaes Nov 1 '18 at 14:13
  • $\begingroup$ Thanks for your input ;-) $\endgroup$ – tatan Nov 1 '18 at 14:15


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


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