Posts Tagged ‘number-theory’

While teaching a largely student-discovery style elementary number theory course to high schoolers at the Summer@Brown program, we were looking for instructive but interesting problems to challenge our students. By we, I mean Alex Walker, my academic little brother, and me, David Lowry-Duda. After a bit of experimentation with generators and orders, we stumbled across a proof of Wilson’s Theorem, different than the standard proof.

Wilson’s theorem is a classic result of elementary number theory, and is used in some elementary texts to prove Fermat’s Little Theorem, or to introduce primality testing algorithms that give no hint of the factorization.

Theorem 1 (Wilson’s Theorem) For a prime number \({p}\), we have $$ (p-1)! \equiv -1 \pmod p. \tag{1}$$

The theorem is clear for \({p = 2}\), so we only consider proofs for “odd primes \({p}\).”

The standard proof of Wilson’s Theorem included in almost every elementary number theory text starts with the factorial \({(p-1)!}\), the product of all the units mod \({p}\). Then as the only elements which are their own inverses are \({\pm 1}\) (as \({x^2 \equiv 1 \pmod p \iff p \mid (x^2 – 1) \iff p\mid x+1}\) or \({p \mid x-1}\)), every element in the factorial multiples with its inverse to give \({1}\), except for \({-1}\). Thus \({(p-1)! \equiv -1 \pmod p.} \diamondsuit\)

Now we present a different proof.

Take a primitive root \({g}\) of the unit group \({(\mathbb{Z}/p\mathbb{Z})^\times}\), so that each number \({1, \ldots, p-1}\) appears exactly once in \({g, g^2, \ldots, g^{p-1}}\). Recalling that \({1 + 2 + \ldots + n = \frac{n(n+1)}{2}}\) (a great example of classical pattern recognition in an elementary number theory class), we see that multiplying these together gives \({(p-1)!}\) on the one hand, and \({g^{(p-1)p/2}}\) on the other.

As \({g^{(p-1)/2}}\) is a solution to \({x^2 \equiv 1 \pmod p}\), and it is not \({1}\) since \({g}\) is a generator and thus has order \({p-1}\). So \({g^{(p-1)/2} \equiv -1 \pmod p}\), and raising \({-1}\) to an odd power yields \({-1}\), completing the proof \(\diamondsuit\).

After posting this, we have since seen that this proof is suggested in a problem in Ireland and Rosen’s extremely good number theory book. But it was pleasant to see it come up naturally, and it’s nice to suggest to our students that you can stumble across proofs.

It may be interesting to question why \({x^2 \equiv 1 \pmod p \iff x \equiv \pm 1 \pmod p}\) appears in a fundamental way in both proofs.

This post appears on the author’s personal website davidlowryduda.com and on the Math.Stackexchange Community Blog math.blogoverflow.com.

Introduction

Today we will play a small game which is really really simple. We will add up numbers to make numbers. And to keep the matters simple we will only deal with counting numbers \(1, 2, 3, \ldots\) As an example \(2 + 3 = 5\), but to make the game challenging we would reverse the problem. Let’s ask how we can split \(5\) into sum of other numbers. For completeness we take \(5\) also as one of the ways to express \(5\) as sum of numbers. Clearly we have the following other ways $$ 5 = 4 + 1 = 3 + 1 + 1 = 3 + 2 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$$ so that there are \(7\) different ways of adding numbers to make \(5\). We don’t take into account the order of summands. Also one number can be repeated if needed.

Partitions of a Number

It turns out that a whole generation of distinguished mathematicians (Euler, Jacobi, Ramanujan, Hardy, Rademacher etc) were also interested in playing the above game. And needless to say, they made the whole thing very systematic by adding some definitions (its their silly habit so to speak). Following their footprints we say that a tuple \((n_{1}, n_{2}, \ldots, n_{k})\) of positive integers is a partition of a positive integer \(n\) if $$n_{1} \geq n_{2} \geq \cdots \geq n_{k}\text{ and }n_{1} + n_{2} + \cdots + n_{k} = n$$ Thus \((3, 2), (3, 1, 1)\) etc are partitions of \(5\). If \((n_{1}, n_{2}, \ldots, n_{k})\) is a partition of \(n\) then we say that each of the \(n_{i}\) is a part of this partition, \(k\) is the number of parts, \(n_{1}\) is the greatest part and \(n_{k}\) the least part of this partition.

The mathematicians were really not so interested in finding individual partitions of a number \(n\), but were rather interested in finding out the total number of partitions of \(n\). The example above deals with \(n = 5\) and clearly there are \(7\) partitions of \(5\). You should convince yourself by taking a slightly larger number, say \(n = 8\) or \(n = 10\), that finding the number of partitions of any given number \(n\) is not that easy. Especially writing out each partition of \(n\) and then counting them all is very difficult. You may always feel that probably you have missed one of the partitions. Mathematicians however found out a smart way to count partitions. We explore this technique further.

more »