Sol PC5

Universidad Nacional de Ingenierı́a
Facultad de Ciencias
Escuela Profesional de Matemática Ciclo 2019−I
SOLUCIONARIO PRÁCTICA CALIFICADA 5 DE

INTRODUCCIÓN A LA MATEMÁTICA DISCRETA
1. Pruebe que, si m, n ∈ N son primos relativos entonces:
φ(mn) = φ(m)φ(n),
donde φ(m) y φ(n) son la función de Euler de m y n respectivamente.

Resolución:
La prueba se desprende de la siguiente afirmación:
Sean S = {s1 , ..., sφ(m) } un sistema completo de residuos módulo m ∈ N y R =
{r1 , ..., rφ(n) } un sistema completo de residuos módulo n ∈ N. Entonces un sistema
completo de residuos módulo mn se obtiene de todas las soluciones del siguiente par de
congruencias:
x ≡ ri (mod n), x ≡ sj (mod m),
con i, j ∈ N.
Si x esta en el sistema completo de residuos módulo mn entonces (x, m) = (x, n) = 1,
ası́ existe i, j ∈ N tal que x ≡ ri (mod n) y x ≡ sj (mod m). Recı́procamente si existen
i, j ∈ N tal que x ≡ ri (mod n) y x ≡ sj (mod m), entonces (x, mn) = 1. Por el teorema
chino del resto, existe una única solución x ∈ Z lo cuál prueba dicha afirmación.
Como cada par distinto (i, j) genera una solución distinta x y como hay φ(m)φ(n) pares
distintos entonces por la afirmación,
φ(mn) = φ(m)φ(n).
2. Pruebe que, si g es una raı́z primitiva módulo 2n entonces n = 1 o n = 2.

Resolución:
La prueba se deriva de la siguiente afirmación:
Si n ∈ N>2 y m es un entero impar entonces
n−2
m2 ≡ 1 (mod 2n ).
Para la prueba, procedamos por inducción. Si n = 3 entonce m2 ≡ 1 (mod 8). Por

hipotesis inductiva se tiene
n−2
m2 ≡ 1 (mod 2n ),
es decir existe z ∈ Z tal que
n−2
m2 = 1 + z2n .
Al elevar al cuadrado
n−1
m2 = 1 + z2n+1 + z 2 22n ,
entonces
n−1
m2 ≡ 1 (mod 2n+1 ),
lo cual prueba dicha afirmación. Por tanto si n > 2 se tiene que
n )/2
mφ(2 ≡ 1 (mod (2n )),
ası́ m no puede ser una raı́z primitiva módulo 2n ya que ord2n (m) 6= φ(2n ).
Por lo tanto las únicas potencias de 2 que tienen raı́ces primitivas son 2, con raı́z primitiva
1 y 4 con raı́z primitiva 3.
3. Show that if a is an integer satisfying mcd(a, 2520) = 1, then:
a12 ≡ 1(mod 2520).
State any theorems you are applying.

Resolución:
Factoring 2520 we get 2520 = 23 · 32 · 5 · 7. Then, sinde 23 , 32 , 5, 7 are pairwise relatively
prime we have, b the Chinese Remainder Theorem, that a12 ≡ 1(mod 2520) if and only
if:
a12 ≡ 1 (mod 23 )
a12 ≡ 1 (mod 32 )
a12 ≡ 1 (mod 5)
a12 ≡ 1 (mod 7)
This will be explained precisely bellow.
We consider each congruence separately:
(a) mod 23 :
As mcd(a, 2520) = 1 ⇒ mcd(a, 23 ) = 1, φ(8) = 4 where φ is the Euler function. By
Euler’s Theorem:
a4 ≡ 1 (mod 23 ).
Cubing both sides gives:
a12 ≡ 1(mod 23 ).
(b) mod 32 As mcd(a, 2520) = 1 ⇒ mcd(a, 32 ) = 1, φ(9) = 6 where φ is the Euler
function. By Euler’s Theorem:
a6 ≡ 1 (mod 32 ).
Squaring both sides gives:

a12 ≡ 1(mod 32 ).
(c) mod 5 As mcd(a, 2520) = 1 ⇒ mcd(a, 5) = 1. By Fermat’s Litle Theorem:
a4 ≡ 1 (mod 5).
Cubing both sides gives:

a12 ≡ 1(mod 5).
(d) mod 7 As mcd(a, 2520) = 1 ⇒ mcd(a, 7) = 1. By Fermat’s Litle Theorem:
a6 ≡ 1 (mod 7).
Squaring both sides gives:

a12 ≡ 1(mod 7).
2
The above shows that the integer a12 satisfies the system congruences:
x ≡ 1 (mod 23 )
x ≡ 1 (mod 32 )
x ≡ 1 (mod 5)
x ≡ 1 (mod 7)
and the integer 1 also obviously satisfies this system of congruences. Since the moduli are
relatively prime, by the Chinese Remainder Theorem there is a unique solution modulo
the product, i.e. mod (2520). Since a12 and 1 are both solutions we must have:
a12 ≡ (mod 2520).
4. Determine si las siguientes congruencias tienen soluciones enteras.
(a) x2 ≡ 101(mod 61).

(b) x2 + 90 ≡ 0(mod 19).
Resolución:
Es suficiente calcular el sı́mbolo de Legendre para cada caso:
3
101 40 2 5 3 61 60 4 1
(a) = = = (−1) (−1) 2 2 = − − = −1, es
61 61 61 61 5 5
decir, la congruencia no tiene solución entera.
(b) La congruencia dada es equivalente a x2 ≡ −90mod 19, ası́, calculamos:
2
−90 −1 2 3 5 19 18 4 4
= = (−1)(−1)(1) (−1) 2 2 = = 1,
19 19 19 19 19 5 5
lo cual quiere decir que la congruencia sı́ tiene solución entera.
El profesor1
Lima, 17 de Junio del 2019.
Duración: 1h:50min
1
Hecho en LATEX

Sol PC5

Cargado por

Copyright:

Formatos disponibles

Sol PC5

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Sol PC5

Cargado por

Copyright:

Formatos disponibles

Universidad Nacional de Ingenierı́a

SOLUCIONARIO PRÁCTICA CALIFICADA 5 DE

1. Pruebe que, si m, n ∈ N son primos relativos entonces:

donde φ(m) y φ(n) son la función de Euler de m y n respectivamente.

2. Pruebe que, si g es una raı́z primitiva módulo 2n entonces n = 1 o n = 2.

Para la prueba, procedamos por inducción. Si n = 3 entonce m2 ≡ 1 (mod 8). Por

3. Show that if a is an integer satisfying mcd(a, 2520) = 1, then:

a12 ≡ 1(mod 2520).

State any theorems you are applying.

Squaring both sides gives:

Cubing both sides gives:

Squaring both sides gives:

a12 ≡ (mod 2520).

4. Determine si las siguientes congruencias tienen soluciones enteras.

(a) x2 ≡ 101(mod 61).

lo cual quiere decir que la congruencia sı́ tiene solución entera.

También podría gustarte