9
$\begingroup$

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.

  • 0
    I love how this elementary (but very interesting) question has three totally different proofs alreafy!2012-05-09

3 Answers 3

5

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.

2

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

  • 0
    ty, fixed, initially I thought one needs to discuss separately the case when it is divisible by 9 and only by 3 :)2012-05-09
2

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.