3
$\begingroup$

I came up with this allegedly false theorem: Any number in the form $$\underbrace{111...11 }_{n \text{ times}}$$ and $$n \not = 1$$ Is a prime number.

Here is my "proof": if we had taken $$11$$,it is true. And for $111$ is true because it is $$100 + 11$$ And we know that there is no number that divides both $100$ and $11$,therefore it is prime.

So constructively, We see that at any step,there will be no number that divides both $$\underbrace{100...00}_{ n \text{ times}} \quad \text{and} \quad \underbrace{11..111}_{(n-1) \text{ times}}.$$ Where am I going wrong?

$\endgroup$
  • 2
    $\begingroup$ You could also write $111 = 108 + 3$, and there is a number dividing both, $108$ and $3$. Just because you can write a number as the sum of two coprime numbers doesn't mean it's a prime. $\endgroup$ – Daniel Fischer Dec 23 '16 at 11:25
  • $\begingroup$ So if were to determine whether 111 is prime or not what should i do? $\endgroup$ – Logan Luther Dec 23 '16 at 11:28
  • 1
    $\begingroup$ For numbers that small, trial division. For larger numbers, it depends on how sure you want to be, maybe a probabiistic test like Miller-Rabin with enough bases is sufficient, maybe you need a proof. If you need proof, something slower than a couple of rounds of MR, like ECPP, APRCL, AKS is to be looked at. $\endgroup$ – Daniel Fischer Dec 23 '16 at 11:49
3
$\begingroup$

Hint: problem lies in the fact There is no number which divides $100$ and $11$.

There is no number which together divides $5$ and $17$ but still $5+17=22$ is composite

$\endgroup$

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.