8
$\begingroup$

I am asked to determine whether the number $11111$ is prime. Upon using the divisibility tests for the numbers 1 to 11, I couldn't find anything that divides it, so I assumed that it is prime. However, it apparently isn't prime. So what is the procedure to determine whether $11111$ is prime?

Thank you for any help.

$\endgroup$
  • 1
    $\begingroup$ Why would you stop checking at $11$? $\sqrt {11111}>105$. $\endgroup$ – lulu Aug 23 '18 at 1:59
  • $\begingroup$ @Lulu Because it's not feasible to keep checking by hand. Or is there a way to check? That's why I'm asking. $\endgroup$ – The Pointer Aug 23 '18 at 2:00
  • 2
    $\begingroup$ Primality checking is really, really hard. There aren't short cuts. There are sophisticated tests you could use but with a very small number like this, those tests take more time than blind testing does. $\endgroup$ – lulu Aug 23 '18 at 2:01
  • $\begingroup$ @Lulu So there's no simple way to check whether $11111$ is prime by hand? That's weird, because this was given in a problem set, so I assumed there was such a way. $\endgroup$ – The Pointer Aug 23 '18 at 2:02
  • 3
    $\begingroup$ Of course it's feasible to check it by hand. It just takes some time and is tedious. In this case you only need to check divisibility by numbers ending in 1, 3, 7, 9 up to 105. That's about 40 trial divisions. Then you will see that $11111 = 41\cdot 271$. $\endgroup$ – Hans Engler Aug 23 '18 at 2:05
9
$\begingroup$

Best I can do:

Let $p$ be a prime dividing $11111$. Then I claim that $p\equiv 1 \pmod 5$

Pf: Indeed, $11111=\frac 19\times (10^5-1)$ so $p\,|\,11111\implies p\,|\,10^5-1$ which implies that $10$ has order $5\pmod p$. Thus $5\,|\,p-1$ and we are done.

Thus you should just check $11,31,41\cdots$ and stop since $41$ already works.

$\endgroup$
4
$\begingroup$

Here is a list for test of prime factor of less than $50$.

Test for divisibility by $41$. Subtract four times the last digit from the remaining leading truncated number. If the result is divisible by $41$, then so was the first number. Apply this rule over and over again as necessary.

$$1111-4(1)=1107$$ $$110-4(7)=110-28=82$$ $$8-4(2)=0$$

The number is divisible by $41$.

$\endgroup$
4
$\begingroup$

Not a clean method though but I used Fermat's factorization to find that,

$(105)^2<11111<(106)^2$

Now applying the fact that a perfect square should end only in $0,1,4,5,6,9$, concentrate only on those numbers, the difference of whose square and $11111$ give these digits in the last place. For instance, omit $113,123,133,143$ because the squares of these numbers end with $9$ and would result in $8$ as the last digit and thus this difference will not be a perfect square.

Similarly omit numbers like $112, 122, 132, 142, 152$ (Can you see the reason why?)

On omitting more of such numbers and a little bit of trial, we find that $(156)^2 - 11111 = 13225=(115)^2$

Therefore, $11111 = (156-115)(156+115) = 41.271$

$\endgroup$
3
$\begingroup$

If an integer is all $1$s, then it's of the form $$\frac{10^n - 1}{9},$$ which we notate $R_n$ either for convenience or to be dull, take your pick. For your number, then, we have $n = 5$. Since $5$ is prime, $11111$ could be prime.

Notice that $R_n$ is divisible by $11$ if $n$ is even. Also notice that $R_n$ is divisible by $3$ if $n$ is a multiple of $3$. And $R_n$ is divisible by $41$ is $n$ is a multiple of $5$.

How am I coming up with those? I just know, I'm a demon, and if I don't know, I ask a wood nymph. But if I was just a mere mortal like you, I would look in Sloane's OEIS and notice the remark "These indices $p$ must also be prime." Meaning that if $R_n$ is prime, then so is $n$.

Wait, there's another way a mere mortal like you could have figured this one out: simple trial division. Since $\sqrt{11111} \approx 105.4$, you only need to try dividing $11111$ by each prime from $3$ to $103$.

If you had just kept going in ascending order, you would have hit upon $41$. Betsy DeVos is doing a great job. Mwahahahahahahahahahaha!

$\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.