Divisibility & Primes

Things you should know:

• The sum, difference and product of two integers are always integers.
• The result of dividing two integers is sometimes an integer.
• Rules of divisibility (see MGMAT NP p14)
• Divisibility without rules:
  1) Find a multiple of the divisor that is close to the dividend
  2) Find the difference of the multiple and the initial number, then check if this difference is divisible by the divisor
  
• A factor is a positive integer that divides evenly into an integer.
• A multiple is formed by multiplying that integer by an integer.
• An integer is always both a factor and a multiple of itself.
• 1 is a factor of every integer.
  
  
• Adding or subtracting multiples of N result in a multiple of N.
• Adding or subtracting a multiple of N to/from a non-multiple of N results in a non-multiple of N.
• Adding two non-multiples of N can result in either a multiple of N or a non-multiple of N.
• When adding or subtracting two integers, neither of which is divisible by 2, the result will always be divisible by 2.
  
  
• First ten prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.
• Determining if a number is prime: test divisibility with odd numbers up to its root.
  
  
• Any integer is divisible by all of its factors and also divisible by all of the factors of its factors.
• An integer n is divisible by all the possible products of its primes.
  
  
• GCF (shared primes): Take the lowest count of each prime factor found across all the integers (smallest count is zero)
  
• LCM (all the primes less the shared primes): Take the highest count of each prime found across all the integers. 
• (GCF of m & n) x (LCM of m & n) = m x n
• GCF of m & n cannot be larger than the difference between m & n
• Consecutive multiples of n have a GCF of n 
• Total prime factors (length): Add the exponents of the prime factors. 
• Total factors - if a prime factors appears to Nth power then there are N+1 possibilities for the occurrence of that factor, multiple the number of ways to make each individual decision to find the number of ways to make all the decisions
  
• All perfect squares have an odd number of total factors and the prime factorization contains only even powers of primes
  
  
• N! must be divisible by all integers from 1 to N
  
  Remainders:
  
• X/N = Q + R/N
• X = Q x N + R
• Remainders range from 0 to (N - 1), there are N possible remainders.
• Remainders can be added or subtracted directly, as long as the excess or negative remainders are corrected by just adding or subtracting the divisor.
• Remainders can be multiplied as long as the excess is corrected at the end.
• The decimal part of a quotient equals the remainder divided by the divisor.