## Panaitopol primes – simple representation

A prime number is called a Panaitopol prime if . I stumbled upon these weird prime numbers while working on problem 291 from Project Euler.

While searching a bit about the problem I did a brute force check to find the first such primes and I found the following values:

Since this was going nowhere I plugged these into the OEIS search engine and bam: it seems they are precisely the primes which can be written in the form . If this latter formulation holds, then the problem can be solved immediately, since searching for primes of the form is much easier than testing the first formula. Now how do we prove this? Suppose , which is equivalent, after simplifying , to

Note that we necessarily have . Now recall that is prime, so if divides we must have which is false, since a positive number cannot divide a number smaller than itself (I leave you the task of seeing why cannot be zero). Therefore it remains that and . Since and it follows that divides and . Therefore we can write

Multiply the first two relations and square the third to get . Furthermore, we have

so . Now let’s see what remains of the initial

Now let’s suppose that and denote . Then we have

Now let’s note that if is a common prime factor of and then it follows immediately that divides , contradicting the choice of above. Therefore we can assume that . This means that, for the above fraction to simplify we need to have . Furthermore, the ratio is strictly greater than . Moreover, so the previous fraction is in fact just . Since is prime, this forces the relation , which, since , gives us

Therefore and for some positive integer . In conclusion

Now if we have we can retrace the construction to find a the corresponding and . Note that in addition to we also have . Choosing we get exactly

nice analysis