MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
Often the answer to this kind of question is 'no, it is not much easier than factorin' see for example here… . This is of course not exactly what you are asking for, but perhaps sufficiently related to be useful. – user9072 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
See also… – Peter Shor Mar 18 '11 at 16:37
up vote 11 down vote accepted

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.

share|cite|improve this answer
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.

Gerhard "Ask Me About System Design" Paseman, 2011.03.16

share|cite|improve this answer
Thanks, but i was thinking if there exists any method not involving factorisation.. – pranay Mar 17 '11 at 2:02
How are you going to list all the divisors without factorizing? A complete list of divisors + AKS = prime factorization, so I don't think you can avoid this. – David Hansen Mar 17 '11 at 2:26
I don't need a list of all the divisors, just a list of all the prime divisors (with multiplicity). That is tantamount to factoring the number, but is not the same as computing the list of all divisors. I suggest a method that does not need the list of all the divisors. (Also, I need to change a q to a p). There may be a method to compute quickly the parity of the number of 4k+3 divisors, but the answer is still going to be 0 or about half the number of divisors of the given number n, assuming n is odd. Gerhard "Ask Me About System Design" Paseman, 2011.03.16 – Gerhard Paseman Mar 17 '11 at 5:59
Actually, there is a way for odd n which does not involve full factorization. First, consult an oracle which (correctly) gives you the number of factors of n. Second, consult another oracle which (correctly) tells you if at least one of the factors is of the form 4k+3. Then the number of factors of the form 4k+3 will be 0 or floor(d/2), where d is the number of divisors of n, and where you need the second oracle to determine which. For even n, keep dividing by 2 first, and record the number of such divisions. Gerhard "Ask Others Directions to Delphi" Paseman, 2011.03.16 – Gerhard Paseman Mar 17 '11 at 6:07
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.