Definiciones 1 Flashcards
Dados n,m ∈ Z decimos que m divide a n si… (y propiedades)
Dados n,m ∈ Z decimos que m divide a n si existe q ∈ Z tal que n = qm. En este caso escribimos m | n, y en caso contrario escribiremos m ł n
Propiedades 1.1.5.
1. Tenemos que m divide a n si y sólo si, el resto de dividir n entre m es cero.
2. ±1 | a, ∀a ∈ Z. Además si un entero x cumple que x | a, ∀a ∈ Z, entonces x = ±1.
3. b | 0, ∀b ∈ Z. Además, si un entero x cumple que b | x, ∀b ∈ Z, entonces x = 0.
4. ±n | n ∀n ∈ Z.
5. Si b | a y a ≠ 0 entonces |b| ≤ |a|.
6. Si a | b y b | a entonces a = ±b.
7. Si a | b y b | c entonces a | c (transitiva).
8. Si db | da y d ≠ 0 entonces b | a (cancelativa).
9. Si b | a, entonces db | da para todo d ∈ Z.
10. Si d | a y d | b, entonces d | (ax + by) para todo x,y ∈ Z.
11. En particular, si d divide a n y a m, entonces d divide al resto de dividir n entre m
Definición 1.2.1. Divisores de a
Definición 1.2.1. Si a ∈ Z escribiremos Div(a) al conjunto de divisores de a y Div+(a) al conjunto de divisores positivos de a. Es decir Div(a) = {x ∈ Z : x | a} y Div+(a) = {x ∈ Z+ : x | a}.
Definición 1.2.2. numero primo
Definición 1.2.2. Decimos que un entero positivo p ∈ Z+ es primo si #(Div+(p)) = 2.
Definición 1.2.4 MCD
Definición 1.2.4. Sean a,b ∈ Z. Definimos el máximo común divisor de a y b, que escribiremos mcd(a,b) (o simplemente (a,b)), de la siguiente manera: Si a ≠ 0 o b ≠ 0, definimos
* mcd(a,b) = máx(Div(a) ∩ Div(b)) = máx{x ∈ Z : x | a y x | b}.
* En caso contrario definimos mcd(0,0) = 0.
Algoritmo de Euclides
Dados a,b ∈ Z con a ≥ b > 0. Utilizaremos la siguiente notación: al resto de dividir a entre b lo escribiremos resto(a,b).
* Fijamos r0 = b.
* Sea r1 = resto(a,b); por lo tanto tenemos que mcd(a,b) = mcd(b,r1) y que 0 ≤ r1 < b.
* Si r1 = 0 entonces mcd(a,b) = mcd(b,r1) = mcd(b,0) = b; y si no, sea r2 = resto(b,r1). Por lo tanto 0 ≤ r2 < r1 < b y mcd(a,b) = mcd(b,r1) = mcd(r1,r2).
* Si r2 = 0, entonces mcd(a,b) = mcd(b,r1) = mcd(r1,r2) = mcd(r1,0) = r1; y si no, sea r3 = resto(r1,r2).
Se sigue de esta forma, definiendo en el paso i + 1, ri+1 = resto(ri−1,ri). En particular tenemos que 0 ≤ ri+1 < ri y que mcd(ri−1,ri) = mcd(ri,ri+1).
Ahora, de esta forma vamos construyendo enteros r0,r1,r2,··· ,ri,ri+1,··· … que cumplen que 0 ≤ ··· < ri+1 < ri < ··· < r1 < r0 = b, y por lo tanto, existe n ∈ Z+ tal que rn = 0. Como en cada caso tenemos que el mcd se preserva, obtenemos:
mcd(a,b) = mcd(b,r1) = mcd(r1,r2) = ··· = mcd(rn−1,rn) = mcd(rn−1,0) = rn−1.
Es decir, mcd(a,b) = rn−1.
Definición 1.2.14. MCM
Definición 1.2.14. Dados a,b ∈ Z no nulos, definimos el mínimo común múltiplo de a y b (y lo llamaremos mcm(a,b)) como mcm(a,b) = mín{x ∈ Z+ : a | x y b | x}
Definición 1.5.2. Ecuaciones diofántica lineales
Definición 1.5.2. Una ecuación diofántica lineal en las variables x,y es una ecuación de la forma ax + by = c
con a,b,c ∈ Z.
Nos interesa buscar todas las soluciones enteras a la ecuación, por lo tanto, diremos que el conjunto solución de la ecuación es S = {(x,y) ∈ Z × Z : ax + by = c}.
A partir de ahora, cuando hablamos de una solución a la ecuación, nos referimos a un par (x,y) ∈ S
Definición 2.2.1. Congruencia
Definición 2.2.1. Fijado n ∈ Z, y dados a,b ∈ Z, decimos que a es congruente con b módulo n y escribimos a ≡ b (mód n)
si n | a − b. En caso contrario escribiremos a ≢ b (mód n).
Definición 2.4.3. Decimos que un entero a es invertible módulo n…
Definición 2.4.3. Decimos que un entero a es invertible módulo n, si existe otro entero x tal que ax ≡ 1 (mód n). Al entero x se le llama inverso de a módulo n.
Definición 2.6.1. La función de Euler
Definición 2.6.1. La función de Euler es ϕ : Z+ → Z+ dada por
ϕ(n) = #{a ∈ {1,··· ,n} : mcd(a,n) = 1}.
Cuenta la cantidad de naturales coprimos con n y menores que n
