2
$\begingroup$

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!

4 Answers 4

4

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

  • 0
    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!!!2012-07-01
4

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

1

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

1

Let F(r,b)=$(111....111)_b$ (r digits, all ones) be a number in base b. So, F(r,b)=$∑_{0≤t. 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(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.