Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many "$1$" is need at least for a decimal number,which is consisting of "$0$" and "$1$" and divisible by $p$?

If $p=2^k\cdot d+1$, and $10^d\equiv 1 \pmod p$,then $10^n\equiv -1 \pmod p$ has no solution, so $10^n+1$ is never divisible by $p$, so two "$1$" is not enough,but since $\dfrac{10^{p-1}-1}{9}=11\cdots 111\equiv 0 \pmod p$,so $p-1$ is awlays enough,in fact,$ord(10,p)$ is enough,but may be not the least.

In When is it solvable:$10^a+10^b\equiv -1 \pmod p$ , I asked that when three "$1$" is need at least,I think I should ask this original problem here,because this is more general and why I asked that question.

Assume $(10,p)=1.$

Two "$1$" is need at least for $p=7, 11, 13, 17, 19, 23, 29, 47, 59, 61, 73, 89, 97, 101, 103,\cdots$

Three "$1$" is need at least for $p=3, 31, 37, 43, 53, 67, 71, 83, 107, 151, 163, 173, 191, 199,\cdots$

Four "$1$" is need at least for $p=79, 733,\cdots$

Thank you!

share|improve this question
    
    
@lab bhattacharjee Thank you for the links!But they are both different to this, my question is how to find the least number of "$1$",neither to find the least number which is divisible by p,nor to prove that there is such a number.I think this problem to more worth to consider´╝îbecause we can answer it easily whether two "1" is need at least. –  Next May 19 '13 at 7:22
    
If the number must end in "$1$" then $2$ is impossible, otherwise $2$ and $5$ only need one "$1$". –  WimC May 19 '13 at 7:25
    
@WimC we only consider the case $(10,p)=1$,I said it in another my question..Thanks for your suggest,I will edit it. –  Next May 19 '13 at 7:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.