# Number of divisors of an integer of form 4n+1 and 4n+3

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$?

-
Often the answer to this kind of question is 'no, it is not much easier than factorin' see for example here mathoverflow.net/questions/3820/… . This is of course not exactly what you are asking for, but perhaps sufficiently related to be useful. –  quid Mar 17 '11 at 2:08
I don't understand the votes to close. Am I missing something? –  Douglas Zare Mar 17 '11 at 13:20
Douglas: I have not voted to close, but I find it a bit difficult to tell exactly what the asker is asking. –  Michael Lugo Mar 17 '11 at 23:50
I agree that it could be written to be slightly clearer. I do not understand the votes to close as "too localized;" did people misread the question? This appears far from trivial. I am voting to reopen. –  Douglas Zare Mar 18 '11 at 15:57
–  Peter Shor Mar 18 '11 at 16:37

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.

-
Thanks a lot :) , i too found the same solution in one of the books . –  pranay Mar 22 '11 at 11:56

A faster way would involve looking at the prime factorization of the integer. Let n be pq, where q contains all the 1 mod 4 prime factors of n, and q contains all the 3 mod 4 prime factors. Then the number of factors of n which are 3 mod 4 is just the number of factors of q times the number of 3 mod 4 factors of p, which is close to half the number of factors of p. I'll let you finish the details, including the case that n is even.

Factorization is hard, and I do not view it as significantly easier than writing out a list of all divisors. You say consult two oracles. I don't grant you those oracles as building blocks. Is it easier to get that information than factorizing $n$? As "unknown" pointed out, some types of information are expected to be about as hard as factorization. –  Douglas Zare Mar 17 '11 at 13:28