Tareas

Aquí está la lista de ejercicios propuestos para las tareas y ayudantías. Recuerda que cada 15 días habrá un mimi-examen para evaluar cada tarea. Por favor, escribe la solución a cada ejercicio en una nueva página creando el hyperlink correspondiente en esta lista.

Por favor: NO crees una palabra nueva para crear la liga a la solución del problema. De preferencia copia el enunciado del problema en la página de la solución para que así todos podamos tener todas las hipótesis presentes

Exámenes

# Primer Examen: Jueves 11 Jueves 18 de Septiembre.

Inducción

  1. Usando el principio del buen orden demuestra que no hay enteros en el intervalo $(0,1) \subset \mathbb{R}$1.
  2. Usa el principio del buen orden ara demostrar que cualquier número racional $r\in \mathbb{Q}$ puede ser escrito como $r=\frac ab$ con $a,b\in \mathbb{Z}$ sin factores comunes.
  3. En cada uno de los siguientes ejercicios establece claramente cuál es la familia de proposiciones $S(n)$, indica cuál es la base de inducción. Demuestra entonces el ejercicio usando inducción.
    1. Demuestra que $1+q+\ldots+ q^n = \frac{1-q^{n+1}}{1-q}$.Digamos
    2. Para $n\ge 0$ se cumple que $n^2\le 4^n$.
    3. $1+3+\cdots+ 2n-1 = n^2$ para $n\ge 1$.Indu
    4. Prueba que $2^n < n!$ para $n \ge 4$.Inducc
    5. Demuestra que $n! \ge 2^{n-1}$ para todo entero positivo $n$.
    6. Demuestra que $1^3+ \ldots + n^3 = (1+2+\cdots+ n)^2$. Ind 3.6
    7. Demuestra que $2^n > n^2$ para $n\ge 0$. asjhgsgsgdfh
    8. Denotemos por $C_n$ al número de maneras que se tienen para cubrir los cuadrados de un tablero de ajedrez de $2 \times n$ con fichas de dominó. Entonces $C_1 =1, C_2 =2, C_3= 3$. Calcula $C_4$ y adivina una expresión para calcular $C_n$. Demuestra tu fórmula por inducción.
    9. Si $x \text{ y } y$ son enteros, demuestra que $x^{2n-1}+ y^{2n-1}$ tiene a $x+y$ como factor.
    10. El juego de la Torre de Hanoi fue publicado por el matemático francés Edouard Lucas en 1883. Este consiste de tres barras verticales y $n$ discos agujerados de tamaños diferentes (dos a dos) que son colocados en orden decreciente uno sobre el otro en una de las barras. El objetivo del juego es transferir toda la pila de discos a otra barra moviendo los discos uno por uno (uno por vez) sobre las barras con la única condición de no colocar un disco de tamaño mayor sobe un disco de tamaño menor. Muestra que es posible resolver este juego en $2^n-1$ movimientos.
    11. Usa el principio de inducción fuerte para demostrar que todo número entero mayor que uno contiene un factor primo.
    12. Prueba (por inducción) la fórmula de Leibiniz del cálculo diferencial: $D^n(fg) = \sum_{r=0}^n\binom nr D^{n-r}f\, D^rg$.
    13. Demuestra que todo conjunto finito con $n$ elementos tiene $2^n$ subconjuntos.
    14. Prueba que la suma de los primeros $n$ términos de una progresión aritmética: $a + (a+d) + (a+2d) + \cdots + [a+(n-1)d]$ es $\frac n2 [2a+(n-1)d]$.
  4. Determina si cada una de las siguientes afirmaciones son verdaderas o falsas para todo natural. Si lo son da una prueba por inducción, si no muestra un contraejemplo.
      1. $n! > 2n$Ind 4.1
      2. $7| 5^n+n+1$ Contrae
      3. $3| 2^{2n}-1$ Dem
      4. $(a+b)|(a^{2n}-b^{2n})$ Ind.4.4

