Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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
2  
See also mathoverflow.net/questions/57981/… –  Peter Shor Mar 18 '11 at 16:37
show 2 more comments

2 Answers

up vote 10 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|improve this answer
    
Thanks a lot :) , i too found the same solution in one of the books . –  pranay Mar 22 '11 at 11:56
add comment

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|improve this answer
    
Thanks, but i was thinking if there exists any method not involving factorisation.. –  pranay Mar 17 '11 at 2:02
2  
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
show 3 more comments

Your Answer

 
discard

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.