Encontrar el menor entero $n > 0$ tal divide a que $2012$ $9^n-1$.

Question

Encontrar el menor entero $n > 0$ tal divide a que $2012$ $9^n-1$.

---

mis pensamientos:

$$2012=2 \cdot 2 \cdot 503$$ $503$ es primo. así que por fermats poco teorema $9^{502} \equiv 1$(mod $503$). otra vez $9^n \equiv 1$ (mod $4$).
¿por lo tanto, $n=502$ igualdad sostiene pero es el más pequeño?

Answer 1

$9^{502} \equiv1\mod503 \Longrightarrow$

$ 9^{502}-1\equiv0\mod503 \Longrightarrow $

$(9^{251}-1)(9^{251}+1)\equiv0\mod503 \Longrightarrow$

Por el teorema de fermat, $3^{502} \equiv1\mod503$

GCD $((9^{251}-1),(9^{251}+1))=2 \Longrightarrow$

$503\not\mid (9^{251}+1)$

Por lo tanto, $9^{251}-1\equiv0\mod503$.

Menor $n=251$. $9^1 \neq 1 \mod 503$.

Answer 2

$503$ es un Sophie Germain prime, es decir, $\rm\: q = 503 = 2p\!+\!1 \:$ primer $\rm\:p = 251,\:$, por lo que el orden de cálculo de mod $\rm\,q\,$ es fácil. Lo demostramos en general (más perspicaz y tan fácil). El suyo es $\rm\: m=4,\ a= 9.$

Teorema $\ $ Si $\rm\,\ p,\, q=2p\!+1\:$ son los números primos y los $\rm\ m\mid a\!-\!1,\,\ q\nmid a,a^2\!-\!1\:$

$$\rm ord_{qm}(a)\ =\ p\ \ \ if\ \ a\ \ is\ a\ square\ mod\ q,\ \ else\ \ 2p$$

Prueba de $\ $ en Primer lugar, tenga en cuenta que $\rm\:(q,m)=1\:$ ($\rm\ q\mid m\mid a\!-\!1\mid a^2\!-\!1)\,\:$ contra la hipótesis). Por lo tanto

$$\rm\:qm\mid a^n\!-\!1\iff q,m\mid a^n\!-\!1\iff q\mid a^n\!-\!1,\ \ \ since\ \ \ m\mid a\!-\!1\mid a^n\!-\!1.\:$$

Así $\rm\: ord_{qm}(a) = ord_q(a) =: n.\,$ $\rm\,mod\ q\!:\ 1 \equiv a^{q-1}\! \equiv a^{2p},\:$ por lo $\rm\:n\mid 2p.\:$ Por la hipótesis de $\rm\:q\nmid a^2\!-\!1,\:$ $\rm\:n\nmid 2.\:$ Si $\rm\:n = p\:$ $\rm\:1 \equiv a^p \equiv a^{(p-1)/2},\:$ verdadero iff $\rm\:a\:$ es un cuadrado de $\rm\:mod\ q,\:$ por Criterio de Euler.

Answer 3

Utilizando el pequeño Teorema de Fermat, $3^{502}\equiv1\pmod {503}$ $\implies (3^2)^{251}\equiv1\pmod {503}$ $\implies 9^{251}\equiv1\pmod {503}$

Como sabemos, si $a^n\equiv 1\pmod n$ y $ord_na=d, d\mid n$ donde entero $n>0$ (prueba)

Si $ord_{503}9=d\implies d\mid 251$

Como $251$ prime, % o $d=1$ $251$

$9^1\not\equiv1\pmod {503} ,d=251$