Some Important results and terms In Number Theory

NOTE : In the following results we are going to use $\;(a,b)\;$ as GCD of a and b, while $\;[a,b]\;$ as LCM of a and b.$\;\phi(n)\;$ is Euler's totient function.

1). $\left(\begin{array}{l}n \\ k\end{array}\right)=\displaystyle \frac{n !}{k !(n-k) !}$

2). $\displaystyle \sum_{k=0}^{n}\left(\begin{array}{l}n \\ k\end{array}\right)=2^{n}$ 

3). $(a+b)^{n}=\displaystyle \sum_{k=0}^{n}\left(\begin{array}{l}n \\ k\end{array}\right) a^{n-k} b^{k}$

4).  Square of any integer is always of form $4 k \;\;\text{or}\;\; 4 k+1$

5).  If $a \mid n$ and $b \mid n$ ,given $(a, b)=1$, then $a b \mid n$ 

6). If $(a, b)=1$ and $d \mid b \Rightarrow(a, d)=1$ 

7). Euclid Lemma: If $a \mid b c$ and $(a, b)=1$ then $a \mid c$ 

8). $(a, n)=(b, n)=1$, Iff $(a b, n)=1$ 

9). An integer is called Square free If it is not divisible by the square of any integer $>1$. Example 5, 7, 10, 11...

10). Euclid's theorem : The number of primes are infinite.

11). Let $p_{m}$ is the mth prime, then $p_{m} \leq 2^{2^{m-1}}$.

12). Mersenne Numbers: The integers of the form $$M_{m}=2^{m}-1, m \geq 1$$ are know as Mersenne Numbers. 

13). If $2^{m}-1$ is a prime number then $m$ will be a prime number. 

14). Fermat's Number: $F_{n}=2^{2^{n}}+1 , n \geq 0$ are known as Fermat's number.

15). Fermat's Numbers are mutually co-prime i.e $\left(F_{n}, F_{m}\right)=1$.

16). Congruence is an equivalence relation.

17). lf $n$ be a composite number then $(n-1) ! \equiv 0(\bmod n)$ where $n \neq 4$.

18). If $a \equiv b(\bmod n)$ and $c \equiv f(\bmod n)$ then $a+c \equiv b+f(\bmod n)$.

19). Let $\;p\;$ be a prime number greater than 5 , then either $p^{2}-1$ or $p^{2}+1$ divisible by 10.

20). If $a \equiv b(\bmod n)$ then $a^{k} \equiv b^{k}(\bmod n)$ where $k$ is a positive Integer.

21). $m a \equiv m b(\bmod n)$ if and only if $a \equiv b\left(\bmod \displaystyle \frac{n}{(m, n)}\right)$

22). If $m a \equiv m b(\bmod n)$ and given $(m, n)=1$ then $a \equiv b(\bmod n)$

23). For any positive Integer $m$. If $a \equiv b(\bmod n)$ then $ma=m b(\bmod mn)$

24). If $a b \equiv e f(\bmod m)$ and $b \equiv f(\bmod m)$ given $(b, m)=1$ then $a \equiv e(\bmod m)$

25). Let $a \equiv b \bmod (m)$ and $d>0$ divides $a, b, m$ then $\displaystyle \frac{a}{d} \equiv \displaystyle \frac{b}{d} \operatorname{mod}\left(\displaystyle \frac{m}{d}\right)$

26). Let $a \equiv b(\bmod m)$ and $a \equiv b(\bmod n)$ then $a \equiv b(\bmod mn)$ If $(m, n)=1$ otherwise $a \equiv b(\bmod ((m, n)))$

27). If $c \mid m$ and $a \equiv b(\bmod m)$, them $a \equiv b(\operatorname{mod} c)$

28). If $a^{m} \equiv 1(\bmod n)$ for some positive integer $m$ then $$(a, n)=1$$

29). If $m$ and $n$ are positive integers such that $$(m, n)=1 \text { then } \phi(m n)=\phi(m) \phi(n)$$

Where $\phi(n)$ represent the number of elements that are coprime to $n$ and less than $n$

30). Let $p$ is some prime and $n$ be some positive Integer then $$\phi\left(p^{k}\right)=p^{k}-p^{k-1} \text { or } p^{k}\left(1-\displaystyle \frac{1}{p}\right)$$

31). ${\phi}(n)=n \displaystyle \prod_{p|n}\left(1-\displaystyle \frac{1}{p}\right)$ where $n$ is any positive Integer $n>1$.

32). If $n>2$ the $\phi(n)$ is always even.

33). Euler-Fermat theorem: $a^{\phi(n)} \equiv 1(\bmod n)$ provided $(a, n)=1$.

