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

$\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
    Mar 17, 2011 at 2:08
  • $\begingroup$ I don't understand the votes to close. Am I missing something? $\endgroup$ 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$ 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$ Mar 18, 2011 at 15:57
  • 2
    $\begingroup$ See also mathoverflow.net/questions/57981/… $\endgroup$
    – Peter Shor
    Mar 18, 2011 at 16:37

2 Answers 2

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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot :) , i too found the same solution in one of the books . $\endgroup$
    – pranay
    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

$\endgroup$
8
  • $\begingroup$ Thanks, but i was thinking if there exists any method not involving factorisation.. $\endgroup$
    – pranay
    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$ 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$ 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$ 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$ Mar 17, 2011 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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