Si ninguno de los números: $a,a+d,a+2d,...,a+(n-1)d$ son divisibles por $n$ demuestre que $n,d$ son coprimos.

Question

Si ninguno de los números: $a,a+d,a+2d,...,a+(n-1)d$ son divisibles por $n$ demuestre que $n,d$ son coprimos.

Como ninguno de los números dados es divisible por $n$ entonces sus residuos mod $n$ son $1,2,...,n-1$ Basándome en el principio de encasillamiento deduzco que hay dos números entre ellos tales que:
$$a+(i-1)d\equiv a+(j-1)d\pmod n,(0<i,j<n)\Rightarrow$$ $$(i-j)d\equiv 0\pmod n$$
Lo que significa $n|d$ porque $i-j<n$ ¿Qué hay de malo en mi solución que contradice el problema?

Answer 1

El enunciado del problema es incorrecto. La conclusión debería ser que $n$ y $d$ son no coprimo.

Sin embargo, tu argumento no es del todo correcto. Usted sabe que $(i-j)d$ es divisible por $n$ pero esto no significa que $n$ divide $d$ desde $n$ puede no ser primo.

Answer 2

Un rápido contraejemplo $1, 1+1\cdot2, 1+2\cdot2, 1+3\cdot2=1+(4-1)\cdot2$ no divisible por $4$ pero $\gcd(4,2)=2$ .

Llegar a la conclusión de que $(i-j)d\equiv 0\pmod n$ (que es $(i-j)d=n\cdot Q_1$ ) es buena, pero no suficiente, como ya se ha señalado. Supongamos que que $\gcd(d,n)=1$ Esto significa que $d$ y $n$ no tiene factores comunes. Así que cada $p$ -factor primo de $n$ dividirá $i-j$ ( de lo contrario $\gcd(d,n)\geq p >1$ ), concluyendo que $n \mid (i-j) < n$ lo que es una contradicción para $\gcd(d,n)=1$ . Así que $\gcd(d,n)\ne1$ .