# Probability that $x \equiv 3 \pmod{4}$

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.

-
@Marvis: I suppose my probability measure would be the same as the one presented here: planetmath.org/… –  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

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{http://en.wikipedia.org/wiki/Gaussian_integer}{{\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:

$$\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}.$$

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)}.$$

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

-
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.

-
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 dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf. –  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