Number Theory Chapter 6 Review Notes

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)