6
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – user9072
    Commented Mar 17, 2011 at 2:08
  • $\begingroup$ I don't understand the votes to close. Am I missing something? $\endgroup$
    – Douglas Zare
    Commented Mar 17, 2011 at 13:20
  • $\begingroup$ Douglas: I have not voted to close, but I find it a bit difficult to tell exactly what the asker is asking. $\endgroup$
    – Michael Lugo
    Commented Mar 17, 2011 at 23:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Mar 18, 2011 at 15:57
  • 2
    $\begingroup$ See also mathoverflow.net/questions/57981/… $\endgroup$
    – Peter Shor
    Commented Mar 18, 2011 at 16:37

2 Answers 2

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot :) , i too found the same solution in one of the books . $\endgroup$
    – pranay
    Commented Mar 22, 2011 at 11:56
3
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks, but i was thinking if there exists any method not involving factorisation.. $\endgroup$
    – pranay
    Commented Mar 17, 2011 at 2:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Hansen
    Commented Mar 17, 2011 at 2:26
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 17, 2011 at 5:59
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 17, 2011 at 6:07
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Mar 17, 2011 at 13:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .