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.

I have found this statement ,can you help me to prove this.

If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit.

OBJECTIVE: Now you are given the number and the only allowable digit, you should report the number of digits of such multiple.

For example you have to find a multiple of 3 which contains only 1's. Then the result is 3 because is 111 (3-digit) divisible by 3. Similarly if you are finding some multiple of 7 which contains only 3's then, the result is 6, because 333333 is divisible by 7.

share|improve this question
    
I love how this elementary (but very interesting) question has three totally different proofs alreafy! –  Simon Markett May 9 '12 at 22:01
add comment

3 Answers

Let $n$ be a positive integer. Then $\varphi(n)$ is defined as the number of integers in the interval $[0,n-1]$ which are relatively prime to $n$, that is, have no factor greater than $1$ in common with $n$. The function $\varphi$ is called the Euler phi-function. The following result, due to Euler, generalizes Fermat's (little) Theorem.

Theorem: (Euler) Suppose that $a$ is relatively prime to $n$. Then $a^{\varphi(n)}\equiv 1\pmod{n}$. Equivalently, $n$ divides $a^{\varphi(n)}-1$.

Proofs of Euler's Theorem can be found in any book on Elementary Number Theory. In the Wikipedia article on Fermat's Theorem, you will find, fairly deep into the article, a discussion of how to adapt one of the standard proofs of Fermat's Theorem.

Suppose now that $n$ is divisible neither by $2$ nor by $5$, and let $a=10$. Then $a$ and $n$ are relatively prime, and therefore $$10^{\varphi(n)}\equiv 1\pmod{n}.$$ For any $k\ge 1$, the number $10^k-1$ has decimal representation that consists only of $9$'s. So we have shown that if $n$ is divisible neither by $2$ nor by $5$, then the number consisting of $\varphi(n)$ $9$'s is divisible by $n$.

That gives you a start on solving the problem you are looking at. To use the result, you might want to look up a formula for $\varphi(n)$ in terms of the prime factorization of $n$.

Now we add more detail. There are some small complications in that in your problem, a specific digit is also given. That makes little difference to the analysis, but does affect numbers $n$ that are divisible by $3$ (when the given digit is $3$, $6$, or $9$) and numbers $n$ divisible by $7$ (when the given digit is $7$).

We address a number-theoretically more important complication. It is quite possible that a number "cheaper" than $\varphi(n)$ will do the job. In our case, the number $n$ is odd. Let $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ where the $p_i$ are distinct odd primes. Let $\lambda$ be the least common multiple of the numbers $(p_i-1)p_i^{a_i-1}$. Then it turns out that the number consisting of $\lambda$ $9$'s is divisible by $n$. For numbers $n$ that are divisible by more than $1$ odd prime, we have $\lambda<\varphi(n)$. For details about these ideas, you might want to look into the Carmichael function.

However, $\varphi(n)$, or the (usually improved) estimate $\lambda$ given in the preceding paragraph, will in general not give you the least exponent that does the job.

But once you have found a number $k$ such that $10^k\equiv 1 \pmod{n}$, any cheaper exponent must be a divisor of $k$. For large $n$, this observation can considerably simplify the search for the cheapest exponent. For enormous $n$, the problem can be exceedingly hard computationally.

share|improve this answer
add comment

And yet another proof which also gives an algorithm to compute the (minimal) number of digits and a lower bound. Given an integer $a$ with the desired properties and the allowed digit $0\leq z\leq 9$ we want to find a solution for $$a\cdot x=z\cdot\sum_{i=0}^n10^i$$ such that x is an integer and $n$ minimal. Consider $a$ as an 10-adic number. Then the given properties mean that $a$ is a unit. Hence we want to solve $$x=a^{-1}\cdot z\cdot \sum_{i=0}^n10^i.$$ Assume that $a\neq 1$ (the case $a=1$ is trivial) then we have

  1. $a^{-1}$ is represented by an infinite sequence $0\leq a_i\leq 9$, and
  2. this sequence is periodic.

(These properties might need a proof, but the argument is very easy).

All we have to do is find $n$ such that $a^{-1}\cdot z\cdot \sum_{i=0}^n10^i$ is represented by a finite sequence and therefore an honest to god integer. It is easy to see that the smallest $n$ with this property is a multiply of the length of the period $l$. It should be obvious after multiplying with the factor $\sum_{i=0}^l10^i$ which multiply we have to choose. (I guess one can improve this statement.)

The example: Given $a=3$ and $z=1$, then $a^{-1}=a^{-1}\cdot z$ has the 10-adic representation $7\cdot1+6\cdot10^1+\sum_{i=2}^\infty(3\cdot 10^i)$. The length of the period is $1$. We see $3\cdot (7\cdot1+6\cdot10^1+\sum_{i=2}^\infty(3\cdot 10^i))=37$ is the smallest possible number.

Given $a=7$ and $z=3$ we find that $3\cdot z^{-1}$ has period $6$. This is already the smallest possible number.

share|improve this answer
add comment

Let $a$ be your digit. Let $d = \gcd(a,n)$.

Then

$$n | aaa.a \Leftrightarrow n| a \cdot 111..1 \Leftrightarrow \frac{n}{d} | \frac{a}{d} \cdot 111....11$$

Since $\frac{n}{d}$ and $\frac{a}{d}$ are relatively prime, we get

$$n| aaa...aa \Leftrightarrow \frac{n}{d}|1111...1$$

we break now the problem in 2 cases:

Case 1: $3 \nmid \frac{n}{d}$.

Then

$$n| aaa...aa \Leftrightarrow \frac{n}{d}|1111...1\Leftrightarrow \frac{n}{d}|9999...9 =10^k-1$$

Thus

$$n|aaa...a \Leftrightarrow 10^k \equiv 1 \mod \frac{n}{d} \Leftrightarrow ord_{\frac{n}{d}}(10) |k$$

Thus, $k$ must be a multiple of the order of 10 in $U(Z/ \frac{n}{d} Z)$. In particular

$k= \phi(\frac{n}{d})$ works, and this $k$ is smallest if and only if $10$ is a primitive root modulo $\frac{n}{d}$.

Case 2: $3 \mid \frac{n}{d}$.

Then

$n| aaa...aa \Leftrightarrow \frac{n}{d}|1111...1\Leftrightarrow 9\frac{n}{d}|9999...9 =10^k-1$$

Thus

$$n|aaa...a \Leftrightarrow 10^k \equiv 1 \mod 9\frac{n}{d} \Leftrightarrow ord_{9\frac{n}{d}}(10) |k$$

Thus, $k$ must be a multiple of the order of 10 in $U(Z/ 9\frac{n}{d} Z)$. In particular

$k= \phi(9\frac{n}{d})$ works, and this $k$ is smallest if and only if $10$ is a primitive root modulo $9\frac{n}{d}$. Note that 10 can only be primitive root in this case if $\frac{n}{d} =3^\alpha$ or $\frac{n}{d}=2 \cdot 3^\alpha$.

share|improve this answer
    
ty, fixed, initially I thought one needs to discuss separately the case when it is divisible by 9 and only by 3 :) –  N. S. May 9 '12 at 22:17
add comment

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.