TIFR CSE 2018 | Part B | Question: 12

Question

Consider the following statements:

1. For every positive integer $n,$ let $\#{n}$ be the product of all primes less than or equal to $n.$
    Then, $\# {p}+1$ is a prime, for every prime $p.$
2. $\large\pi$ is a universal constant with value $\dfrac{22}{7}.$
3. No polynomial time algorithm exists that can find the greatest common divisor of two integers given as input in binary.
4. Let $L \equiv \{x \in \{0,1\}^{*}\mid x \text{ is the binary encoding of an integer that is divisible by 31}\}$
   Then, $L$ is a regular language.

Then which of the following is TRUE ?

• A. Only statement (i) is correct.
• B. Only statement (ii) is correct. 
• C. Only statement (iii) is correct.
• D. Only statement (iv) is correct. 
• E. None of the statements are correct.

Comments

option 2?

Answer 1

π is not equal to 22/7

https://math.stackexchange.com/questions/93222/is-22-7-equal-to-the-pi-constant

For (i), consider $n=9$. Now, we get product of primes less than $9$ as $\#n = 2\times 3\times 5\times 7\times 9 = 1890.$ Now $\#n+1 = 1891$ is not a prime as $1891 = 31 \times 61.$  (This example might be difficult to arrive during exam, but this option could have been eliminated by good intuition or by seeing that other there are better other options).

We can construct dfa for binary string divisible by 31 

https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n

Option 4

Comments

@Rameez Raza.. I also marked D.. But I was confused between A and D.. In option A,  I took some values of p then it was satisfying.. But I was not sure it will satisfy for all values of p.. How to prove it mathematically??

---

As I saw option 2 is wrong

Then

I checked option 4

I eliminated other option

---

Can you make a DFA for 4? If yes, can you please share?

---

https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n

---

For statement (i) ,Please refer https://www.math.utah.edu/~pa/math/q2.html

---

when n = 9

then #n will be =2 X 3 X 5 X 7 = 210

and 211 is prime

---

@ankitgupta.1729

what about option 3)?

I think it is wrong, because we can write C code for GLB and then make it binary. So, it is possible

---

@Rameez so 9 is prime? you have multiplied it.

---

9 is not a prime number! A better example needed!

---

you can take p=13 as described in the above image.

$2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1$ is not prime