154
Proofs, Induction, and Number Theory
prime. The largest known prime number as of June 2013 is 2
57,885,161
− 1, a Mersenne prime. There happens to be a particularly efficient algorithm for testing numbers of the form 2
p
− 1 for primality, which is
why almost all of the largest known primes are Mersenne primes. In recent years, most of these Marsenne
primes have been discovered (and verified) by the GIMPS (Great Internet Mersenne Prime Search) distributed computing project, a worldwide group of volunteers who collaborate over the Internet to test for
Mersenne primes.
Find the first 4—the 4 smallest—Mersenne primes.
48. Goldbach’s conjecture states that every even integer greater than 2 is the sum of two prime numbers.
Verify Goldbach’s conjecture for
a. n = 8
b. n = 14
c. n = 28
49. A perfect number is a positive integer n that equals the sum of all divisors less than n. For example, 6 is a
perfect number because 6 = 1 + 2 + 3. Perfect numbers are related to Mersenne primes (see Exercise 47)
in that if p is a prime and 2
p
− 1 is a prime, then 2
p−1
(2
p
− 1) is a perfect number. (This result was proved
by Euclid around 300 b.c.). For example, 6 = 2
1
(2
2
− 1).
a. Prove that 28 is a perfect number by writing it as the sum of its divisors.
b. Write 28 in the form 2
p−1
(2
p
− 1).
50. a. Prove that 496 is a perfect number (see Exercise 49) by writing it as the sum of its divisors.
b. Write 496 in the form 2
p−1
(2
p
− 1).
51. An algorithm exists to find all prime numbers less than some given positive integer n. This method, called
the Sieve of Eratosthenes, was discovered by Eratosthenes, a student of Plato. To carry out this algorithm,
list all integers from 1 through n − 1. Then make repeated passes through the list, on the first pass crossing
out all multiples of 2 that are greater than 2. On the second pass cross out all multiples of 3 that are greater
than 3. On the next pass, cross out all multiples of 5 that are greater than 5, and so forth for all primes less
than !n. The numbers remaining when this process terminates are the primes less than n. Use the Sieve
of Eratosthenes to find all prime numbers less than 100.
52. a. Compute the square of 11.
b. Compute the square of 111.
c. Prove that any n-digit number consisting of all 1’s, when squared, produces the number
123 … (n − 1)n(n − 1) … 321. A number that reads the same forward and backward is called a
palindrome.
53. Sudoku puzzles are popular number-based puzzles. A game consists of a 9 × 9 grid made up of nine 3 × 3 blocks. Each row
and each column of the game must contain exactly one of the 9
digits 1 − 9; furthermore, each 3 × 3 block must contain exactly
one of the digits 1 through 9. Following is a sample puzzle, used
by permission from Web Sudoku at http://www.websudoku.com,
where you can generate puzzles at any of four levels of difficulty.
Try completing this puzzle.
2
2
2
2
2
2
5
5
5
5
3
3
3
3
8
8
8
8
8
9
9
9
4
4
4
4
6
1
1
1
1
7
7
7
7
Proofs, Induction, and Number Theory
prime. The largest known prime number as of June 2013 is 2
57,885,161
− 1, a Mersenne prime. There happens to be a particularly efficient algorithm for testing numbers of the form 2
p
− 1 for primality, which is
why almost all of the largest known primes are Mersenne primes. In recent years, most of these Marsenne
primes have been discovered (and verified) by the GIMPS (Great Internet Mersenne Prime Search) distributed computing project, a worldwide group of volunteers who collaborate over the Internet to test for
Mersenne primes.
Find the first 4—the 4 smallest—Mersenne primes.
48. Goldbach’s conjecture states that every even integer greater than 2 is the sum of two prime numbers.
Verify Goldbach’s conjecture for
a. n = 8
b. n = 14
c. n = 28
49. A perfect number is a positive integer n that equals the sum of all divisors less than n. For example, 6 is a
perfect number because 6 = 1 + 2 + 3. Perfect numbers are related to Mersenne primes (see Exercise 47)
in that if p is a prime and 2
p
− 1 is a prime, then 2
p−1
(2
p
− 1) is a perfect number. (This result was proved
by Euclid around 300 b.c.). For example, 6 = 2
1
(2
2
− 1).
a. Prove that 28 is a perfect number by writing it as the sum of its divisors.
b. Write 28 in the form 2
p−1
(2
p
− 1).
50. a. Prove that 496 is a perfect number (see Exercise 49) by writing it as the sum of its divisors.
b. Write 496 in the form 2
p−1
(2
p
− 1).
51. An algorithm exists to find all prime numbers less than some given positive integer n. This method, called
the Sieve of Eratosthenes, was discovered by Eratosthenes, a student of Plato. To carry out this algorithm,
list all integers from 1 through n − 1. Then make repeated passes through the list, on the first pass crossing
out all multiples of 2 that are greater than 2. On the second pass cross out all multiples of 3 that are greater
than 3. On the next pass, cross out all multiples of 5 that are greater than 5, and so forth for all primes less
than !n. The numbers remaining when this process terminates are the primes less than n. Use the Sieve
of Eratosthenes to find all prime numbers less than 100.
52. a. Compute the square of 11.
b. Compute the square of 111.
c. Prove that any n-digit number consisting of all 1’s, when squared, produces the number
123 … (n − 1)n(n − 1) … 321. A number that reads the same forward and backward is called a
palindrome.
53. Sudoku puzzles are popular number-based puzzles. A game consists of a 9 × 9 grid made up of nine 3 × 3 blocks. Each row
and each column of the game must contain exactly one of the 9
digits 1 − 9; furthermore, each 3 × 3 block must contain exactly
one of the digits 1 through 9. Following is a sample puzzle, used
by permission from Web Sudoku at http://www.websudoku.com,
where you can generate puzzles at any of four levels of difficulty.
Try completing this puzzle.
2
2
2
2
2
2
5
5
5
5
3
3
3
3
8
8
8
8
8
9
9
9
4
4
4
4
6
1
1
1
1
7
7
7
7