The definition of limit of a sequence (in the real numbers) is well known:

Let $(u_n)_{n \in \mathbb{N}}$ be a sequence of real numbers. Then:

$$\lim_{n \to \infty} u_n = L \iff \forall \epsilon >0: \exists N \in \mathbb{N}: \forall n > N: |u_n - L| < \epsilon$$

and we say that the sequence converges to its limit $L$.

While this definition may seem abstract, there is a good reason it looks like this. When we speak about convergence, we mean that when we look far, for very great indices $n$, the terms of the sequence come arbitrarily close to the limit. So, the distance between the limit value, and the value of the sequence for this large $n$, can become as small as possible.

So for a certain (small) $\epsilon > 0$, we have that $|u_n - L| < \epsilon$, if we look far enough, which translates by saying that we can always find a positive integer $N$ such that the condition $|u_n - L| < \epsilon$ is met whenever $n > N$.

## Thursday, 10 August 2017

## Sunday, 16 April 2017

### $(p-1)! \equiv -1 \bmod p$

A group theoretic proof:

Obviously, for $p = 2$, the statement is true.

For the rest of the proof, let's assume $p \neq 2$

Now, if we have a finite abelian group $G = \{x_1, \dots , x_n\}$, we know that $x_1*x_2* \dots x_n = \prod\limits_{ord(x_i)=2}x_i$, because every element that does not have order 2 cancels with its inverse (if $ord(x) = 2$, then $x^2 = e$, then $x = x^{-1}$)

Now, let's apply this to the group $(\mathbb{Z}/p\mathbb{Z}-\{0\},.)$:

(Denote the elements of $\mathbb{Z}/p\mathbb{Z}-\{0\}$ as $\{ [1], \dots [p-1]\}$)

We find $$[1][2][3]\dots[p-1] = [(p-1)!] =\prod\limits_{ord(x_i)=2}x_i$$

So, we only have to find the elements of order 2 in the group:

Hence, let's solve the equation $[a]^2 = [1]$:

$[a]^2 = [1] \iff [a^2] = [1] \iff a^2 \equiv 1 \bmod p \iff p|(a-1)(a+1)$

and because $p$ is prime (that's important here), it follows that either $p|(a-1)$ or $p|(a+1)$. Hence, $a \equiv 1 \bmod p$ or $a \equiv -1 \bmod p$

and thus:

$[a] = [1]$ or $[a] = [-1]$

Because $ord([1]) = 1$, it follows that $[-1]$ is the only element of order $2$ in the group. Hence:

$[(p-1)!] = [-1]$

and thus:

$(p - 1)! \equiv -1 \bmod p \quad \triangle$

Obviously, for $p = 2$, the statement is true.

For the rest of the proof, let's assume $p \neq 2$

Now, if we have a finite abelian group $G = \{x_1, \dots , x_n\}$, we know that $x_1*x_2* \dots x_n = \prod\limits_{ord(x_i)=2}x_i$, because every element that does not have order 2 cancels with its inverse (if $ord(x) = 2$, then $x^2 = e$, then $x = x^{-1}$)

Now, let's apply this to the group $(\mathbb{Z}/p\mathbb{Z}-\{0\},.)$:

(Denote the elements of $\mathbb{Z}/p\mathbb{Z}-\{0\}$ as $\{ [1], \dots [p-1]\}$)

We find $$[1][2][3]\dots[p-1] = [(p-1)!] =\prod\limits_{ord(x_i)=2}x_i$$

So, we only have to find the elements of order 2 in the group:

Hence, let's solve the equation $[a]^2 = [1]$:

$[a]^2 = [1] \iff [a^2] = [1] \iff a^2 \equiv 1 \bmod p \iff p|(a-1)(a+1)$

and because $p$ is prime (that's important here), it follows that either $p|(a-1)$ or $p|(a+1)$. Hence, $a \equiv 1 \bmod p$ or $a \equiv -1 \bmod p$

and thus:

$[a] = [1]$ or $[a] = [-1]$

Because $ord([1]) = 1$, it follows that $[-1]$ is the only element of order $2$ in the group. Hence:

$[(p-1)!] = [-1]$

and thus:

$(p - 1)! \equiv -1 \bmod p \quad \triangle$

Subscribe to:
Posts (Atom)