You are currently browsing the tag archive for the ‘Gauss’ tag.

John Wilson (1741-1793) was a well-known English mathematician in his time, whose legacy lives on in his eponymous result, Wilson’s Theorem. To recall, this is the statement that an integer n >1 is prime if and only if

(n-1)! \equiv -1 \mod n.

(The “if” part is trivial.) As is the case for many historical results, Wilson’s Theorem was not proven by Wilson. Instead, it was Joseph Lagrange who provided the first proof.

The proof, as we see it today, might be phrased as follows:

Proof: Suppose that p is prime. Then each of the nonzero residues modulo p is a unit, so that (p-1)! represents the product over all units in \mathbb{Z}/p\mathbb{Z}. If

a \not\equiv a^{-1} \mod p,   i.e.    a^2 \not\equiv 1 \mod p,

then a and its inverse each show up in our list of units. We cancel out such terms in pairs, and conclude that

\displaystyle (p-1)! \equiv \prod_{a^2 \equiv 1 (p)} a \mod p.

We have a^2 \equiv 1 \mod p if and only if p \mid (a-1)(a+1), which by primality of p forces p \mid (a-1) or p \mid (a+1). In other words, a \equiv \pm 1 \mod p. It follows that

(p-1)! \equiv 1(-1) \equiv -1 \mod p.


When n is composite, the direct translation of Wilson’s problem gives

(n-1)! \equiv 0 \mod n.

The problem, here, is that we’ve multiplied a number of zero divisors together, which can be avoided by only multiplying across the units, U_n, of \mathbb{Z}/n\mathbb{Z}. In this post, we consider the product

\displaystyle \prod_{a \in U_n} a \mod n,

determine its value, give credit to Gauss for doing so over two centuries ago, and discuss a few generalizations.

Read the rest of this entry »

Let k/\mathbb{Q} be a number field, i.e. a finite field extension to \mathbb{Q}.  We recall that the ring of integers in k, denoted \mathcal{O}_k, is the ring

\mathcal{O}_k := \{\alpha \in k : f(\alpha)=0 \text{ for some monic } f(t) \in \mathbb{Z}[t]\}.

For k= \mathbb{Q}, the ring of integers is just the integers \mathbb{Z}, in which case we recall the  Fundamental Theorem of Arithmetic: that every integer n \neq 0 may be written as a finite product

n=\pm 1\cdot p_1 \cdots p_k,

in which the \{p_i\} are prime and uniquely determined (up to permutation). Domains for which this holds are known in general as unique factorization domains (UFDs). For k = \mathbb{Q}(\sqrt{d}) — with d \neq 0,1 square-free — the ring of integers \mathcal{O}_k will in general not be a UFD.  In fact, for d <0, the integers \mathcal{O}_k have unique factorization only in the 9 cases

d=-1, -2, -3, -7, -11, -19, -43, -67, -163.

Far less is known in the case d >0 (in which case k is known as a real quadratic field), although an unproven conjecture dating back to Gauss suggests that there should be infinitely many real quadratic fields.  More recently, some heuristics stemming from Cohen suggests that the ring of integers in \mathbb{Q}(\sqrt{d}) should be a UFD with probability \approx 0.75446 as d \to \infty on the square-free integers.

Here, we’ll focus on a more tractable variant of this problem:

Question: What can be said about the number \tau(n) of distinct real quadratic fields k=\mathbb{Q}(\sqrt{d}) with d\leq n for which \mathcal{O}_k is not a UFD?

For a weak answer to the question above, we devote the rest of this article to the establishment of the following bound:

Theorem: As n \to \infty, we have

\tau(n) \gg \sqrt{n}\log n,

in which the implied constant is made effective (e.g. greater than 1/11).

Read the rest of this entry »

For what follows, we define a loaded die as a discrete probability distribution with six outcomes (labelled {1,…,6}), each of which has positive probability. To each such die, we associate a generating polynomial, given by

p(t):=p_1t+p_2t^2+\ldots +p_6 t^6

in which p_i denotes the probability of the outcome i.  If q(t) corresponds to another such die, we note that the product

p(t)q(t) =\sum_i a_i t^i:=\sum_{i=2}^{12}\big( \sum_{k=1}^{i-1} p_k q_{i-k}\big) t^i

has coefficients which reflect the probabilities of  certain dice sums for p and (and this is the utility of generating polynomials).  We are now ready to ask the following question:

Question: Does there exist a pair of loaded dice such that the probability of rolling any dice sum ({2,…12}) is equally likely?

Read the rest of this entry »