I am trying to complete a coding challenge where, given a number, $n$, I need to create a program to output the $n^{th}$ prime number, $p$, for which there exists an integer, $x$, such that $x^2 - 2$ is evenly divisible by $p$.
For my first attempt to solve this problem, I created a program which started with $x = 2$ and then performed the following steps, increasing $x$ after each step:
- Calculate $x^2 - 2$
- Find the prime factorization for $x^2 - 2$
- Add the prime factors to a list, ignoring duplicates already on the list
- Sort the list in ascending order
While I was not expecting this program to actually function as a viable solution, I had hoped that looking at the list might give me some insight into the properties of the prime numbers which satisfy the condition of the challenge, but unfortunately it didn't bring me much closer to the solution, as it became evident that there were a lot of gaps in my list.
I then began researching relationships between prime numbers and perfect squares, and although it's clear that there are interesting relationships (for example, all prime numbers other than 2 can be expressed as the sum of two perfect squares), I have as yet been unable to find a relationship that helps me solve my problem.
I understand that the solution will likely involve interating through prime numbers in order, and testing whether each prime number satisfies the given condition, but I have been having difficulty with figuring out how to test that.
I'm not looking for someone to write the exact answer for me, as the reason I'm doing the code challenge is to improve my math and programming abilities, however I would appreciate if someone could inform me of a relationship between prime numbers and perfect squares from which I can derive my own solution, or even just direct me to a helpful resource.