Another Proof of Wilson's Theorem

In previous posts, we have learned about modulo for rational numbers. To show its application, today, we will use the language of modulo of rationals to give another proof of Wilson's Theorem.

Wilson's theorem is a well known theorem in number theory. It is stated as follows.

Wilson's Theorem. If $p$ is a prime number then $$(p-1)! = -1 \pmod{p}.$$

Modulo for rational numbers II

In the previous post, we have learned about modulo for rational numbers. Today, we will continue on this topic and will learn about some properties of this modulo.

First of all, let us look at some examples and review the definition: $$\frac{14}{5} =_{Q} ~0 \pmod{7}, $$ $$ \frac{16}{55} =_{Q} ~\frac{9}{55} =_{Q} ~\frac{2}{55} \pmod{7},$$ $$\frac{1}{4} =_{Q} ~\frac{8}{4} =_{Q} ~2 \pmod{7}, \dots$$

Definition. Let $n$ be an integer, and $\alpha$, $\beta$ two rational numbers. We say that $\alpha$ is equal to $\beta$ modulo $n$, and write $$\alpha =_{Q} ~\beta \pmod{n}$$ if and only if there exists an integer $k$ co-prime to $n$ such that $k(\alpha - \beta)$ is an integer and $$k(\alpha - \beta) = 0 \pmod{n}.$$

A proof of Wilson's Theorem using polynomial interpolation

In the last posts, we have learned about polynomial interpolation through two formulas, the Newton's interpolation formula and the Lagrange's interpolation formula. Both formulas can be used to prove the Wilson's theorem.

In this post, we will present a proof of the Wilson's theorem based on the Newton's interpolation formula. The other proof, that is, proving Wilson's theorem based on the Lagrange's interpolation formula, we leave it as a homework exercise.

Wilson's Theorem is a well known theorem in number theory. It says that if $p$ is prime number then the number $(p−1)!+1$ is a multiple of $p$.

Wilson's Theorem

Today, we will study Wilson's Theorem - a theorem concerning prime numbers. Wilson's theorem says that if $p$ is a prime number then the number $(p-1)! + 1$ will be divisible by $p$.

Here, the notation $n!$ denotes $$n! = 1 \times 2 \times 3 \times \dots \times n.$$

For example,

• $1! + 1 = 2$ is divisible by $2$
• $2! + 1 = 3$  is divisible by $3$
• $4! + 1 = 25$  is divisible by $5$
• $6! + 1 = 721$  is divisible by $7$

modulo - Part 6

We recall the definition of modulo. Two numbers $a$ and $b$ are said to be equal modulo $n$ if and only if $a-b$ is a multiple of $n$, and we write $a = b \pmod{n}$. For example, $9 = 1 \pmod{8}$ and $14 = -2 \pmod{8}$. 

In our usual arithmetic, we picture our integer numbers lying on the number line and we do addition and multiplication like this $2 + 7 = 9$, $2 \times 7 = 14$, etc...

our number line

modulo - Part 5

Today we will learn about Fermat's "little" Theorem. We will see that Fermat's little Theorem is very useful in modulo arithmetic. The theorem asserts that for any prime number $p$ and for any number $a$ not divisible by $p$,
$$ a^{p-1} = 1 \pmod{p} . $$

modulo - Part 4

One of the all-time famous mathematicians is Pierre de Fermat. He is a French mathematician and lived in the 17th century.

To mention Fermat, we must mention "his problem" - the Fermat's last problem. The problem that had challenged generations of mathematicians. Probably the reason that his problem is so well-known and attracted so much effort from top mathematicians as well as young school students is that it is stated so simple and that a secondary school student can understand it.

The Fermat's last problem is stated as follows. Prove that for any $n \geq 3$ the following equation does not have non-trivial solutions  

$$ x^n+y^n=z^n $$

Non-trivial solutions here mean non-zero solutions. This is because if  $x$, $y$ or $z$ is equal to 0 then the equation becomes trivial.

modulo - Part 3

Today, we are going to look at some more examples about modulo.

Example 1: Prove that $11 + 2011^{2012} + 2012^{2013}$ is divisible by 13.

modulo - Part 2

Last time, we have learnt about modulo. Two integers $a$ and $b$ are said to be equal modulo $n$, denoted by $a = b \pmod{n}$, iff $a-b$ is divisible by $n$.

For example, $15 = 3 \pmod{4}$ and $99 = -1 \pmod{10}$.

modulo - Part 1

Today we will look at an important concept in number theory -- the concept of modulo. Two integer numbers $a$ and $b$ are said to be equal modulo $n$ iff they have the same remainder when divided by $n$. Or equivalently, iff $(a-b)$ is divisible by $n$. We will write $a = b \pmod{n}$.