Si un entero no divisible por 2 o 5

Question

He encontrado esta declaración ,me puedes ayudar para probar esto.

Si un entero no divisible por 2 o 5, algunos múltiplo de ese número en notación decimal es una secuencia de sólo un dígito.

OBJETIVO: Ahora se le da el número y el permitido sólo dígitos, usted debe reportar el número de dígitos de estas múltiples.

Por ejemplo, usted tiene que encontrar un múltiplo de 3 que contiene sólo 1. A continuación, el resultado es 3 porque es 111 (3 dígitos) divisible por 3. Del mismo modo, si usted está encontrando cierto múltiplo de 7, el cual contiene sólo 3 entonces, el resultado es 6, porque 333333 es divisible por 7.

Answer 1

Deje $n$ ser un entero positivo. A continuación, $\varphi(n)$ se define como el número de enteros en el intervalo de $[0,n-1]$ que son relativamente primos a $n$, es decir, no tienen ningún factor mayor que $1$ en común con $n$. La función de $\varphi$ se llama la phi de Euler-función. El siguiente resultado, debido a Euler, generaliza de Fermat (poco) Teorema.

Teorema: (Euler) Supongamos que $a$ es relativamente primer a $n$. A continuación,$a^{\varphi(n)}\equiv 1\pmod{n}$. Equivalentemente, $n$ divide $a^{\varphi(n)}-1$.

Pruebas de el Teorema de Euler se puede encontrar en cualquier libro Elemental de la Teoría de números. En el artículo de Wikipedia sobre el Teorema de Fermat, usted encontrará, bastante profundo en el artículo, una discusión de cómo adaptar una de las pruebas del Teorema de Fermat.

Supongamos ahora que $n$ es divisible ni por $2$ ni $5$, y deje $a=10$. A continuación, $a$ $n$ son relativamente primos, y por lo tanto $$10^{\varphi(n)}\equiv 1\pmod{n}.$$ Para cualquier $k\ge 1$, el número de $10^k-1$ tiene representación decimal que consta sólo de $9$'s. Así hemos demostrado que si $n$ es divisible ni por $2$ ni $5$, entonces el número que consta de $\varphi(n)$ $9$'s es divisible por $n$.

Que le da un inicio en resolver el problema que usted está buscando. Utilice el resultado, es posible que desee buscar una fórmula para $\varphi(n)$ en términos de la descomposición en factores primos de a $n$.

Ahora podemos añadir más detalles. Hay algunas pequeñas complicaciones que en su problema, un dígito. Que hace una pequeña diferencia para el análisis, pero afecta a los números de $n$ que son divisibles por $3$ (cuando la cifra es $3$, $6$, o $9$) y los números de $n$ divisible por $7$ (cuando la cifra es $7$).

Estamos frente a un número teóricamente más importante complicación. Es muy posible que un número "más barato" que $\varphi(n)$ va a hacer el trabajo. En nuestro caso, el número de $n$ es impar. Vamos $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ donde el $p_i$ son distintos de los números primos impares. Deje $\lambda$ ser el mínimo común múltiplo de los números de $(p_i-1)p_i^{a_i-1}$. Luego resulta que el número que consta de $\lambda$ $9$'s es divisible por $n$. Para los números de $n$ que son divisibles por más de $1$ impares primos, tenemos $\lambda<\varphi(n)$. Para más detalles acerca de estas ideas, es posible que desee buscar en el Carmichael función.

Sin embargo, $\varphi(n)$ o la (generalmente mejorada) estimación $\lambda$ dada en el párrafo anterior, en general no dan el mínimo exponente que hace el trabajo.

Pero una vez que han encontrado un número $k$ tal que $10^k\equiv 1 \pmod{n}$, todo más barato exponente debe ser un divisor de a $k$. Para un gran $n$, esta observación puede simplificar considerablemente la búsqueda de la más barata exponente. Por el enorme $n$, el problema puede ser extremadamente difícil de cómputo.

Answer 2

Deje $a$ ser su dígitos. Deje $d = \gcd(a,n)$.

Entonces

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

Desde $\frac{n}{d}$ $\frac{a}{d}$ son relativamente primos, obtenemos

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

partimos ahora el problema en 2 casos:

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

Entonces

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

Así

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

Por lo tanto, $k$ debe ser un múltiplo de la orden de 10 $U(Z/ \frac{n}{d} Z)$. En particular

$k= \phi(\frac{n}{d})$ obras, y esto $k$ es el más pequeño, si y sólo si $10$ es una raíz primitiva módulo $\frac{n}{d}$.

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

Entonces

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

Así

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

Por lo tanto, $k$ debe ser un múltiplo de la orden de 10 $U(Z/ 9\frac{n}{d} Z)$. En particular

$k= \phi(9\frac{n}{d})$ obras, y esto $k$ es el más pequeño, si y sólo si $10$ es una raíz primitiva módulo $9\frac{n}{d}$. Tenga en cuenta que 10 sólo puede ser raíz primitiva en este caso si $\frac{n}{d} =3^\alpha$ o $\frac{n}{d}=2 \cdot 3^\alpha$.

Answer 3

Y aún otra prueba, que también le da un algoritmo para calcular el (mínimo) número de dígitos y un límite inferior. Dado un entero $a$ con las propiedades deseadas y el permitido de dos dígitos $0\leq z\leq 9$ queremos encontrar una solución para $$a\cdot x=z\cdot\sum_{i=0}^n10^i$$ tal que x es un entero y $n$ mínimo. Considere la posibilidad de $a$ 10-ádico número. A continuación, las propiedades especificadas significa que $a$ es una unidad. Por lo tanto queremos resolver $$x=a^{-1}\cdot z\cdot \sum_{i=0}^n10^i.$$ Suponga que $a\neq 1$ (en el caso de $a=1$ es trivial), entonces tenemos

1. $a^{-1}$ está representado por una infinita secuencia $0\leq a_i\leq 9$, y
2. esta secuencia es periódica.

(Estas propiedades se podría necesitar una prueba, pero el argumento es muy fácil).

Todo lo que tenemos que hacer es encontrar a $n$ tal que $a^{-1}\cdot z\cdot \sum_{i=0}^n10^i$ está representado por una secuencia finita y, por tanto, un honesto a dios entero. Es fácil ver que los más pequeños de $n$ con esta propiedad es una de multiplicar la longitud del período de $l$. Debe ser obvio que después de multiplicar por el factor $\sum_{i=0}^l10^i$ que se multiplican tenemos que elegir. (Supongo que se puede mejorar en esta declaración.)

El ejemplo: Dado $a=3$$z=1$, $a^{-1}=a^{-1}\cdot z$ tiene el 10-ádico representación $7\cdot1+6\cdot10^1+\sum_{i=2}^\infty(3\cdot 10^i)$. La duración del período es $1$. Vemos a $3\cdot (7\cdot1+6\cdot10^1+\sum_{i=2}^\infty(3\cdot 10^i))=37$ es el menor número posible.

Dado $a=7$ $z=3$ nos encontramos con que $3\cdot z^{-1}$ periodo $6$. Este es ya el menor número posible.