Let $L_1$ and $L_2$ be the following:
$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$
$L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$
Claim $L_1 \leq_P L_2$
Sketch Proof
If I want to know whether $r\in L_1$.
The number of integer solutions to $x^2+y^2=r$ is given by
$g(r)=\sum_{d|r}{\chi{(d)}}$ where $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$
Then $L_1=\{r: g(r)\neq 0\}$. So then to answer is "$r\in L_1$?" is at most as hard to answer as "what are the divisors of $r$?"
$\square$
What I would like to know is if this is true the other way around. Is it true that if I had a machine which could tell me in constant time whether $r\in L_1$ could I create a machine which could answer "is $(M,N)\in L_2$?" in polynomial time?
Motivations
This question came out of a discussion on this question.
Apologies I am really just a math.se member who has gotten lost and wandered on to cs.se. Let me know if my question is clear and up to the standards of this site. I am happy to make corrections.