Suppose $n$ is a large odd integer. Let $D\_1(n)$ be the number of divisors of $n$ of the form $4k+1$ and let $D\_3(n)$ be the number of divisors of the form $4k+3$. I would like to compute $(D\_1(n),D\_3(n))$. 


As Joe Silverman points out, the number of representations of $n$ as a sum of two squares of integers is $4(D\_1(n)-D\_3(n))$. For example, $D\_1(225)=6$ and $D\_3(225)=3$, so there are $4(6-3)=12$ lattice points on the circle of radius $\sqrt {225}$ centered at the origin including $(0,15)$ and $(-9,-12)$.



> 
> Is there a faster way to find $(D\_1(n),D\_3(n))$ than factoring $n$?
> 
> 
> 




---


Original:


Hi, one way to do so is to list all the divisors of the integer and check each if it is of the form $4n+1$ or $4n+3$. 
Is there any faster method to it, especially for large $n$?



Number of divisors of an integer of form 4n+1 and 4n+3
Not quite what you're asking, but an interesting theorem of Legendre's says that the number of ways of writing an integer $N$ as a sum of two squares is $4D\_1(N)-4D\_3(N)$, where $D\_1(N)$ is the number of positive divisors of $N$ that are congruent to 1 modulo 4 and $D\_3(N)$ is the number of positive divisors of $N$ that are congruent to 3 modulo 4. There are undoubtedly also results proved via analytic methods that describe the distribution of $D\_1(N)$ and $D\_3(N)$. But I'd have to agree with the other posters that computing $D\_1(N)$ and $D\_3(N)$ for a specific $N$ sounds about as hard as factoring $N$. Indeed, if $N=pq\equiv 1 \pmod{4}$, computing $D\_1(N)$ is equivalent to computing the first bit in the factors of $N$, which seems hard.


