# Prime number and square problem

How many pairs of natural numbers, not bigger than 100, are such that difference between that pair is a prime number, and their product is a square of a natural number.
My attempt: I tried writing relationship such as $$x-y=p$$ and $$xy=n^2$$ but I can't seem to find any pattern to enumerate it.

• There are only $9$ squares between $2$ and $100$ and it's not hard to factor them and look at the differences, so if all you care about is this one problem, brute force is the way to go. If this is one instance of the more general problem you should ask about that. There may not be a nice pattern (I haven't looked). – Ethan Bolker May 16 at 11:56
• @EthanBolker, but the squares in question can go up to $10000$, at least a priori. If $x, y \leq 100$ then $xy = n^2 \leq 10000$. – Mees de Vries May 16 at 12:04
• @MeesdeVries You're right. I misread the question. – Ethan Bolker May 16 at 12:34

OK, if you have $$x-y=p$$, then either both $$x$$ and $$y$$ are divisible by $$p$$, or both are not.

If they are not, then $$x$$ and $$y$$ are coprime, and their product being a square, this means they must both be squares themselves: $$x=i^2,\;y=j^2$$, in which case their difference factors nicely to $$(i-j)(i+j)$$ and can only be a prime if $$i=j+1$$. As Ethan noted, there are not awfully many values to check.

If they are, then $$x\over p$$ and $$y\over p$$ are two integers that differ by 1 and hence are also coprime. Notice that their product is $$n^2\over p^2$$, that is, also a square, so they must be squares themselves, but two squares rarely differ by 1.

So it goes.

If $$x - y$$ is prime, then there can be at most one number that divides both $$x$$ and $$y$$, and it has to be that prime. Suppose the prime $$p$$ divides both $$x, y$$. Thus we can write $$x = np$$, and $$y = (n-1)p$$. Then we would have that $$n(n-1)p^2$$ is a square, hence so is $$n(n-1)$$. But $$n, n-1$$ are coprime, so this would mean that both $$n, n-1$$ are squares. This is impossible, so $$p$$ does not divide $$x$$ or $$y$$. It follows that $$x, y$$ are coprime.

Because $$xy$$ is also a square, it follows that $$x, y$$ must be squares individually -- so write $$x = a^2, y = b^2$$. Now a square is a sum of odd numbers, $$a^2 = \sum_{k=1}^a 2k-1,$$ so $$a^2 - b^2 = \sum_{k=b+1}^a 2k-1.$$ But we run into a restriction: if we have a sequence of odd numbers of more than one term, say $$5, 7, 9$$ or $$25, 27$$, then they are a multiple of their average. The first sum equals $$3 \times 7$$ and the second one $$2 \times 26$$. Thus we must have that the sum consists of at most one term, and we have $$a = b+1$$, and the sum is prime if and only if $$2a-1$$ is prime.

In the end your numbers are the $$x, y$$ such that $$x = \left(\frac{p+1}{2}\right)^2$$ and $$y = \left(\frac{p-1}{2}\right)^2$$, where $$p$$ is an odd prime.

You may proceed by reducing it into $$\pmod 4$$. i.e. $$n^2 \equiv 0,1 \pmod 4$$ and $$p \equiv 1,3 \pmod 4$$. So, the reduced problem is $$xy\equiv 0,1 \pmod 4$$ $$x-y\equiv 1,3 \pmod 4$$ From this you may find out $$(x,y)$$.