Determining Whether the Number $11111$ is Prime. Used Divisibility Tests.

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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$

Answer 4

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!