Transcript
Univ. Nal. de Colombia, Medell´ın – Esc. de Matem´aticas – Conj. y Combinatoria – 2011-I
Parcial 2 – Soluciones Mayo 11, 2011
1. Justifique que las congruencias x ≡ a (mod m)
x ≡ b (mod n)
y
(∗)
admiten una soluci´ on simult´anea si y s´olo si mcd(m, n) | a − b. Si una soluci´on existe, pruebe que es u ´nica m´odulo mcm(m, n) (el m´ınimo com´ un m´ ultiplo de m y n). Sugerencia: Puede usar resultados acerca de ecuaciones diofantinas lineales y mcm(m, n) = mn/mcd(m, n). Soluci´ on. Sea d = mcd(m, n). Existencia: (⇒) Supongamos que las congruencias (∗) tienen una soluci´ on simult´anea x. Entonces existen enteros s y t tal que x = a + sm
y
x = b + tn.
Por lo tanto a + sm = b + tn y −sm + tn = a − b. Puesto que d | m y d | n se obtiene que d | a − b. (⇐) Supongamos que d | a−b. Entonces existe un entero q tal que a−b = qd. Por la identidad de Bezout, existen enteros s, t tal que d = sm + tn. De lo anterior, obtenemos que a − b = q(sm + tn) y entonces a − qsm = b + qtn. Pero entonces x = a − qsm = b + qtn satisface las congruencias (∗). Unicidad: Supongamos que x y x 0 satisfacen las congruencias (∗). Entonces x ≡ x 0 (mod m)
y
x ≡ x 0 (mod n),
y m | x − x 0 y n | x − x 0 . Es decir, x − x 0 es com´ un m´ ultiplo de m y n y por lo tanto, por propiedad del m´ınimo com´ un m´ ultiplo, mcm(m, n) | x − x 0 y entonces x ≡ x 0 (mod mcm(m, n)). 1
2. Justifique que si mcd(a, n) = 1, la congruencia lineal ax ≡ b (mod n) tiene soluci´ on x ≡ baφ(n)−1 (mod n). (∗) Use esto para resolver la congruencia 3x ≡ 5 (mod 26). Soluci´ on. Por el teorema de Euler sabemos que para todo entero a aφ(n) ≡ 1 (mod n). (∗∗) Sea x que satisface (∗). Entonces, usando (∗∗) se obtiene que ax ≡ a · (baφ(n)−1 ) ≡ b · aφ(n) ≡ b (mod n). Esto es, x en (∗) satisface la congruencia lineal dada. Ahora resolvemos la congruencia dada. Primero φ(26) = 26(1 − 1/2)(1 − 1/13) = 12. Entonces necesitamos determinar 311 (mod 26). Pero 33 = 27 ≡ 1 (mod 26), por lo tanto 311 = (33 )3 · 32 ≡ 9 (mod 26) Por lo tanto, la soluci´ on es x ≡ 5 · 311 ≡ 5 · 9 ≡ 45 ≡ 19 (mod 26). 3. Justifique que para p primo y m entero positivo, φ(pm ) = pm−1 φ(p) Soluci´ on. Para p primo, los enteros 1, 2, 3, . . . , p − 1 son coprimos con p; por lo tanto φ(p) = p − 1. M´ as general, para m ≥ 1 entero, un entero k con 1 ≤ k ≤ pe no es coprimo con pe si y s´ olo si k es m´ ultiplo de p. Estos m´ ultiplos son p, 2p, 3p, . . . , pm−1 p; es decir, hay pm−1 no coprimos y por lo tanto pm − pm−1 = pm−1 (p − 1) coprimos con pm . Por lo tanto φ(pm ) = pm−1 (p − 1) = pm−1 φ(p). 4. Sea p primo. Justifique que para todo entero a, p divide ap + a(p − 1)!
2
Soluci´ on. Por el teorema de Fermat, si p 6 | a se tiene ap−1 ≡ 1 (mod p). De aqu´ı que ap ≡ a (mod p), lo que es v´alido incluso cuando p | a. Por otra parte, por el teorema de Wilson, (p − 1)! ≡ −1 (mod p) y por lo tanto ap + a(p − 1)! ≡ a + a(−1) = 0 (mod p). Esto significa que p divide ap + a(p − 1)! 5. Justifique lo siguiente: Sea G un grupo con elemento unidad e. Si g ∈ G con ordG (g) < ∞, entonces gk = e si y s´ olo si ordG (g) | k. Soluci´ on. Sea d = ordG (g). (⇒) Usando el algoritmo de la divisi´on, se obtiene que k = qd + r donde 0 ≤ r < d. Entonces e = gk = gqd+r = gqd gr = (gd )q gr = eq gr = gr . De aqu´ı se deduce que r = 0 ´o de lo contrario se tendr´ıa una contradicci´on con el hecho de que d = ordG (g). Por lo tanto, k = qd; es decir, d | k. (⇐) Si d | k entonces k = qd y gk = (gd )q = eq = e. 6. Justifique que para cualquier entero n, n9 + 2n7 + 3n3 + 4n es divisible por 5. Sugerencia: Utilice el teorema de Fermat para obtener un polinomio en n que es divisible por 5. Soluci´ on. Si 5 | n entonces 5 divide el polinomio dado (ya que n se puede factorizar). Si 56 | n entonces, por el teorema de Fermat, se tiene que n4 ≡ 1 (mod 5) y, por lo tanto, aplicando esta equivalencia repetidamente: n9 + 2n7 + 3n3 + 4n = (n4 )2 n + 2(n4 ) n3 + 3n3 + 4n ≡ n + 2n3 + 3n3 + 4n (mod 5) = 5n + 5n3 ≡ 0 (mod 5). Por lo tanto 5 divide n9 + 2n7 + 3n3 + 4n. 7. Sea p un primo impar y r una ra´ız primitiva de p (es decir, ordp (r) = p − 1). Justifique que a) r(p−1)/2 ≡ −1 (mod p) Soluci´ on. Sea x = r(p−1)/2 . Entonces x2 = rp−1 ≡ 1 (mod p) porque ordp (r) = p − 1. De aqu´ı que, factorizando, (x − 1)(x + 1) ≡ 0 (mod p). 3
Puesto que p es primo, se deduce que x − 1 ≡ 0 (mod p) ´o x + 1 ≡ 0 (mod p). En el primer caso se tendr´ıa que x = r(p−1)/2 ≡ 1 (mod p), lo que contradice la minimalidad de ordp (r). Por lo tanto, r(p−1)/2 ≡ −1 (mod p). b) r0 , r1 , r2 , . . . , rp−2 son incongruentes (mod p) (y por lo tanto congruentes (mod p) con 1, 2, 3, . . . , p − 1 en alg´ un orden) Soluci´ on. Si dos de estas potencias, ri y rj con j > i satisfacen xj ≡ i x (mod p), entonces xj−i ≡ 1 (mod p). Pero 0 < j−i < ordp (r), lo que contradice la minimalidad de ordp (r). Por lo tanto, las potencias r0 , r1 , r2 , . . . , rp−2 son incongruentes y, puesto que hay p−1 de estas, ellas deben ser congruentes (mod p) con 1, 2, 3, . . . , p − 1 en alg´ un orden. c) Use (a,b) para probar que (p − 1)! ≡ −1 (mod p) (el teorema de Wilson) Sugerencia: Forme el producto 1 · 2 · 3 · · · · · (p − 1) usando (b) y entonces use (a) Soluci´ on. Utilizando (b), podemos escribir (p − 1)! como (p − 1)! = 1 · 2 · 3 · · · · · (p − 1) ≡ r0 · r1 · r2 · · · · · rp−2 (mod p) = r
0+1+2+···+(p−1)
= r
(p−2)(p−1)/2
= (r
(p−1)/2 p−2
≡ (−1) = −1
)
p−2
usando (b)
usando propiedad de potencias
usando f´ormula para la suma 1 + 2 + · · · + (p − 1) usando propiedad de potencias
(mod p)
usando (a)
porque p − 2 es impar.
4