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?


closed as off-topic by Raphael Jun 9 '15 at 9:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Crossposted on Mathematics. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – Raphael Jun 9 '15 at 9:16
  • $\begingroup$ Since this is at heart a pure mathematics question, I'm closing as offtopic. $\endgroup$ – Raphael Jun 9 '15 at 9:16

$n(1+b)$ is not prime for any integers $n>1$ and $b\geq 1$, simply because it is divisible by both $n$ and $(b+1)$, and the conditions on $n$ and $b$ guarantee that neither of these factors is $1$.

Note that we must have $n>1$, since $n\geq p$ where $p$ is the number of states in an automaton which we suppose to exist that accepts the given language. Since a $1$-state automaton can only accept $\emptyset$ or $\Sigma^*$, we must have $p>1$.

  • 1
    $\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. $\endgroup$ – user3461957 Jun 9 '15 at 14:42
  • $\begingroup$ @user3461957 Good point. Edited. $\endgroup$ – David Richerby Jun 9 '15 at 15:57

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