Answers must be correct. Or else it will be flagged. All sub-parts need to be an

ID: 3905078 • Letter: A

Question

Answers must be correct. Or else it will be flagged. All sub-parts need to be answered with step by step process showing all work and reasoning.

YOU MUST PROVIDE ALL ANSWERS AS PER THE QUESTIONS.

DON'T PROVIDE WRONG ANSWERS AND DON'T ANSWER IF YOU DON'T WANT TO ANSWER ALL SUB-PARTS. INCOMPLETE ANSWERS WILL BE FLAGGED

DISCRETE STRUCTURES

Question 3 (16 points) For this question let P1, P2, P3,... e the prime numbers in order from smallest to larO and so on a) Show that pi .P2 Pn + 1 s not always prine. b) Show there exists 1,000,000 consecutive numbers which are not prime.

Explanation / Answer

Part a:

Your question, as I understand it, is "show that not every number of the form p1p2?pn+1 is prime, where pn represents the nth prime number?"

Well, in order to do that, you just need to find some n where this doesn't hold.

For n = 1, you get 2 + 1 = 3, which is prime.
For n = 2, you get 2*3 + 1 = 7, which is prime.
For n = 3, you get 2*3*5 + 1 = 31, which is prime.
For n = 4, you get 2*3*5*7 + 1 = 211, whis is prime.
For n = 5, you get 2*3*5*7*11 + 1 = 2311, whis is prime.
For n = 6, you get 2*3*5*7*11*13 + 1 = 30031, which is composite: it's equal to 59 * 509.

So all you have to do is exhibit this one number 30031.

Let p1 = 2, p2 = 3, and so on, so this list can just be written as
p1, p2, p3, . . . , pn?1, pn.
Multiply all of the pi together and add one, and call the result q:
q = p1 · p2 · p3 · · · pn?1 · pn + 1.
Then q is a positive integer greater than 2, so it’s either prime or composite.
Clearly q is larger than any the primes in p1, p2, . . . pn, so it can’t be somewhere on this list, i.e., q itself is
not prime.
Therefore q must be composite: Let p1 = 2, p2 = 3, and so on, so this list can just be written as
p1, p2, p3, . . . , pn?1, pn.
Multiply all of the pi together and add one, and call the result q:
q = p1 · p2 · p3 · · · pn?1 · pn + 1.
Then q is a positive integer greater than 2, so it’s either prime or composite.
Clearly q is larger than any the primes in p1, p2, . . . pn, so it can’t be somewhere on this list, i.e., q itself is
not always prime, therefore q must be composite.

Part b:

Generic Way

Since we desire "a sequence of n (1000000) consecutive positive integers containing no primes,"
thus denominate these n numbers as: x+0,x+1,...,x+(n?2),x+(n?1).
Thus the objective is to prove: None of these are prime. ? All of these are composite.

Define x:=(n+1)!+2. Then for all 0?i?n?1:
x+i=1?2?3?...?(i+1)(i+2)(i+3)...n(n+1)+2+i=(i+2)[1?2?3?...?(i+1)(i+3)...n(n+1)+1]

We have to find x such that x+i is not a prime number. So x+i must have a non-trivial factor.
The factor will depend on i.
The most natural choice for the factor is i (when i>1).
Now i divides x+i if and only if i divides x.
The problem now is to find x that is divisible by 2,…,n+1.
One option is to let x=(n+1)! and consider consecutive numbers x+2,…,x+(n+1).

Define x:=(n+1)!+2. Then for all 0?i?n?1:
x+i=1?2?3?...?(i+1)(i+2)(i+3)...n(n+1)+2+i=(i+2)[1?2?3?...?(i+1)(i+3)...n(n+1)+1]

with an example :

Let n be any natural number and consider the numbers 2 + (n + 1)!, 3 + (n + 1)!, 4 + (n + 1)!, ....., n + (n + 1)!, (n + 1) + (n + 1)!.

observe that 2 divides the number 2 + (n + 1)!, 3 divives the number 3 + (n + 1)! and n divides the n + (n + 1)! likewise (n + 1) divides (n + 1)!.

In short i divides i + (n + 1)! where i is an element of the set. {2, 3, 4, ..., n, n + 1} the reason been you can always factor out i.

Likewise the numbers 2 + (n + 1)!, 3 + (n + 1)!, 4 + (n + 1)!, ....., n + (n + 1)!, (n + 1) + (n + 1)! are all consecutive and their count is n.

Navigate

Answers must be correct. Or else it will be flagged. All sub-parts need to be an

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Answers must be correct. Or else it will be flagged. All sub-parts need to be an

Question

Explanation / Answer

Related Questions

Navigate