34). Fermat's Little theorem: Given $p$ is a prime and $p\nmid a$ then $a^{p-1} \equiv 1(\bmod p)$.

35). If $p$ is prime then $a^{p} \equiv a(\bmod p)$ for every integer $a$.

36). If $n$ is odd and $2^{m-1}\not \equiv 1(\bmod m)$ then $m$ must be a composite number.

37). Linear congruence: $A$ Congruence of the form $a x \equiv b(\bmod n)$ is Called Linear Congruence.

38). Let $a x \equiv b(\bmod n)$ is a Linear congruence and given $(a,n)=d$, then linear congruences have solution Iff $d \mid b$. Also If $d \mid b$, then there are exactly $d$ solutions modulo $n$.

39). Linear congruence $a x\equiv b(\bmod n)$ with $\operatorname(a, n)=1$, always has a unique solution.

40). Chinese remainder  theorem :

Given $n_{1}, n_{2}, \cdots n_{m}$ are positive integers which are relatively prime in pairs, then for any $a_{1}, a_{2}\cdots a_{m} \in \mathbb{Z}$, the system of linear congruence

$$\begin{aligned}&x=a_{1}\left(\bmod n_{1}\right) \\&x=a_{2}\left(\bmod n_{2}\right)\\&\vdots\\&x=a_{m}\left(\bmod n_{m}\right)\end{aligned}$$

has Unique Solution modulo $n$, where

$$n=n_{1} \times n_{2} \times n_{3} \times n_{n} \cdots \times n_{m}$$ .

41). Wilson's theorem: for any prime number $p$, we have $$(p-1)!\equiv-1(\bmod p)$$

42).Converse of Wilson's theorem: If $n>1$ an positive integer and $\left.(n-1 \right)! \equiv -1(\bmod n)$, then $n$ is prime.

43). Let $p$ be a prime. Then $x^{2} \equiv-1(\bmod p)$ has solution If and only If $p=2$ or $p \equiv 1(\bmod 4)$.

44). If $p$ is an odd prime, then $$\left[\left(\displaystyle \frac{p-1}{2}\right) !\right]^{2}+(-1)^{\displaystyle \frac{p-1}{2}} \equiv 0(\bmod p)$$

45). For every positive integer $n>1$ $$d(m)=\prod_{p^{n}||m} \mid (n+1)$$ where $d(m)$ is the number of positive divisors of $m$.

46). $\sigma(m)=\displaystyle \prod_{p^{n}|| m}\left(\displaystyle \frac{p^{n+1}-1}{p-1}\right)$, where $p^{n}\mid m$ indicates $p^{n}| m \quad$ But $p^{n+1}\nmid m$.

47). Multiplicative function: An Arithmetic function $g$ , provided $g$ is not identically zero , is said to be multiplicative function If

$$g(m \times n)=g(m) g(n) \text { provided }(m, n)=1$$ .

48). Both $d(m)$ and $\sigma(m)$ are Multiplicative functions.

49). Möbius function: Denoted by $\mu$, $$\mu(m)= \begin{cases}1 & \text {If}\;\; m=1 \\ 0 & \text {otherwise} \\ (-1)^{k} & \text {If m is square free with k prime factors} \end{cases}$$

 where $p_{1}, p_{2}\cdots p_{n}$ are distinct primes.

50). For each positive Integer $n \geq 1$, we have

$$\displaystyle \sum_{d | m} \mu(d)=\left\{\begin{array}{lll}1 & \text { If } & m=1 \\0 & \text { If } & m>1\end{array}\right.$$

51). For any $m \geq 1$ we have $$\phi(m)=\displaystyle \sum_{d \mid m} \mu(d) \cdot \displaystyle \frac{m}{d}$$

52). Möbius inversion formula: Let $\;f$ and $g$ are two Arithmetic functions. Then for every integer $\mathrm{m}$. If $f(m)=\displaystyle \sum_{d| m} g(d)$

than $g(m)=\displaystyle \sum_{d \mid m} \mu(d) f\left(\displaystyle \frac{m}{d}\right)$

53). Let $p$ is a prime number. Then Largest exponent $a$ such that $p^{a} \mid m$ ! is

$$a=\displaystyle \sum_{i=1}^{\infty}\left[\displaystyle \frac{m}{p^{i}}\right]$$

where $m$ is positive integer, and $\;\left[ \cdots \right]\;$ is greatest integer function.

54). For any positive integer $m \geq 1$ $$m=\displaystyle \sum_{d \mid m} \phi(d)$$

55).  $\displaystyle \phi(m)\phi(n) =\frac{\phi(mn)\times \phi(d)}{d}$ , where m and n are positive Integers.