Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I am working on a number theory project and I am interested in the following statement:

What is the probability that an integer $x$ has the property that $|x| \equiv 3 \mod{4}$?

This seems equivalent to me as asking, what is the probability that the Legendre symbol $\left(\frac{-1}{p}\right) = -1$, by Quadratic Reciprocity.

Additionally, since we know from the integers that the probability a number in $\mathbb{Z}$ is divisible by a prime $p$ is $1/p$, can we say that the probability that a Gaussian integer, $a + bi \in \mathbb{Z}[i]$ with $a,b \neq 0$, is divisible by a Gaussian prime is $1/(a^2 + b^2)$? (Notice the theorem regarding Gaussian primes here: Gaussian Primes).

These may seem like disjoint questions, but they are related to the fact that the probability that two gaussian integers are coprime involves the zeta function.

share|cite|improve this question
@Marvis: I suppose my probability measure would be the same as the one presented here:… – Samuel Reid Mar 30 '13 at 19:30
@Marvis That isn't a probability measure, since a probability measure has to be countably additive. That is just a density measure. – Thomas Andrews Mar 30 '13 at 19:43
@SamuelReid That example is also not a probability measure, unfortunately. There is no probability measure on a countable set that is uniform. What that theorem reaslly says is that if $N$ is large and we pick two random integers from $1$ to $N$, the probability that the two numbers are relative prime approaches $\frac{6}{\pi^2}$ as $N\to\infty$. – Thomas Andrews Mar 30 '13 at 19:45
Also, the Legendre symbol is not defined unless $p$ is prime. It is actually the Jacobian symbol when the "bottom" might be composite. – Thomas Andrews Mar 30 '13 at 19:47
@ThomasAndrews Yes. Thanks for pointing it out. Will delete the comment. – user17762 Mar 30 '13 at 19:48
up vote 1 down vote accepted

The probability that a rational integer (i.e. in $\bf Z$) has residue $r$ modulo $n$ is $1/n$, since the probability attached to each residue is equal and there are $n$ residues. Here we are using an asymptotic notion of "probability distribution" as mentioned in the comments.

Similarly, in any number field $K/{\bf Q}$ with ring of integers ${\cal O}_K$ and ideal ${\frak n}\triangleleft {\cal O}_K$, any intuitively nice asymptotic notion of density would be translation-invariant, so the probability an integer $\in{\cal O}_K$ would be in a fixed residue $r$ mod $\frak n$ (i.e. congruent to $r+{\frak n}$ in the quotient ${\cal O}_K/{\frak n}$) is the same for every choice of $r$, and hence is equal to the reciprocal of the number of equivalence classes, which is the order $|{\cal O}_K/{\frak n}|$ of the quotient, which is (by definition) the norm $N({\frak n})$ of $\frak n$. If ${\frak n}=(n)$ is a principal ideal generated by some integer $n\in{\cal O}_K$, then $N({\frak n})=N_{K/{\bf Q}}(n)$ is the norm of $n$ (this is a fact from algebraic number theory). This is indeed $a^2+b^2$ for $n=a+bi\in\href{}{{\bf Z}[i]}={\cal O}_{{\bf Q}(i)}$.

The same heuristic for deducing that the probability two rational integers are coprime works for computing the probability two integers $\in{\cal O}_K$ of a number field $K$ are coprime (with the caveat that $\cal O$ is a UFD). Originally, we assume that the events "being divisible by the prime $p$" for distinct $p$ are independent, and two numbers are coprime iff for each prime $p$ it is not the case that both are divisible by $p$ (which has probability $1/p^2$), so the probability two rational integers are coprime is given by the Euler product factorization associated with the Riemann zeta function:


Similarly, the probability two integers in ${\cal O}_K$ are coprime is

$$\prod_{\frak p}\left(1-\frac{1}{N({\frak p})^2}\right)=\frac{1}{\zeta_K(2)}.$$

See Dedekind zeta function.

On Mathworld, for Gaussian and Eisenstein integers the probabilities are listed in closed form.

share|cite|improve this answer
Do you have a reference for a proof of your last claim regarding the probability two integers in $\mathcal{O}_{K}$ are coprime? – Samuel Reid Mar 30 '13 at 21:13
@SamuelReid Unfortunately, no, I don't have one. I've only seen the claim mentioned in passing by mathematicians, but I follow the heuristic argument easily enough. The formal proof should begin as follows: the probability two integers with norm $\le n$ are coprime, by inclusion-exclusion principle, is $$\sum_{\frak n}(-1)^{\mu({\frak n})} \ell^{-1}\lfloor\ell/N({\frak n})^2\rfloor$$ where $\ell=\#\{x\in{\cal O}:N(x)\le n\}$ and the (finite) sum is taken over ideals of the form $\frak n={\frak p}_1\cdots{\frak p}_{\rm k}$, the ${\frak p}_i$s distinct and $\mu({\frak n}):=k$, with norm $\le n$. – anon Mar 30 '13 at 21:41

From my comment above, now relocated here:

There are four equivalence classes modulo $4$. Every integer falls into one of those equivalence classes. The equivalence class $[3] = \{n: n = 4k + 3, k\in \mathbb Z\}$. Every fourth integer belongs to $[3]$; that is, consecutive integers map cyclicly into one of four equivalence classes: $$4k \mapsto [0], \;\; 4k+1 \mapsto [1], \;\; 4k + 2 \mapsto [2], \;\; 4k + 3 \mapsto [3],\;\; 4k+ 4 = 4(k+1) \mapsto [0], \cdots$$

Hence the probability that an integer is equivalent to $3 \pmod 4$ is no more than probability of that integer belonging to one of four equivalence classes: probability $\;\large \frac 14$.

I am not at all clear as to how this relates to your second question.

share|cite|improve this answer
I'll accept your answer if you can answer a follow-up question: What is the probability that a prime number $p$ has $p \equiv 3 \mod{4}$, this would be equivalent to answering my question about the zeta function, I'll make a post about how they are connected as an answer after. – Samuel Reid Mar 30 '13 at 20:33
@SamuelReid That is actually not as trivial to answer - it is a strong version of Dirichlet's theorem on primes in arithmetic progressions, a theorem which involves heavy analytic-number-theoretic machinery rather than just observation of translation-invariance of density - though the format of the answer is the same: the probability a prime is congruent to $r$ mod $n$ is $0$ if $r,n$ are not coprime and $1/|({\bf Z}/n{\bf Z})^\times|$ otherwise. Also see – anon Mar 30 '13 at 20:37
Thanks, anon! I hope it helps. – amWhy Mar 30 '13 at 20:39
@amWhy: Yes, I learned a lot from both responses, thank you very much! – Samuel Reid Mar 30 '13 at 23:31

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.