Mathematics

  Lemma: Let $p$ be a prime number. Then prove that $x^2 \equiv 1 ~(mod ~p)$ if and only if $x \equiv 1 ~ (mod ~p) $ or $x \equiv - 1 ~ (mod ~p) $. P roof: Suppose that $x^2 \equiv 1 ~(mod ~p)$. This quadratic congruence is equivalent to $(x^2 -1 )\equiv 0 ~(mod ~p)$ i.e.  $(x -1 ) ~(x + 1) \equiv 0 ~(mod ~p)$. This implies that $p ~|~ (x - 1) ~ (x+1)$. By Theorem , $p ~|~ (x - 1)$ or $p ~|~ (x + 1)$. This gives that $x \equiv 1 ~ (mod ~p) $ or $x \equiv - 1 ~ (mod ~p) $. Conversely, suppose that either $x \equiv 1 ~ (mod ~p) $ or $x \equiv - 1 ~ (mod ~p) $. Then clearly $x^2 \equiv 1 ~(mod ~p)$.

  Theorem:  There is an infinite number of primes.  Proof :  Suppose on the contrary that there are only finite number of primes. Let $p_{1} = 2, p_2 = 3, p_3 = 5, p_4 = 7, \cdots $ be  the primes in ascending order, and suppose that there is a last prime, called $p_n$· Now consider the positive integer $P = (p_{1} \cdot p_2 ~ \cdots ~ p_n)+ 1$. Since $P > 1$, by Theorem , $P$ is  divisible by some prime $p$. But $p_{1}, ~p_2, ~ p_3, ~\cdots~, p_n $ are the only prime numbers, so that $p$ must be equal to one of $p_{1}, ~p_2, ~ p_3, ~\cdots~, p_n $ and hence $p ~|~  p_{1} \cdot p_2 ~ \cdots ~ p_n$· Since $p ~|~  p_{1} \cdot p_2 ~ \cdots ~ p_n$ and $p ~|~ P$, we will get $p ~|~ (p_{1} \cdot p_2 ~ \cdots ~ p_n) - P$ i.e. $p ~|~ 1$. Since the only positive divisor of the integer $1$ is $1$ itself so we will get a contradiction to  $p > 1$. Hence there are  infinite number of primes.

  (Fundamental Theorem of Arithmetic): Every positive integer $n > 1$ is either a prime or can be written as a product of primes; this representation is unique, apart from the order in which the factors occur. Proof: If a positive integer $n > 1$ is a prime number, then we are done. So suppose that $n$ is a composite number. Therefore there exists an integer $d$ satisfying $d ~|~ n$ and $1 < d < n$. By Well-Ordering Principle , there exists smallest integer among all such integers $d$ (positive divisors), we will called this smallest integer (smallest positive divisor) as a $p_{1}$. We claim that $p_{1}$ is a prime number. Suppose that $p_{1}$ is not a prime number. So there exists  an integer $q$ satisfying $q ~|~ p_{1}$ and $1 < q < p_{1}$. Since $q ~|~ p_{1}$ and $p_{1} ~|~ n$, we will get $q ~|~ n$, a contradiction to choice of smallest positive divisor  $p_{1}$ of $n$. Therefore we can write $n$ as $n = p_{1} \cdot n_{1}$, where $p_{1}$ is a pri...

Corollary:  If $p$ is a prime and $p ~|~ a_{1} \cdot a_2 ~\cdots~ a_n$, then $p ~|~ a_k$ for some $k$, where $1 \leq k \leq n$. Proof:  Suppose that $p$ is a prime and $p ~|~ a_{1} \cdot a_2 ~\cdots~ a_n$, then by Theorem , $p ~|~ a_{1}$ or $p ~|~ a_2 \cdot a_3 ~\cdots~ a_n$. If $p ~|~ a_{1}$, then we are done. If $p \nmid a_{1}$, then $p ~|~ a_2 \cdot a_3 ~\cdots~ a_n$. We use Theorem , to $p ~|~ a_2 \cdot a_3 ~\cdots~ a_n$. So we will get either $p ~|~ a_2$ or $p ~|~ a_3 \cdot a_4 ~\cdots~ a_n$. If $p ~|~ a_2$, then we are done. If $p \nmid a_2$, then $p ~|~ a_3 \cdot a_4 ~\cdots~ a_n$. We will make use of Theorem   again and again. Since $n$ is finite, use of Theorem  ,  will stop after finitely many times. So we will get  $p ~|~ a_k$ for some $k$, where $1 \leq k \leq n$. Corollary:  If $p, q_{1}, q_2, ~\cdots~ q_n$ all are primes and $p ~|~ q_{1} \cdot q_2 ~\cdots~ q_n$, then $p = q_k$ for some $k$, where $1 \leq k \leq n$. Proof:   We w...

Definition: An integer $p > 1$ is called a prime number, or simply a prime, if its only positive divisors are $1$ and $p$. An integer greater than $1$ that is not a prime is termed composite. Example: We can observe that $2, 3, 5, 7$ etc. are prime numbers whereas $4, 6, 8, 9, 10$ etc. are composite numbers. Theorem: If $p$ is a prime and $p ~|~ ab$, then $p ~|~ a$ or $p ~|~ b$. Proof: If $p ~|~ a$, then we are done. So suppose that $p \nmid a$. Therefore $gcd(p,a) = 1$. Hence by Euclid Lemma , $p ~|~ b$..