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.
0 Comments