Tuesday, March 7, 2017

Perfect Numbers – Proofs

PNP01 – Euclid: If 2p – 1 is prime, then 2p – 1(2p – 1) is a perfect number

01
assume 2p – 1 is prime
assumption
02
  σ(2p – 1(2p – 1))
find the sum of all the divisors of 2p – 1(2p – 1)
03
  = σ(2p – 1)σ(2p – 1)
σ(ab) = σ(a)σ(b) if a and b are relatively prime
04
  = (2p – 1)σ(2p – 1)
σ(2n) = 2n + 1 – 1
05
  = (2p – 1)(2p – 1 + 1)
σ(prime) = prime + 1, and 2p – 1 is prime
06
  = (2p – 1)(2p)
simplify
07
  = (2p)(2p – 1)
commutative
08
  = 2(2p – 1(2p – 1))
laws of exponents
09
  2p – 1(2p – 1) is perfect
if n = 2σ(n), then n is perfect

PNP02 – Euler: If a perfect number is even, it is in the form of 2p – 1(2p – 1), where 2p – 1 is prime

01
assume n is an even
perfect number
assumption
02
  n = 2kx, where 2k and x are relatively prime
properties of an even number
03
  σ(n) = 2n
definition of a perfect number
04
  σ(2kx) = 2(2kx)
substitute n = 2kx
05
  σ(2kx) = 2k+1x
laws of exponents
06
  σ(2k)σ(x) = 2k+1x
σ(ab) = σ(a)σ(b) if a and b are relatively prime
07
  (2k+1 – 1)σ(x) = 2k+1x
σ(2n) = 2n + 1 – 1
08
  x = y(2k+1 – 1)
2k+1 – 1 is odd, and cannot divide into 2k+1, so it must divide into x
09
  σ(x) = 2k+1x/(2k+1 – 1)
divide by (2k+1 – 1)
10
  σ(x) = 2k+1y
substitute x = y(2k+1 – 1)
11
  x + y + d = 2k+1y
x and y and others are divisors of x, so σ(x) = x + y + d
12
  y(2k+1 – 1) + y + d = 2k+1y
substitute x = y(2k+1 – 1)
13
  2k+1y – y + y + d = 2k+1y
distribute
14
  2k+1y + d = 2k+1y
simplify
15
  d = 0
subtract 2k+1y
16
  x = 2k+1 – 1 must be prime
x has no other divisors d
17
  x = 2p – 1 must be prime
substitute k = p – 1

PNP03 – If a perfect number is even (and therefore in the form of 2p – 1(2p – 1)), then it can be represented in binary as p ones followed by p – 1 zeros

01
assume n is an even perfect number
assumption
02
  n = 2p – 1(2p – 1)
Euler’s theorem (PNP02)
03
  multiplying a number q with a number that is a 1 followed by r zeros results in a number that starts with q and is followed by r zeros
rules of multiplication
04
  2p – 1 in binary is a 1 followed by p – 1 zeros
rules of binary
05
  2p – 1 in binary is p ones
rules of binary
06
  n in binary is p ones followed by p – 1 zeros
substitution

PNP04 – If a perfect number is even (and therefore in the form of 2p – 1(2p – 1)), then it is the sum of all the integers from 1 to 2p – 1

01
assume n is an even perfect number
assumption
02
  n = 2p – 1(2p – 1)
Euler’s theorem (PNP02)
03
  n = ½(2p)(2p – 1)
divide 2p – 1 by 2
04
  n = ½(2p – 1)(2p)
commutative
05
  n = ½k(k + 1)
substitute k = 2p – 1
06
  n is the sum of all integers from 1 to k
Σ1kk = ½k(k + 1)
07
  n is the sum of all integers from 1 to 2p – 1
substitute k = 2p – 1

PNP05 – If a perfect number is even and not 6 (and therefore in the form of 2p – 1(2p – 1)), then it is the sum of the first 2(p−1)/2 odd cubes

01
assume n is an even perfect number and not 6
assumption
02
  n = 2p – 1(2p – 1)
Euler’s theorem (PNP02)
03
  n = (2p – 1)2p – 1
commutative
04
  let x2 = 2p – 1 and y2 = 2p – 1
define variables
05
  n =  x2y2
substitute x2 = 2p – 1 and y2 = 2p – 1
06
  y = 2(p – 1)/2
square root y2 = 2p – 1 (p also must be an odd number for this, which is why the perfect number cannot be 6, the only instance where p is even).
07
  x2 – 2y2 = (2p – 1) – 2(2p – 1)
