Here is the complete proof taken from this link

enter image description here

How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then resulting string 111 111 is prime. Is this how it should be done it in proofs? The way I see is this. If n(1+b) is not proved for even one set of values then I can say it is not prime. Set of values in this case was n =3 & b = 3.

Is this approach of understanding poofs is right?


The number $n(1+b)$ is not prime because it has 2 divisors greater than 1. These are $(b+1)$ and $n$. I believe that's what is meant here.

  • $\begingroup$ If there is only one state in DFA then because of n>=p, n can be equal to 1. What happens then? Now at least one of factor is 1. @peter.petrov $\endgroup$ – user3461957 Jun 9 '15 at 14:43
  • $\begingroup$ It says n is prime number. So n cannot be 1. $\endgroup$ – peter.petrov Jun 9 '15 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.