1. Notation: a|b means 'a is a divisor of b'. We read it as 'a divides b'. Example: 4|12, but 4 | 13
2. If a|b and a|c then a | (pb+qc)
3. GCD - Let a and b two non zero integers. Then the gcd of a and b exists and is written as (a, b) and it is unique also. Examples: GCD (10, 15) = 5, GCD (8, 9) = 1
If (a,b) = 1, then a and b are said to be ralatively primes or co-primes of each other. Example 15 and 22 are co-prime
Two consecutive integers are always co-prime
4. Congruencies
a ≡ b (mod c) means a-b is divisible by c. We read it as 'a is congruent to b modulo c'.
Let a ≡ b (mod m) and c ≡ d (mod m), then
a + c ≡ ( b + d) (mod m)
a - c ≡ (b - d) (mod m)
ac ≡ bd (mod m)
aⁿ ≡ bⁿ (mod m) ∀ integers n
4. Fermat's little theorem
If p is a prime number, and a is co-prime to p, then "a^{p-1}\equiv 1 (mod \: p)")
 "2^{7-1}\equiv 1 (mod \: 7)")
 "3^{5-1}\equiv 1 (mod \: 5)")
5. Another form of the Fermat little theorem:
If p is a prime number, then a is any integer, then
 "a^{p}\equiv a (mod \: p)")
^p&space;\equiv&space;(a^p&space;+&space;b^p)\:&space;mod&space;\:&space;p "(a+b)^p \equiv (a^p + b^p)\: mod \: p")
6. Wilson's Theorem
If p is a prime number, then!\equiv&space;-&space;1&space;(mod&space;\:&space;p) "(p-1)!\equiv - 1 (mod \: p)")
6! = -1 (mod 7)
10! =- 1 (mod 11)
7. Euler's totient functions
Let n be a postive integer. The number of all positive integers less than or equal to n and prime to it is denoted by "\phi (n)")
Example "\phi (10)")
= {1, 2, 3, 5, 6, 7,8 ,9, 10} = 4
If n is a prime number then&space;=&space;n-1 "\phi (n) = n-1")
If n is a power of 2 then&space;=&space;\frac{1}{2}&space;n "\phi (n) = \frac{1}{2} n")
The Euler phi function is multiplicative.
This means that if m,n are co-prime, then&space;=&space;\phi&space;(m)&space;.&space;\phi&space;(n) "\phi (mn) = \phi (m) . \phi (n)")
Quick way of computing: List the distinct primes p which divide n, then multiply the product of (p-1)/p for all such p.
Take n = 20. The distinct primes dividing 20 are 2 and 5, so
&space;=&space;20&space;.&space;\frac{1}{2}&space;.&space;\frac{4}{5}&space;=&space;8 "\phi (20) = 20 . \frac{1}{2} . \frac{4}{5} = 8")
Take n = 350. The distinct primes dividing 350 are 2, 5, 7
&space;=&space;350&space;.&space;\frac{1}{2}&space;.&space;\frac{4}{5}&space;.&space;\frac{6}{7}&space;=&space;120 "\phi (350) = 350 . \frac{1}{2} . \frac{4}{5} . \frac{6}{7} = 120")
8. Infinitude of primes
* There are infinitely many prime number
* There are infinitely many prime numbers of each of the types 1 (mod 4) and 3 (mod 4)
1 (mod 3) : {5, 13, 17, 29, 37, 41, 53, 61, 73, 89,...}
1 (mod 5) : {3, 7, 11, 19, 23, 31, 43, 47, 59, 67, ...}
9. If p is a prime number of the type 3 (mod 4), then it cannot be expressed as x² + y², where x and y are integers
10. If p is a prime number of the type 1 (mod 4), then it can be expressed as x² + y², where x and y are integers. Moreover, this representation is unique
example 13 = 2² + 3², 89 = 5² + 8²
The Goldbach Conjecture is a yet unproven conjecture stating that every even integer greater than two is the sum of two prime numbers. The conjecture has been tested up to 400,000,000,000,000.
9. Two important formulae
1. If n is either even or odd2. If a|b and a|c then a | (pb+qc)
3. GCD - Let a and b two non zero integers. Then the gcd of a and b exists and is written as (a, b) and it is unique also. Examples: GCD (10, 15) = 5, GCD (8, 9) = 1
If (a,b) = 1, then a and b are said to be ralatively primes or co-primes of each other. Example 15 and 22 are co-prime
Two consecutive integers are always co-prime
4. Congruencies
a ≡ b (mod c) means a-b is divisible by c. We read it as 'a is congruent to b modulo c'.
Let a ≡ b (mod m) and c ≡ d (mod m), then
a + c ≡ ( b + d) (mod m)
a - c ≡ (b - d) (mod m)
ac ≡ bd (mod m)
aⁿ ≡ bⁿ (mod m) ∀ integers n
4. Fermat's little theorem
If p is a prime number, and a is co-prime to p, then
5. Another form of the Fermat little theorem:
If p is a prime number, then a is any integer, then
6. Wilson's Theorem
If p is a prime number, then
6! = -1 (mod 7)
10! =- 1 (mod 11)
7. Euler's totient functions
Let n be a postive integer. The number of all positive integers less than or equal to n and prime to it is denoted by
Example
If n is a prime number then
If n is a power of 2 then
The Euler phi function is multiplicative.
This means that if m,n are co-prime, then
Quick way of computing
Take n = 20. The distinct primes dividing 20 are 2 and 5, so
Take n = 350. The distinct primes dividing 350 are 2, 5, 7
8. Infinitude of primes
* There are infinitely many prime number
* There are infinitely many prime numbers of each of the types 1 (mod 4) and 3 (mod 4)
1 (mod 3) : {5, 13, 17, 29, 37, 41, 53, 61, 73, 89,...}
1 (mod 5) : {3, 7, 11, 19, 23, 31, 43, 47, 59, 67, ...}
9. If p is a prime number of the type 3 (mod 4), then it cannot be expressed as x² + y², where x and y are integers
10. If p is a prime number of the type 1 (mod 4), then it can be expressed as x² + y², where x and y are integers. Moreover, this representation is unique
example 13 = 2² + 3², 89 = 5² + 8²
The Goldbach Conjecture is a yet unproven conjecture stating that every even integer greater than two is the sum of two prime numbers. The conjecture has been tested up to 400,000,000,000,000.
9. Two important formulae
2. If n is even