Prime Numbers

• The first twenty-six prime numbers are:
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101
  
  
• Note: only positive numbers can be primes.
  
  
• There are infinitely many prime numbers.
  
  
• The only even prime number is 2, since any larger even number is divisible by 2. Also 2 is the smallest prime.
  
  
• All prime numbers except 2 and 5 end in 1, 3, 7 or 9, since numbers ending in 0, 2, 4, 6 or 8 are multiples of 2 and numbers ending in 0 or 5 are multiples of 5. Similarly, all prime numbers above 3 are of the form 6n−1 or 6n+1, because all other numbers are divisible by 2 or 3.
  
  
• Any nonzero natural number n can be factored into primes, written as a product of primes or powers of primes. Moreover, this factorization is unique except for a possible reordering of the factors.
  
  
• Prime factorization: every positive integer greater than 1 can be written as a product of one or more prime integers in a way which is unique. For instance integer n with three unique prime factors a, b, and c can be expressed as \(n=a^p * b^q * c^r\), where p, q, and r are powers of a, b, and c, respectively and are ≥1.
  Example: \(4200\)=\(2^3\)∗\(3\)∗\(5^2\)∗\(7\).
  
  
• Verifying the primality (checking whether the number is a prime) of a given number nn can be done by trial division, that is to say dividing n by all integer numbers smaller than \(\sqrt{n}\), thereby checking whether n is a multiple of m≤\(\sqrt{n}\).
  Example: Verifying the primality of 161: √161 is little less than 13, from integers from 2 to 13, 161 is divisible by 7, hence 161 is not prime.
  Note that, it is only necessary to try dividing by prime numbers up to √n, since if n has any divisors at all (besides 1 and n), then it must have a prime divisor.
  
  
• If \(n\) is a positive integer greater than 1, then there is always a prime number p with \(n<p<2n\).

Factors

• 1 (and -1) are divisors of every integer.
  
• Every integer is a divisor of itself.
  
• Every integer is a divisor of 0, except, by convention, 0 itself.
  
• Numbers divisible by 2 are called even and numbers not divisible by 2 are called odd.
  
• A positive divisor of n which is different from n is called a proper divisor.
  
• An integer n > 1 whose only proper divisor is 1 is called a prime number. Equivalently, one would say that a prime number is one which has exactly two factors: 1 and itself.
  
• Any positive divisor of n is a product of prime divisors of n raised to some power.
  
• If a number equals the sum of its proper divisors, it is said to be a perfect number.
  Example: The proper divisors of 6 are 1, 2, and 3: 1+2+3=6, hence 6 is a perfect number.
  
  There are some elementary rules:
• If a is a factor of b and a is a factor of c, then a is a factor of (b+c). In fact, a is a factor of (mb+nc) for all integers m and n.
  
• If a is a factor of b and b is a factor of c, then a is a factor of c.
  
• If a is a factor of b and b is a factor of a, then a=b or a=−b.
  
• If a is a factor of bc, and gcd(a,b)=1, then a is a factor of c.
  
• If p is a prime number and p is a factor of ab then p is a factor of a or p is a factor of b.

Finding the Number of Factors of an Integer

Finding the Sum of the Factors of an Integer