Monday, April 12, 2010

how to prove it - intro exercises

Ex-1 (a)
Using the formula
$2^{15} - 1$ = $2^{3*5} -1$
a = 5, b = 3
$2^b -1$ = $2^3 - 1$ = 7

and

$1 + 2^b + 2^{2b} + ... + 2^{(a-1)b}$ = $1 + 2^3 + 2^{2*3} + 2^{3*3} + 2^{4*3}$ = 4681

Ex-1 (b)
$2^{32767} - 1$ = $2^{7*4681} - 1$
b = 7, so
x = $2^7 - 1$ = 127

Ex-2




































n$3^n - 1$$3^n - 2^n$
121
285
32619
48065
5242211
6728665
721862059
865606305
91968219171
105904858025


2 conjectures are:
$3^n - 2^n$ is prime for prime n
$3^n - 1$ is never prime except for n = 1

Ex-3(a)
2*3*5*7 + 1 = 211

Ex-3(b)
2*3*5*7*11 + 1 = 2311

Ex-4
x = (n+1)! + 2 = (5+1)! + 2 = 722
5 consecutive non-prime numbers are x, x + 1, x + 2, x + 3, x + 4 = 722,723,724,725,726

Ex-5
Use: If $2^n - 1$ is prime $\Rightarrow$ $2^{(n-1)}(2^n - 1)$ is perfect number
$2^5 - 1 = 31$ is prime $\Rightarrow$ $2^{(5-1)}(2^5 - 1)$ = 496 is perfect number
$2^7 - 1 = 127$ is prime $\Rightarrow$ $2^{(7-1)}(2^7 - 1)$ = 8128 is perfect number

Ex-6 There are no more triplet primes other than 3,5,7 where adjacent numbers in the list differ by 2.

Proof: I'll prove it by contradiction. Let say p, p+2, p+4 (p > 3)be such a triplet prime list.

Since one of the 3 consecutive numbers has to be divisible by 3, so
one out of p, p+1 or p+2 is divisible by 3. Since p and p+2 are primes by assumption so p+1 is divisible by 3. But then p+4 = (p+1)+3 and hence p+4 should be divisible by 3 and this is a contradiction.

13 comments:

  1. Just noticed - in your solution to Ex 6, 57 is not a prime - it's 19 x 3.

    I was doing the same exercises, and came across this - http://en.wikipedia.org/wiki/Prime_triplet

    ReplyDelete
  2. thanks hrish. Now that I think about it again, I think another list of such triplet primes is not possible and I've added a quick proof for same.

    just curious, what was your answer?

    ReplyDelete
  3. Himanshu, Initially I was under the impression that such a triplet might exist, and it might do so within the first 100 or 150 +ve integers. I actually went through the numbers and noticed the pattern in the wikipedia article I mention. A google search found it for me - so I did not actually prove it myself. Wish I had done that first :)

    ReplyDelete
  4. don't worry, there will be plenty of opportunities :)

    ReplyDelete
  5. BTW in Ex-3(b), the answer is not 111 because 111 is not a prime; It is divisible by 3.

    ReplyDelete
  6. thanks @Niyaz, yes I missed 3 and 7. For the theorem to work I have to include all the primes from 2 to 11. Corrected that now.

    ReplyDelete
  7. Hmm... the answer is correct, but this method is still not guaranteed to give you a prime number. (If it did, then it would be easy to find a larger prime number than the current largest prime number right? http://en.wikipedia.org/wiki/Largest_known_prime_number )

    My point was that 111 is not a prime number. 111 = 3 * 37, which gives us 37 (or 3) as our new prime number which the question asked us to find.

    If you look at the proof of theorem 3, you can see that there are two cases in it. First when p1.p2.p3....pn + 1 is a prime and the second case where it is not a prime. I think Ex-3(a) wants us to use case 1 while Ex-3(b) wants us to use case 2.

    ReplyDelete
  8. @Niyaz: No, the method is guaranteed to give you a prime.
    2*3*5*....p_n + 1 will always be a prime number(however, ensure that you are taking all the primes smaller than and equal to p_n, you can't miss any). I guess, finding the largest prime is limited by the computational resources and not by theory. As theorem is all about proving that there are infinitely many primes.

    ReplyDelete
  9. E6 = 13# + 1 = 30031 = 59 x 509 is the first composite Euclid number, demonstrating that not all Euclid numbers are prime.

    http://en.wikipedia.org/wiki/Euclid_number

    ReplyDelete
  10. Thanks for correcting.. Yes, Agree, I was wrong.

    There exist infinite primes *does not* imply all euclid numbers are prime(which looked like true due to the way theorem was proved).

    ReplyDelete
  11. Stumbling across this in 2013 while working through the introduction; I think the above discussion should be mandatory reading after attempting the exercise!

    ReplyDelete
  12. In fact, 3^n-2^n is a multiple of 5 whenever n is even. (Can be proved by induction.)

    ReplyDelete
  13. The conjecture that '3^n-2^n is a prime number when n is prime' is not valid. This can be seen for n=7 where 3^7-2^7=2059=29*71.

    ReplyDelete