Chapter - introduction,
I have started reading a book - How to Prove it (author: Daniel J. Velleman). I shall be posting its solutions from this post onwards, each titled with corresponding chapter. This post contains solutions for the introduction section of the book.
Note: In this book natural numbers include $0$ also. But it seems like in some places in the proofs, I messed up with this convention. In some placed I might have considered $N$ includes $0$ while in other places vice versa. Please point out to me, I will correct to use the book’s version of $\mathbb N$ in all the places.
Soln.1(a)
Using theorem:
We have \( n = 3 \times 5 \), Taking \( a = 3 \) and \( b = 5 \)
\( \Rightarrow x = 2^5 - 1 = 31 \) and \( y = 1 + 2^{1 \cdot 5} + 2^{2 \cdot 5} = 1057 \)
\( \Rightarrow x = 31, y = 1057 \)
Soln.1(b)
We can use the same theorem again. Now we have \( n = 32767 = 31 \times 1057 \). Taking \( b = 31 \) gives \( x = 2^b - 1 = 2^{31} - 1 = 2147483647 \)
Soln.2
Table for \( 3^n - 1\) :
\( n \) | Is \( n \) prime? | \( 3^n - 1 \) | Is \( 3^n - 1 \) is prime? |
---|---|---|---|
1 | no | 2 | yes |
2 | yes | 8 | no |
3 | yes | 26 | no |
4 | no | 80 | no |
5 | yes | 242 | no |
6 | no | 728 | no |
7 | yes | 2186 | no |
8 | no | 6560 | no |
9 | no | 19682 | no |
10 | no | 59048 | no |
11 | yes | 177146 | no |
12 | no | 531440 | no |
13 | yes | 1594322 | no |
14 | no | 4782968 | no |
It can be observed from above table that \( 3^n - 1 \) is always an even number and it is never prime except for \( n = 1 \).
Table for \( 3^n - 2^n \) :
\( n \) | Is \( n \) prime? | \( 3^n - 2^n \) | Is \( 3^n - 2^n \) is prime? |
---|---|---|---|
1 | no | 1 | no |
2 | yes | 5 | yes |
3 | yes | 19 | yes |
4 | no | 65 | no |
5 | yes | 211 | yes |
6 | no | 665 | no |
7 | yes | 2059 | no |
8 | no | 6305 | no |
9 | no | 19171 | no |
10 | no | 58025 | no |
11 | yes | 175099 | no |
12 | no | 527345 | no |
13 | yes | 1586131 | no |
14 | no | 4766585 | no |
15 | no | 14316139 | no |
16 | no | 42981185 | no |
17 | yes | 129009091 | yes |
It can be observed that if \( n \) is not prime than \( 3^n - 2^n \) is also not prime. Also it is observed that \( 3^n - 2^n \) is prime only if \( n \) is prime.
Soln3
Theorem 3 says:
Proof of this theorem is done by contradiction. It was shown if \( m = p_1 \cdot p_2 \cdot p_3 … p_n + 1 \) where \( p_1, p_2, p_3 … p_n \) are finite(assumption) list of prime numbers. Now it can be seen that \( m \) is a prime number which contradicts the assumption of finite prime numbers.
(a) Use this method to find a prime different from 2, 3, 5, and 7.
Lets find \( m = 2 \times 3 \times 5 \times 7 + 1 = 210 + 1 = 211 \)
Now, if \( 2, 3, 5, 7 \) is the list of all prime numbers known(except m), than from the proof \( m = 211 \) can be the new prime number.
But this is not the case here as there are infinite prime numbers. Thus \( m \) may not result in a prime number.
If we use all prime numbers less than a given number(say \( g \) ), for computing \( m \), than from the steps of the proof we are sure that \( m \) is not divisible by any of the numbers less than \( g \). Thus if m is not prime than all of its prime-factors must be greater than \( g \).
As, \( 211 \) is a big number to manually check from all prime-number greater than 7 for prime-factors of \( 211 \), we may take a smaller set say \( 2, 3, 5 \) to find \( m = 2 \times 3 \times 5 + 1 = 31 \) and check for prime-factors of m greater than \( 5 \).
After checking, \( 31 \) is a prime number.
(b) Use this method to find a prime different from 2, 5, and 11.
Using the method from above, taking only \( 2 \) results \( m = 2 + 1 = 3 \) which is a prime number.
Now taking only \( 2, 3 \) results \( m = 2 \times 3 + 1 = 7 \) which is also a prime number.
Soln4
We may use following theorem here:
Its proof shows that a set of such consecutive integers can be
Putting \( n = 5 \Rightarrow x + i = 6! + 2 + i = 722 + i \) which gives us 722, 723, 724, 725, 726
Soln5
Table:
\( n \) | Is \( n \) prime? | \( 2^n - 1 \) | Is \( 2^n - 1 \) is prime? |
---|---|---|---|
1 | no | 1 | no |
2 | yes | 3 | yes |
3 | yes | 7 | yes |
4 | no | 15 | no |
5 | yes | 31 | yes |
6 | no | 63 | no |
7 | yes | 127 | yes |
8 | no | 255 | no |
9 | no | 511 | no |
10 | no | 1023 | no |
11 | yes | 2047 | no |
12 | no | 4095 | no |
The discussion on p.5 says that if \( 2^n - 1 \) is prime than \( 2^{n-1} \cdot (2^n - 1) \) is a perfect number,
For \( n = 3 \Rightarrow 2^{3-1} \cdot (2^3 - 1) \Rightarrow 4 \times 7 = 28 \).
Similarly, for \( n = 5 \Rightarrow 2^{5-1} \cdot (2^5 - 1) \Rightarrow 16 \times 31 = 496 \).
Soln6
There are no more such prime triplets. From wiki:
In mathematics, a prime triplet is a set of three prime numbers of the form (p, p + 2, p + 6) or (p, p + 4, p + 6). With the exceptions of (2, 3, 5) and (3, 5, 7), this is the closest possible grouping of three prime numbers, since one of every three sequential odd numbers is a multiple of three, and hence not prime. wiki
which is true, as all prime numbers except \( 2 \) are odd and no three consecutive odd numbers can be prime as at-least one of them must be a multiple of three.