substitute x2 = 2p – 1 and y2 = 22p – 1
08
  x2 – 2y2 = 2p – 1 – 2p
laws of exponents
09
  x2 – 2y2 = -1
simplify
10
  x2y2 is the sum of the first y cubes
If x2 – 2y2 = -1, then x2y2 is the sum of the first y cubes
11
  n is the sum of the first y cubes
substitute n =  x2y2
12
  n is the sum of the first 2(p−1)/2  cubes
substitute y = 2(p – 1)/2

PNP06 – If a perfect number is even and not 6 (and therefore in the form of 2p – 1(2p – 1)), then it is in the form of 1 + 9(T(2^p-2)/3), where T(2^p-2)/3 is the sum of all the integers from 1 to 2^p – 2 / 3
                                                                                                                                                               
01
assume n is an even perfect number and not 6
assumption
02
  n = 2p – 1(2p – 1)
Euler’s theorem (PNP02)
03
  n = 22p – 1 – 2p – 1
distribute
04
  n = 1 + 22p – 1 – 2p – 1 – 1
add 1 and subtract 1
05
  n = 1 + ½(22p – 2p – 2)
factor out a ½
06
  n = 1 + ½(2p – 2)(2p + 1)
factor 22p – 2p – 2
07
  n = 1 + ½∙9∙1/31/3(2p – 2)(2p + 1)
multiply by 9, 1/3, and 1/3
08
n = 1 + 9∙½∙1/3(2p – 2)1/3(2p + 1)
commutative
09
n = 1 + 9∙½∙1/3(2p – 2)1/3(2p – 2 + 3)
substitute 1 = -2 + 3
10
n = 1 + 9∙½((2^p – 2)/3)((2^p – 2)/3 + 1)
distribute 1/3
11
n = 1 + 9∙½k(k + 1)
substitute k = (2^p – 2)/3, (p also must be an odd number for this, which is why the perfect number cannot be 6, the only instance where p is even)
12
n = 1 + 9Tk
Tk = Σ1kk = ½k(k + 1) = the sum of all integers from 1 to k
13
n = 1 + 9T(2^p-2)/3
substitute k = (2^p – 2)/3, T(2^p-2)/3 is the sum of all the integers from 1 to
2^p – 2 / 3

PNP07 – If a perfect number is even and not 6, then it has a digital root of 1
                                                                                                                                                               
01
assume n is an even perfect number and not 6
assumption
02
  n = 1 + 9T(2^p-2)/3
proved above (PNP06)
03
  n mod 9 = 1 mod 9 + 9T(2^p-2)/3 mod 9
mod 9 the equation n = 1 + 9T(2^p-2)/3
04
  n mod 9 = 1
laws of mod
05
  the digital root of n is 1

PNP08 – The sum of reciprocals of all the divisors of every perfect number is equal to 2.
                                                                                                                                                               
01
1/d1 + 1/d2 + … + 1/dn-1 + 1/dn
sum of reciprocals of all the divisors of a perfect number n
02
= n/n(1/d1 + 1/d2 + … + 1/dn-1 + 1/dn)
multiply and divide by n
03
= 1/n(n/d1 + n/d2 + … + n/dn-1 + n/dn)
distribute n
04
= 1/n(dn + dn – 1 + … d2 + d1)
a number divided by its divisor is another divisor
05
= 1/n(d1 + d2 + … dn – 1 + dn)
commutative
06
= 1/nσ(n)
σ(n) is the sum of all the divisors of n
07
= 1/n∙2n
by definition of a perfect number, σ(n) = 2n
08
= 2
simplify

PNP09 – Any number raised to a perfect number exponent is equal to the product of all its perfect roots.
                                                                                                                                                               
01
xn
any number raised to a perfect number exponent n
02
= x2n – n
substitute n = 2n – n
03
= xσ(n) – n
by definition of a perfect number, σ(n) = 2n
04
= x(d1 + d2 + … dn-2 + dn–1 + dn) – n
σ(n) is the sum of all the divisors of n
05
= xd1 + d2 + … dn-2 + dn–1
The greatest divisor of n is n itself, so dn = n, therefore dn – n = 0
06
= xdn-1 + dn-2 + … + d2 + d1
commutative
07
= xn/d2 + n/d3 + … + n/dn-1 + n/dn
a number divided by its divisor is another divisor
08
= d2√xnd3√xn∙…∙dn-1√xndn√xn
laws of exponents

