6.2 - Special Primes

• Mersenne primes - (2^p)-1

  • (2^11) -1 is not a Mersenne Prime

  • Not all (2^p)-1 will give you a prime

  • ((2^p)-1)*(2^p-1) will give you a perfect number for working Mersenne Primes

• Fermat primes - 2^(2^n)+1

  • Fermat believed all numbers in the form 2^(2^n)+1 are prime

  • Works for n=0,1,2,3,4 but not 5

  • Conjectured that only known Fermat primes are 3, 5, 17, 257, and 65537

• Twin primes - Primes that only differ by 2

  • Ex: 3 and 5, 11 and 13

  • Twin prime conjecture: there are infinitely many twin primes

  • Sum of any two twin primes other than 3 and 5 is divisible by 12

6.3 - Factorials, Exponents, and Divisibility

• Factorial: n! = n(n-1)(n-2)…(2)(1)

• Used in combinations

  • Number of ways to arrange 4 objects is 4!

• x!+(x+1)! = x!(2+x)

• All prime factors of n! are all primes less than or equal to n

• x! = (x-1)! * x

Find highest power of n that divides x!

1. Prime factorize n (ex 10 = 2*5)

2. Find the number of times the biggest prime factor of n goes into x (ex 45/5 = 9)

3. Repeat with the number from the last step until you can fit no more factors into it (ex 9/5 = 1 r4; 1/5 = 0 r1; stop here)

4. Add up all numbers gotten from last step (ex 9 + 1 = 10)

5. Highest power of n that divides x! is the new number from the last step (ex 10^10 is the highest power of 10 in 45!)

6.4 - Perfect, Abundant, and Deficient Numbers

• Perfect number - integer that is equal to the sum of its proper divisors (ex 6 = 1+2+3)

• Abundant number - integer that is smaller than the sum of its proper divisors (ex 12- 1+2+3+4+6 = 16, 16>12)

• Deficient number - integer that is greater than the sum of its proper divisors (ex 4- 1+2 = 3, 3<4)

• Every prime number is deficient

• All multiples of perfect numbers are abundant

• First odd abundant number is 945

• Perfect numbers are found using Mersenne Primes (mentioned in 6.2 notes)

6.5 - Palindromes

• Numbers that are the same backwards and forwards. (ex 1331, 12721)

• Total # of n-digit palindromes: 9*(10^(ciel(n/2)-1) (ex: # of 3-digit palindromes = 90)