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.

Okay, so I have worked on this problem and even though I can see it is true I just don't know how to show it.

Here it goes.

Question:

Show that every odd prime except $5$ divides some number of the form $111 \ldots 11$ ($k$ digits, all ones).

Thank you my friends!

share|improve this question
    
See this recent related question. In fact it is only coprimality with $10$ that matters. –  Marc van Leeuwen Jul 1 '12 at 7:01

4 Answers 4

up vote 4 down vote accepted

Given an odd prime $p$ it is known (Fermat's Little Theorem) that $p$ divides $10^{p-1}-1$, hence, $(10^{p-1}-1)/9$ except you have to note 3 divides 111).

share|improve this answer
    
YES! thank you! I had this and I knew that I had to apply Fermat's theorem somehow but I just could not for the life of me make the connection! Thanks!!! –  HowardRoark Jul 1 '12 at 3:23

By a simple Pigeonhole argument one can prove much more: if $\rm\:n\:$ is coprime to $10\,$ then every integer with at least $\rm\:n\:$ digits $\ne 0$ has a contiguous digit subsequence that forms an integer $\ne 0$ divisible by $\rm\:n.\:$ In your case the divisor $\rm\:n,\,$ being an odd prime $\ne 5,\,$ is coprime to $10,\,$ therefore the $\rm\,n\,$ digit number $\,111\ldots111\,$ does the trick, i.e. some subsequence $\,11\ldots11\,$ is divisible by $\rm\,n.$

share|improve this answer

It is of course okay to use Fermat's Little Theorem, but it can be done by an even more elementary argument. Saying your $p$ divides the number, say $mp$, formed with $k$ digits $1$ means that $10^k=9mp+1$, so one searches $k$ such that $10^k\equiv1\pmod{9p}$. Now $9p$ is coprime to $10$ if $p$ is, which implies that mulitplication by $10$ is an invertible operation on integers modulo $9p$ (you can find a multiplicative inverse of $10$ using Euclid's algorithm, but its existence is all that matters). Now imagine writing the powers $10^0=1,10^1,10^2,\ldots$ reduced modulo $9p$ until the first time some number (more precisely some class modulo $9p$) already present re-appears. If that number were not $1$, then inverting the multiplication by $10$ on the two equal numbers immediately gives a contradiction, so it is in fact the number has to be $1$. This gives your $k$.

So you don't have to use the catch-all exponent $\phi(9p)$ (the order of the group) that will work for all invertible elements modulo $9p$ at once. However in practice, when $9p$ is large but not so huge that you have difficulty calculating $\phi(9p)$, it helps a lot, if your goal is to explicitly find the least possible $k$, to know that it has to divide $\phi(9p)$.

share|improve this answer

Let F(r,b)=$(111....111)_b$ (r digits, all ones) be a number in base b. So, F(r,b)=$∑_{0≤t<r}b^t =(b^r-1)/(b-1)$. If r|φ($p^k$) where p is prime, then $p^k$ will divide $(b^r-1)$. Again, $p^k$ will also divide $(b^r-1)/(b-1)$ if p∤(b-1). So, $p^k$ will divide $(111....111)_b$ (r digits, all ones) if (p,b-1)=1 and r|φ($p^k$). If (p,b-1)≠1, then p|(b-1), let k be the highest power of p, that divides (b-1). So b is of the form 1+$p^kq$ where (p,q)=1. Then F(r,b)=$∑_{0≤t<r}b^t=∑_{0≤t<r}{(1+p^kq)}^t$≡r(mod $p^k$) as ${(1+p^kq)}^t≡1(mod\ p^k$) for all integral t≥0. Then, $p^k$ will divide F(r,b) if r|$p^k$ and $p^k|(b-1)$.

Let $p^i$ divides $(a^s-1)/(a-1)$, so $a^s$=1+(a-1)$p^i$d for some integer d. Then, $a^{sp}=(a^s)^p=(1+(a-1)p^id)^p=1+pC_1(a-1)p^id+...+(a-1)^pp^{ip}d^p$. Then,$(a^{sp}-1)/(a-1)$ is divisible by $p^{i+1}$. So, if $p^i$|F(s,a) then $p^{i+1}$ will divide F(sp,a) i.e., $(111....111)_a$ (sp digits, all 1's in base a).

Clearly, we shall find some r(the period or the length of 1's) relatively prime with b, such that $p^{m}$ where m is a natural number will divide F(r,b) for any base b. Now, if n=$p^aq^b$ and $p^a$ divides F($r_p$,b) which is (111...111)$_b$ with $r_p$ digits & $q^b$ divides F($r_q$,b), then n=$p^aq^b$ will divide (111...111)$_b$ with lcm($r_p$,$r_q$) digits and so on for any number n=$p^aq^br^c...\ $ co-prime with the base b.

share|improve this answer

Your Answer

 
discard

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

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