PNP10 – If a perfect number is even, then it ends in 6 or 8

01
assume n is an even perfect number
assumption
02
  n = 2p – 1(2p – 1)
Euler’s theorem (PNP02)
03
  p is odd or p = 2
p is prime by Euler’s theorem
04
  if p = 2:
assumption
05
    n = 22 – 1(22 – 1) = 6
substitute p = 2
06
    n ends in 6
definition
07
  if p is odd:
assumption
08
    p = 2q + 1
definition of odd
09
    n = 22q(22q + 1 – 1)
substitute p = 2q + 1
10
    n = 4q(22q + 1 – 1)
laws of exponents
11
    n = 4q(2∙22q – 1)
laws of exponents
12
    n = 4q(2∙4q – 1)
laws of exponents
13
    4q ends in 4 or 6
14
    if 4q ends in 4:
assumption
15
      n mod 10 = 4(2∙4 – 1) mod 10 = 28 mod 10 = 8
substitute 4q mod 10 = 4
16
      n ends in 8
definition of mod 10
17
    if 4q ends in 6:
assumption
18
      n mod 10 = 6(2∙6 – 1) mod 10 = 66 mod 10 = 6
substitute 4q mod 10 = 6
19
      n ends in 6
definition of mod 10
20
  n ends in 6 or 8
conclusion of all options

PNP11 – If a perfect number is even and has more than 1 digit, then it ends in 16, 28, 36, 56, 76, or 96

01
assume n is an even perfect number
assumption
02
  n = 2p – 1(2p – 1)
Euler’s theorem (PNP02)
03
  p > 2
n has more than one digit
04
  p is odd
p > 2 and p is prime by Euler’s theorem
05
  p = 2q + 1
definition of odd
06
  n = 22q(22q + 1 – 1)
substitute p = 2q + 1
07
  n = 4q(22q + 1 – 1)
laws of exponents
08
  n = 4q(2∙22q – 1)
laws of exponents
09
  n = 4q(2∙4q – 1)
laws of exponents
10
  4q ends in 4, 16, 64, 56, 24, 96, 84, 36, 44, or 76
11
  if 4q ends in 4:
assumption
12
    n mod 100 = 4(2∙4 – 1) mod 100 = 28 mod 100 = 28
substitute 4q mod 100 = 4
13
    n ends in 28
definition of mod 100
14
  if 4q ends in 16:
assumption
15
    n mod 100 = 16(2∙16 – 1) mod 100 = 496 mod 100 = 96
substitute 4q mod 100 = 16
16
    n ends in 96
definition of mod 100
17
  if 4q ends in 64:
assumption
18
    n mod 100 = 64(2∙64 – 1) mod 100 = 1728 mod 100 = 28
substitute 4q mod 100 = 64
19
    n ends in 28
definition of mod 100
20
  if 4q ends in 56:
assumption
21
    n mod 100 = 56(2∙56 – 1) mod 100 = 616 mod 100 = 16
substitute 4q mod 100 = 56
22
    n ends in 16
definition of mod 100
23
  if 4q ends in 24:
assumption
24
    n mod 100 = 24(2∙24 – 1) mod 100 = 1128 mod 100 = 28
substitute 4q mod 100 = 24
25
    n ends in 28
definition of mod 100
26
  if 4q ends in 96:
assumption
27
    n mod 100 = 96(2∙96 – 1) mod 100 = 8736 mod 100 = 36
substitute 4q mod 100 = 96
28
    n ends in 36
definition of mod 100
29
  if 4q ends in 84:
assumption
30
    n mod 100 = 84(2∙84 – 1) mod 100 = 5628 mod 100 = 28
substitute 4q mod 100 = 84
31
    n ends in 28
definition of mod 100
32
  if 4q ends in 36:
assumption
33
    n mod 100 = 36(2∙36 – 1) mod 100 = 2556 mod 100 = 56
substitute 4q mod 100 = 36
34
    n ends in 56
definition of mod 100
35
  if 4q ends in 44:
assumption
36
    n mod 100 = 44(2∙44 – 1) mod 100 = 3828 mod 100 = 28
substitute 4q mod 100 = 44
37
    n ends in 28
definition of mod 100
38
  if 4q ends in 76:
assumption
39
    n mod 100 = 76(2∙76 – 1) mod 100 = 3876 mod 100 = 76
substitute 4q mod 100 = 76
40
    n ends in 76
definition of mod 100
41
  n ends in 16, 28, 36, 56, 76, or 96
conclusion of all options

No comments:

Post a Comment