Divisibilidad

  1. Prueba que si $a,b \in \mathbb{Z}$, con $b>0$, entonces existen enteros únicos $q,r$ tales que $a=qb+r$ con $2b \le r < 3b$.
  2. Verifica que si un entero es simultaneamente un cuadrado y un cubo, entonces este tiene que ser ya sea multiplo de 7 o dejar residuo 1 al dividirlo entre siete.
  3. 11, 111, 1111, 11111, … que sean cuadrados perfectos (Ayuda: Demuestra que estos números son de la forma 4k+3).
  4. Si $a|b$, muestra que $(-a)|b,\ a|(-b)$ y $(-a)|(-b)$.
  5. Verifica que:
    1. Si $a|b \rightarrow a|bc$
    2. Si $a|b \land a|c \rightarrow a^2|bc$
    3. $a|b$ si y sólo si $ac|bc$ con $c\ne 0$.
  6. Prueba o da un contraejemplo: Si $a|(b+c)\rightarrow a|b \lor a|c$.contra ejemplo
  7. Pureba que para cualquier entero $a$, alguno de los enteros $a, a+2, a+4$ es divisible por $3$. Respuesta
  8. Para un entero arbitrario $a$ demuestra que 2 siempre divide al producto de dos enteros consecutivos y que 3 siempre divide al producto de tres enteros consecutivos.
  9. Pureba que $4\nmid (a^2+2)$ para cualquier entero $a$.
  10. Demuestra por inducción que:
    1. $7| (2^{3n}-1)$ y que $8| (3^{2n}+7)$.
    2. $3| (2^n +(-1)^{n+1})$ div 10.2
  11. Muestra que si $a$ es un entero tal que $2\nmid a \land 3\nmid a \rightarrow 24| (a^2 -1)$.
  12. Prueba que:
    1. La suma de los cuadrados de dos enteros impares no puede ser un cuadrado perfecto.
    2. El producto de cuatro enteros consecutivos es una unidad menor que un cuadrado perfecto. Demostración
  13. Prueba que la diferencia de dos cubos consecutivos nunca puede ser un número par.

MCD

  1. Para un entero $a\ne 0$ muestra que $(a,0)=(a,a)=| a |$.MCD.1
  2. Para cualesquiera enteros, no ambos igual a cero, verifica que $(a,b)=(-a,b)=(a,-b)=(-a,-b)$.
  3. Prueba que para cualquier entero $a$ y para cualquier entero positivo $n$ se tiene que $(a, a+n) | n$.
  4. Prueba que si exiten enteros $x,y$ para los que $(a,b)=ax+by$ entonces $(x,y)=1$. Demostración1
  5. Prueba que:
    1. Si $(a,b)=1 \land (a,c)=1 \rightarrow (a,bc)=1$ esv
    2. Si $(a,b)=1 \rightarrow (ac,b)=(c,b)$. prueba(mcd5.2)
    3. Si $(a,b)=1 \land c\mid a \Rightarrow (b,c)=1$
    4. Si $(a,b)=1 \land c\mid a+b \Rightarrow (a,c)=(b,c)=1$

El algoritmo de Euclides

  1. Encuentra
    1. (143,227)
    2. (306, 657)
    3. (272,1479)
  2. Usa el algoritmo de Euclides para encontrar los enteros $x,y$ tales que:
    1. $(56,72)=56x+72y$; Euclides 2.1
    2. $(1729,2378)=1769x + 2378y$;Euclides 2.2
    3. $(119, 272) = 119x + 272y$;Euclides 2.3
  3. Asumamos que $(a,b)=1$ prueba que:
    1. $(a+b,a-b)=1 \text{ ó } 2$Euclides 3.1
    2. $(2a+b,a+2b) = 1 \text{ ó } 3$ Euclides 3.2
    3. $(a+b, a^2+b^2) = 1 \text{ ó } 2$ Euclides 3.3
    4. $(a+b, a^2-ab +b^2) = 1 \text{ ó } 3$. 4Euclides 3.4
  4. Para enteros positivos $a,b$ y $n\ge 1$ muestra que:
    1. Si $(a,b)=1$ entonces $(a^n,b^n)=1$
    2. Si $a^n\mid b^n$ implica que $a\mid b$Euclides4.2
  5. Encuentra:
    1. [143,227];Euclides 5.1
    2. [306,657];Euclides 5.2
    3. [227,1479].Euclides 5.3
  6. Sean $a,b,c$ enteros tal que no dos de ellos son cero, y sea $d=(a,b,c)$. Muestra que $d=((a,b),c) = (a, (b,c)) = ((a,c),b)$.
  7. Encuentra enteros $x,y,z$ tales que $(198,288,512)=198x + 288y + 512z$.

