Concluir que el orden multiplicativo módulo $ab$ de cualquier $c$ , $gcd(c,ab) = 1$ debe ser un divisor propio de $\phi(ab)$ .

Question

a) Demuestre que si $n = ab$ donde $1 < a, b$ son impar y $gcd(a,b) = 1$ entonces $lcm(\phi(a),\phi(b)) < \phi(ab)$ .

b) Concluya que el orden multiplicativo módulo $ab$ de cualquier $c$ , $gcd(c,ab) = 1$ debe ser un divisor propio de $\phi(ab)$ . Pista: Teorema del Resto de China Teorema.

c) Por último, concluye que el compuesto impar $n$ no tiene una raíz primitiva.

He tenido algunos problemas con este problema. He resuelto la parte a) pero tengo problemas con las partes b) y c). Cualquier ayuda sería útil.

Answer 1

Ya que has hecho a), resolvemos b), en un lugar utilizando el resultado de a).

Tenemos $c^{\varphi(a)}\equiv 1\pmod{a}$ y $c^{\varphi(b)}\equiv 1\pmod{b}$ por el Teorema de Euler.

De ello se deduce que si $k$ es un múltiplo de $\varphi(a)$ entonces $c^k\equiv 1\pmod{a}$ y un resultado similar es válido para $b$ .

En particular, si $k$ es el lcm de $\varphi(a)$ y $\varphi(b)$ entonces $c^k\equiv 1\pmod{a}$ y $\pmod{b}$ y por lo tanto $\pmod{ab}$ ya que $a$ y $b$ son relativamente primos.

Según la parte a), este lcm es menor que $\varphi(a)\varphi(b)$ es decir, menos de $\varphi(ab)$ .

Por último, demostramos que el orden de $c$ modulo $ab$ divide este lcm $k$ y, por tanto, divide $\varphi(ab)$ .

Dejemos que $e$ sea el orden de $c$ modulo $ab$ . Así que $e$ es el menor número entero positivo tal que $c^e\equiv 1\pmod{ab}$ .

Tenemos $$\varphi(ab)=qe+r,\tag{1}$$ para algunos enteros $q$ y $r$ tal que $0\le r\lt e$ . Demostraremos que $r=0$ . A partir de (1) tenemos $$c^{\varphi(ab)}=(c^e)^q c^r.$$

Pero $c^{\varphi(ab)}\equiv 1\pmod{ab}$ y $(c^e)^q\equiv 1\pmod{ab}$ . De ello se desprende que $c^r\equiv 1\pmod{ab}$ . Si $r\ne 0$ Esto contradice la minimidad de $e$ . Así, $r=0$ . Esto completa la prueba de divisibilidad.

Tenemos que modificar ligeramente c), para afirmar que si $n$ es el producto de dos números Impares relativamente primos, entonces $ab$ no tiene una raíz primitiva. Esto demostrará que el impar compuesto $n$ que no son potencias primarias no tienen una raíz primitiva.

Porque hemos demostrado que cualquier $c$ relativamente primo a $ab$ tiene orden menos de $\varphi(ab)$ . Una raíz primitiva de $n$ tiene exactamente el orden igual a $\varphi(n)$ .