Encontrar productos naturales consecutivos que todos no tienen inversos modulo $70$

Question

No estoy seguro de cómo probar la siguiente declaración verdadero o falso.

Existen cinco productos naturales consecutivos que todos no tienen inversos modulo $70$.

Sé que puedo aplicar el Algoritmo euclidiano para encontrar el inverso modulo $70$ de algunos, pero no estoy seguro de cómo aplicar el algoritmo a este problema.

Answer 1

Cualquier número que se coprime a un módulo tendrá una relación inversa, por lo que necesitamos encontrar $5$ números consecutivos que comparten un factor de con $70$.

$70$ tiene tres primos factores: $2,5,7$. De cualquier $5$ números consecutivos, dos o tres serán aún, pero en la mayoría de los que uno será divisible por $5$ o $7$. Así que tenemos tres números con una extraña múltiples de $5$ y una extraña múltiples de $7$ en la segunda y cuarta posición. Desde impares múltiplos de $5$ todos los $\equiv 5\bmod 10$, es evidente que esto significa que tenemos que mirar para los casos en que $7k \equiv \{3,7\} \bmod 10$. Hay dos de estos casos a continuación $70$: $k=1$ y $k=9$ (lo $7$$63$), con las dos opciones de $5$ números consecutivos:

$$\{4,5,6,7,8\} \text{ and } \{62,63,64,65,66\}$$

Para aquellos cómodo con valores negativos en la aritmética modular, la segunda, a la negación de la primera, que es, $\{62,63,64,65,66\} \equiv \{-8,-7,-6,-5,-4\} \bmod {70}$ .

Answer 2

Nota que $x \in \mathbb{N}$ tiene una inversa modulo $n$ si y sólo si $\text{gcd}(x,n) = 1$. Buscando la primera descomposición de $70$, vemos $$70 = 2 \cdot 5 \cdot 7.$ $ ahora claramente $4, 5, 6, 7, 8$ no tiene máximo común divisor $1$ $70$ y por lo tanto no inverso modulo $70$.

Answer 3

El % de números $[4,5,6,7,8]$satisfacen la propiedad requerida.