Ecuaciones Diofantinas

  1. Determina todas las soluciones en enteros de las siguientes ecuaciones Diofantinas:
    1. $56x +72y = 40$;Diofantina 1.1
    2. $24x+138y=18$;Diofantina 1.2
    3. $84x - 438y = 156$;
    4. $30x + 17y =300$;Diofantina 1.4
    5. $123x + 360y = 99$.Diofantina 1.5
  2. Si $a,b$ son enteros primos relativos. Prueba que la ecuación Diofantina $ax-by=c$ tiene una infinidad de soluciones en enteros positivos.
  3. Demuestra que la ecuación Diofantina $ax+by+cz = d$ tiene soluciones enteras si y solamente si $(a,b,c)\mid d$.
  4. Encuentra todas las soluciones en enteros de $15x + 12y + 30 z = 24$.
  5. Un cierto número de seises y nueves son sumados para obtener la suma de 126. Si el número de seises y nueves son intercambiados, entonces la nueva suma es 114. ¿Cuántos seises y cuantos nueves se consideraron en la primera suma?
  6. Un granjero compra 100 cabezas de ganado por un costo total de $4000. Los precios por cabeza son como sigue: vacas $120/u, borregos $50/u, puercos $25/u. Si el granjero compró al menos un animal de cada tipo, ¿Cuántos compró de cada tipo?.

Números primos y compuestos

El teorema fundamental de la Aritmética

  1. Se conjetura que hay una infinidad de primos de la forma $n^2-2$. Encuentra 5 primos de esta forma.
  2. Da un ejemplo para mostrar que la siguiente conjetura no es verdadera. Conjetura: Todo entero positivo puede ser escrito de la forma $p+a^2$, donde $p$ es primo o uno, y $a\ge 0$.
  3. Pueba lo siguiente:
    1. Todo primo de la forma $3k+1$ es también de la forma $6m+1$.
    2. Todo entero de la forma $3n+2$ tiene un factor primo de la misma forma.
    3. Los único primo de la forma $n^3-1$ es $7$.
    4. El único primo $p$ parael que $3p+1$ es un cuadrado perfecto es $p=5$.
  4. Si $p\ge 5$ es un primo, muestra que $p^2+2$ es compuesto.Aritmetica 4
  5. Resuelve :
    1. Demuestra que si $p$ es primo y $p\mid a^n \Rightarrow p^n \mid a^n$.
    2. Si $(a,b)=p$ es primo, ¿cuáles son los valores posibles para $(a^2,b^2)$? ¿para $(a^2,b)$? ¿para $(a^3,b^2)$?
  6. Encuentra todos los números primos que dividen a $50!$.
  7. Si $p\ne 5$ es un primo impar, demuestra que $p^2-1$ o $p^2+1$ es divisible por $10$.
  8. Encuentra la factorización en primos de 1234, 10140, 36000.}
  9. Considera el conjunto $S$ de enteros de la forma $3k+1$. Decimos que un entero $a\in S$ es S-primo is no puede ser factorizado como producto de dos enteros en $S$.
    1. Prueba que cualquier elemento de $S$ es o S-primo o producto de S-primos.
    2. Da un ejemplo para mostrar que es posible para un elemento de $S$ tener varias factorizaciones distintas en S-primos.
  10. Muestra que un entero $n$ es un cuadrado, si y sólo si los exponentes que aparecen en su factorización en primos son todos números pares.
  11. Un entero es llamado libre de cuadrados si no es divisible por el cuadrado de cualquier número entero mayor que 1. Demuestra que:
    1. Un entero $n>1$ es libre de cuadrados si, y sólo si, $n$ puede ser factorizado como el producto de primos distintos.
    2. Todo número $n>1$ es el producto de un entero que es un cuadrado perfecto y otro que es libre de cuadrados.
  12. Probar que si $2^{n}+1$ es primo, entonces $n$ es una potencia de 2.

La criba de Eratostenes

  1. Determina si 701 es primo probando con todos los primos menores que $\sqrt{701}$ como posibles divisores. Haz lo mismo para 1009.
  2. Usa la criba de Eratostenes para obtener todos los primos que están entre 100 y 200.
  3. Demuestra que:
    1. $\sqrt p$ es irracional para cualquier primo $p$.Criba3.1.
    2. Si $n>0$ y $\sqrt[k]n$ es racional, entonces $\sqrt[k]n$ es entero.
  4. Muestra que cualquier número compuesto con tres dígitos debe tener un factor primo menor que 31.
  5. Modifica la prueba del teorema de Euclides sobre la infinitud de los números primos, considerando el número $N=p!+1$ para llegar a una contradicción.
  6. Prueba que para $n>2$, existe un primo que está entre $n$ y $n!$.
  7. Si $p_n$ es el $n$-ésimo primo, demuestra que ninguno de los números $p_1p_2\cdots p_n+1$ es un cuadrado perfecto.

