Nacional OMA 2011 - Nivel 3 - Problema 5

[ésta]

Hallar todos los enteros [math]n tales que [math]1<n<10^6 y [math]n^3-1 es divisible por [math]10^6n-1.

[No, manzana]

Una version sin abecedario de mi solución:

Spoiler: mostrar

Primero, cómo [math]n^3 -1 \equiv 0 \pmod{10^6n-1} \Rightarrow n^3-1 \ge 10^6n -1 \Rightarrow n \ge 10^3.

Segundo, cómo [math]n^3 -1 \equiv 0 \pmod{10^6n-1} \Rightarrow n^3 \equiv 1 \pmod{10^6n-1} \Rightarrow 10^{18}n^3-1 \equiv 10^{18}-1 \pmod{10^6n-1}.

Tercero [math]a^3-b^3 \equiv 0 \pmod{a-b} para [math]a,b enteros distintos, entonces [math]10^{18}n^3-1 \equiv 0 \pmod{10^6n-1}.

Cuarto, de lo segundo y lo tercero se obtiene: [math]10^{18}-1 \equiv 0 \pmod {10^6n-1}, entonces [math]10^{18}-1 \ge 10^6n-1 \Rightarrow n \le 10^3.

De lo primero y lo cuarto, el único entero [math]n que cumple con lo pedido es [math]n=10^3.

[Vladislao]

Tenés un error que invalida todo:

Spoiler: mostrar

Si [math]10^{18}-1 \geq 10^6n-1 entonces [math]10^{12} \geq n.

[No, manzana]

Tenés un error que invalida todo:

Spoiler: mostrar

Si [math]10^{18}-1 \geq 10^6n-1 entonces [math]10^{12} \geq n.

Cierto, ya me parecía q no era tan fácil después de llegar a eso, y entonces no me lamento haberme comido alto viaje antes n.n .

[Vladislao]

Spoiler: mostrar

Es trivial ver que [math]10^3 \leq n.

Ahora:

[math]10^6n-1 \mid n^3-1 \Leftrightarrow 10^6n-1 \mid n^3-10^6n \Leftrightarrow 10^6n-1 \mid n(n^2-10^6)

Como [math]\mbox{mcd}(n,10^6n-1)=1, sigue que [math]10^6n-1 \mid n^2-10^6

Entonces, recordando que [math]10^3 \leq n, hay dos casos:

1) [math]10^6n-1 \leq n^2-10^6, tomando esto como una cuadrática nos dice que [math]n\geq 10^6, absurdo.

2) [math]n^2-10^6 = 0, lo que nos dice que [math]n=10^3 que es solución y además es la única.

[ésta]

Spoiler: mostrar

Es posible ahorrarse la cuadrática diciendo que:
[math]n^2 \geq 10^6n + (10^6-1) > 10^6n \Rightarrow n>10^6

[Johanna]

Spoiler: mostrar

Sabemos que [math]10^6n-1\mid n^3-1
Entonces [math](10^6n-1)x=n^3-1
Reacomodando los terminos:
[math]10^6nx-(x-1)= n^3
Como estamos en enteros entonces [math]n\mid x-1
[math]x>0, Si [math]x=1, resolvemos y nos queda [math]n=10^3

Si [math]x>1 notemos que [math]n\leq x-1 [math]\Rightarrow n+1\leq x
Entonces [math](10^6n-1)(n+1)\leq (10^6n-1)x=n^3-1
Desarrollando los terminos y reacomodando queda:
[math]0\leq n^2-10^6n-10^6+1= P(n)
Resolviendo la cuadratica queda que las raices del polinomio [math]P(n)=n^2-10^6n-10^6+1 son [math]n=\{1000001;-1\}
Es decir que [math]P(n) toma valores positivos para [math]n<-1 y [math]n> 10^6+1 pero como [math]1<n<10^6 entonces la desigualdad no tiene soluciones en este conjunto.
Por lo que la unica solucion es [math]n=10^3

[Gianni De Rico]

Spoiler: mostrar

Tenemos que:
[math]10^6n-1\mid n^3-1\Rightarrow 10^6n-1\Rightarrow 10^6n-1\mid n^3-1-(10^6n-1)\Rightarrow
[math]10^6n-1\mid n^3-10^6n\Rightarrow 10^6n-1\mid n(n^2-10^6)

Además:
[math]10^6n-1\equiv 0-1\equiv -1(n)\Rightarrow 10^6n-1 es coprimo con [math]n\Rightarrow 10^6n-1\mid n^2-10^6 (+)

Como [math]n<10^6:
[math]n^2<10^6n\Rightarrow n^2-10^6<10^6n-10^6<10^6n-1 (*)

Como [math]1<n:
[math]n^2-10^6>1-10^6>1-10^6n>-(10^6n-1) (**)

De (*) y (**) resulta:
[math]10^6n-1>n^2-10^6>-(10^6n-1)\Rightarrow |n^2-10^6|<|10^6n-1| (++)

De (+) y (++) sale que:
[math]n^2-10^6=0\Rightarrow n^2=10^6\Rightarrow n=10^3

Finalmente, el único entero que cumple las condiciones del enunciado es [math]n=10^3

[Joacoini]

Spoiler: mostrar

Si $n<10^3\Rightarrow n^2<10^6\Rightarrow n^3-1<10^6n-1$.
Por lo que $n\geq 10^3$.

Como $10^6n-1\mid n^3-1$ tenemos que

$10^6n-1\mid (10^{12}n^2+10^6n+1)(10^6n-1)-10^{18}(n^3-1)=10^{18}-1\Rightarrow (10^6n-1)k=10^{18}-1$

$(10^6n-1)k=10^6nk-k=10^{18}-1\Rightarrow 10^6nk=10^{18}+k-1\Rightarrow 10^6\mid k-1\Rightarrow k=10^6m+1$

Como $n\geq 10^3$ y $(10^6n-1)(10^6m+1)=10^{18}-1$, $10^6m+1=\frac{10^{18}-1}{10^6n-1}\leq \frac{10^{18}-1}{10^9-1}=10^9+1\Rightarrow m\leq 10^3$

$(10^6n-1)(10^6m+1)=10^{18}-1=10^{12}nm+10^6n-10^6m-1\Rightarrow 10^{18}=10^{12}nm+10^6n-10^6m\Rightarrow
10^{12}=10^{6}nm+n-m$

$10^6\mid n-m$ y como $10^3\leq n<10^6$ y $m\leq10^3$ esto solo se da si $n=m=10^3$.