Teoría de Números Ecuaciones Diofantinas Lineales

Question

Dejemos que $n$ sea un número entero positivo. Demostrar que existe un número entero positivo $m > 1000$ con las dos propiedades siguientes: $m$ son 007, y $m$ es relativamente primo de $n$ .

¿Puede alguien darme una solución?

Hasta ahora tengo esto: Sabemos que tener los tres últimos dígitos de $m$ sea $007$ significa $m \equiv 7 \mod 1000.$ Cuando $n$ no tiene factores de $2$ o $5,$ podemos hacer congruencias $m \equiv 1\mod p$ donde $p$ es un primo que divide a $n$ . El conjunto de congruencias con $m \equiv 7 \mod1000$ dar una solución $(m,n)$ .

No sé cómo demostrarlo cuando n es un múltiplo de 2 o 5. He buscado esta pregunta, las dos soluciones dadas utilizaban el teorema de dirichlet, que no puedo utilizar, y la otra no explicaba lo que quiero saber. Gracias de antemano.

Answer 1

Si $n$ es coprima de $10$ es decir, termina con $1,3,7,9$

Si $n$ es coprima de $10$ , entonces de hecho hay un múltiplo de $n$ que termina en $006$ . Esto se debe a que $n$ es coprima de $1000$ por lo que los restos que $1000k + 6$ se van cuando se dividen por $n$ , para $0 \leq k \leq n-1$ son todos diferentes. (Si no, entonces $1000(k-l)$ es un múltiplo de $n$ para algunos $0 < |k-l| < n$ así que $n$ debe ser un múltiplo de $1000$ , una contradicción).

Por lo tanto, para algunos $k$ , $1000k + 6$ es un múltiplo de $n$ . Por supuesto, $1000k + 7$ será coprima de $1000k+6$ y por lo tanto a $n$ .

Para múltiplos de $2$ y $5$

Para los números que son posiblemente múltiplos de $2$ y $5$ No hay que pensar mucho.

De hecho, hay que tener en cuenta que un número de la forma $..007$ ya es coprima de $2$ y $5$ . Por lo tanto, podemos tratar con un nuevo número formado por la eliminación de todas las instancias de $2$ y $5$ a partir de la factorización en primo del número dado.

De hecho, si $n$ es el número dado, crea $l$ eliminando $2$ y $5$ a partir de la factorización primaria de $n$ .

Ahora, podemos encontrar un $..007$ que es coprima de $l$ . También es coprima de $\frac nl$ porque $\frac nl$ sólo tiene $2,5$ como sus factores primos, ninguno de los cuales divide a $..007$ .

Lema

Si $n$ es coprima de $a$ y coprima a $b$ entonces $n$ es coprima de $ab$ .

Para ver por qué, $xn+ya = 1$ y $wn + zb = 1$ , por lo que multiplicando , $n(xwn + xzb+yaw) + (yz)ab = 1$ por lo que alguna combinación lineal de $n$ y $ab$ es $1$ por lo que su gcd es $1$ .

Uso del lema

Utilizando el lema, se ve que $..007$ es coprima del producto de $l$ y $\frac nl$ que es $n$ ¡!

Por lo tanto, este $..007$ es el deseado.

Ejemplos

• Dejemos que $n = 23$ . Entonces $n$ es coprima de $10$ . Encuentra un múltiplo de $23$ que termina con $006$ . Por lo que sabemos, uno de $6,1006,...,22006$ es un múltiplo de $23$ . Comprobamos que $12006$ es un múltiplo de $23$ . Por lo tanto, $12007$ es coprima de $23$ .

  • Dejemos que $n = 850$ . Entonces, $n = 17 * 50$ Así que nuestro $l$ es $17$ y $\frac nl$ es $50$ . Ejecutamos nuestro algoritmo con $17$ La respuesta es: sabemos que uno de los $6,1006,2006,...,16006$ es un múltiplo de $17$ . Puede comprobar que $2006$ es un múltiplo de $17$ . Por lo tanto, $2007$ es coprima de $17$ y, por tanto, a $850$ .

Answer 2

Sugerencia: Si $m \equiv 1 \pmod{n}$ ¿se puede decir algo sobre el gcd de $m$ y $n$ ?

Pista 2:

Teorema chino del resto