Funciones aritméticas

  1. Problema 1
    1. Sean $n,m$ enteros positivos y sean $p_1,p_2, \ldots, p_r$ primos distintos que dividen a al menos uno de $m$ o $n$. Entonces $m$ y $n$ se pueden escribir en la forma: $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ con $a_i\ge 0$ y $n=p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r}$ con $b_i\ge 0$. Demuestra que $(m,n)=p_1^{u_1}p_2^{u_2}\cdots p_r^{u_r}$ con $u_i=\min(a_i,b_i)$; y $[m,n]= p_1^{v_1}p_2^{v_2}\cdots p_r^{v_r}$ con $v_i=\max(a_1,b_i)$.
    2. Usa lo anterior para caluclar $(12378,3054)$ y $[12378,3054 ]$.
    3. Deduce de los ejercicios anteriores que $(m,n)[m,n] = mn$.
    4. Prueba que $(m,n)=1$ si y sólo si $a_ib_i=0$ para todo $i=1\ldots r$.
  2. Prueba que para todo entero $n\ge 1$ se tiene que $\tau(n)\le 2\sqrt n$.
  3. Prueba que:
    1. $\tau(n)$ es impar si y sólo si $n$ es un cuadrado perfecto.
    2. $\sigma(n)$ es impar si y sólo si $n$ es un cuadrado perfecto o 2 por un cuadrado perfecto.
  4. Muestra que $\sum_{d\mid n} \frac 1d = \sigma(n)/n$ para cada entero positivo $n$.
  5. Si $n$ es libre de cuadrados, prueba que $\tau(n) = 2^r$, en donde $r$ es el número de primos distintos que dividen a $n$.
  6. Demuestra que:
    1. Si $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ es la factorización en primos para $n>1$ . Entonces $1> \frac{n}{\sigma(n)} > \left( 1-\frac{1}{p_1}\right) \left( 1-\frac{1}{p_2} \right) \cdots \left( 1-\frac{1}{p_r} \right)$.
    2. Para cualquier entero positivo $n, \ \sigma(n!)/n! > 1 + 1/2 + 1/3+ \cdots + 1/n$.
    3. Si $n>1$ es compuesto, entonces $\sigma(n)> n + \sqrt n$.
  7. Dado un entrero positivo $k>1$, muestra que hay una infinidad de enteros $n$ para los que $\tau(n)=k$, pero que hay a lo más un número finito de $n$ para los que $\sigma(n)=k$.
    1. Encuentra la forma de todos los enteros $n$ que satisfacen que $\tau(n)=10$. ¿Cuál es el más pequeño de todos ellos?
    2. Prueba que no hay enteros positivos para los que $\sigma(n)=10$.
  8. Para $k\ge 2$ muesta que:
    1. $n=2^{k-1}$ satisface la ecuación $\sigma(n)=2n-1$.
    2. Si $2^k-1$ es primo, entonces $n=2^{k-1}(2^k-1)$ satisface la ecuación $\sigma(n)=2n$.
    3. Si $2^k-3$ es primo, entonces $n=2^{k-1}(2^k-3)$ satisface la ecuación $2n+2$.
  9. Prueba que:
    1. La función $f(n)=n^k$ es multiplicativa para todo $k\ge 1$.
    2. Si $f,g$ son funciones multiplicativas, entonces también lo son $fg$ y $f/g$.
    3. Si $f,g$ son multiplicativas y $f(p^k)=g(p^k)$ para todo primo $p$ y $k\ge 1$ entonces $f=g$.
  10. Dado un entero $n\ge 0$, sea $\sigma_s(n) := \sum_{d\mid n} d^s$. Verifica que:
    1. $\sigma_0=\tau$ y $\sigma_1 = \sigma$;
    2. $\sigma_s$ es multiplicativa.
    3. Encuentra una fórmula para calcular $\sigma_s(n)$ en términos de la factorización en primos de $n$.
  11. Calcula $\phi(1001), \phi(5040)$
  12. Demuestra que:
    1. Si $n$ es impar, entonces $\phi(2n) = \phi(n)$
    2. Si $n$ e par, entonces $\phi(2n) = 2 \phi(n)$
    3. $\phi(2n)=3 \phi(n)$ si y sólo si $3\mid n$.
    4. $\phi(3n) = 2 \phi(n)$ si y sólo si $3\nmid n$.
    5. $\phi(n)=n/2$ si y sólo si $n=2^k$ para algún $k\ge 1$.
  13. Demuestra que si todo primo que divide a $n$ también divide a $m$, entonces $\phi(mn)=n \phi(m)$; en paricular $\phi(n^2)=n \phi(n)$ para todo entero positivo $n$.

La fórmula de Inversión de Moebius

  1. Sea $n= p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ la factorización en primos del entero $n>1$. Si $f$ es una función multiplicativa, demuestra que: $\sum_{d\mid n} \mu(d)f(d)= (1-f(p_1))(1-f(p_2))\cdots (1-f(p_r))$.
  2. Usa el problema anterior para demostrar que:
    1. $\sum_{d\mid n} \mu(d)\tau(d) = (-1)^r$.
    2. $\sum_{d\mid n} \mu(d)\sigma(d)=(-1)^rp_1p_2\cdots p_r.$
    3. $\sum_{d\mid n} \mu(d)/d = (1-1/p_1)(1-1/p_2)\cdots (1-1/p_r)$.
    4. $\sum_{d\mid n} d \mu(d) = (1-p_1)(1-p_2)\cdots (1-p_r).$
  3. Sea $S(n)$ el número de divisores libres de cuadrados de $n$. Muestra que $S$ es multiplicativa y que $S(n)= \sum_{d\mid n} |\mu(d)| = 2^r$ donde $r$ es el número de primos distintos que dividen a $n$.

La funcíón mayor entero

  1. Dados enteros $a,b >0$, muestra que existe un entero único $r$ con $0\le r<b$ tal que $a=[a/b]b+r$.
  2. Sean $x,y$ números reales. Demuestra que la función mayor entero satisface las siguientes propiedades:
    1. $[x+n] =[x]+n$ para $n$ entero.
    2. $[x]+[-x] =0 \lor -1$ dependiendo de si $x$ es entero o no.
    3. $[x]+[y]\le [x]+[y]$ y cuando $x,y$ son positivos se tiene que $[x][y] \le [xy]$.
    4. $[x/n] = [[x]/n]$ para cualquier entero positivo $n$.
    5. $[nm/k] \ge n[m/k]$ para enteros positivos $n,m,k$.
  3. Encuentra la potencia mayor de $5$ que divide a $1000!$ y la mayor potencia de 7 que divide a $2000!$.
  4. Encuentra $v_p(m)$ para:
    1. $m= (2)(4)\cdots (2n)$ el producto de los primeros $n$ enteros pares.
    2. $m$ el producto de los primeros $n$ enteros impares.
  5. Muestra que $1000!$ termina con 249 ceros.
  6. Si escribimos al entero positivo $n$ en base $p$, esto es, si $n= a_kp^k + \ldots + a_1p + a_0$ con $0\le a_i <p$. Muesta que el exponente de la mayor potencia de $p$ que aparece en la factorización en primos de $n!$ es $\frac{n-(a_k+\cdots + a_1+ a_0)}{p-1}$.
  7. Usa el problema anterior para calcular la potencia mayor de $p$ que divide a $(p^k-1)!$. Determina la mayor potencia de 3 que divide a 80! y la mayor potencia de 7 que divide a 24000! (nota que 24000=7^4-1).
  8. Encuentra un entero $n\ge 1$ tal que la mayor potencia de 5 contenida en $n!$ es 100.
  9. Dado un entero positivo $N$, muestra que:
    1. $\sum_{n=1}^N \mu(n)[N/n] =1$;
    2. $\left| \sum_{n=1}^N \mu(n)/n \right|\le 1$
    3. Ilustra lo anterior tomando $N=6$.

Congruencias

Fermat, Euler Wilson:

La tarea se encuentra en la siguiente liga:

  1. Tarea Fermat Euler Wilson

Si alguien tiene problemas con entender el inglés que ponga su pregunta en el foro y con gusto le traducimos.

Congruencias Lineales y Teorema Chino del Residuo

  1. La tarea está en esta liga: Tarea: Teorema Chino y congruencias

Raíces Primitivas

  1. La tarea se encuentra en esta página: Tarea raíces primitivas

Reciprocidad Cuadrática

  1. tarea Orden de un elemento
  2. aquí El símbolo de Legandre
Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License