MA14 para AV1

Prévia do material em texto

MA14 para AV1 
 
1) Divisibilidade: 
a|b (a divide b) ⇒ ∃c ∈ Z | b=c.a (c 
é quociente de b por a, a é divisor 
de b, b é múltiplo de a); 
a, b, c, d, x, y ∈ Z: 
a|b ⇒ ±a|±b; 
1|a, 
a|a, 
a|0, 
0|a ⇒ a = 0 
a|b, b|c ⇒ a|c (prop.1); 
a|b, c|d ⇒ a.c|b.d (prop.2); 
a|b±c, a|b ⇔ a|c (prop.3); 
a|b,a|c ⇒ a|xb+yc (prop. 4); 
c>0 ⇒ c ≥ 1; 
b≠0, ∃n ∈ Z | nb > a (prop. 
Arquimediana); 
a, b ∈ N, a|b ⇒ a ≤ b (prop.5); 
relação de ordem (R, AS, T); 
a-b|an-bn (prop.6), 
a+b|a2n+1+b2n+1 (prop.7), 
a+b|a2n–b2n (prop.8); 
i!|produto de i naturais consecutivos 
(resumo). 
 
2) Divisão Euclidiana: 
a, b ∈ Z, a≠0 ⇒ ∃q, r únicos | b = 
a.q + r, 0≤r<|a| (teo. 1); 
a, b ∈ N, a >0, ∃n ∈ Z | na ≤ b < 
(n+1)a (cor.2); 
a, b ∈ N, a < b, q é o número de 
múltiplos não nulos de a, menores 
ou iguais a b. 
 
3) Sistemas de Numeração: 
a, b ∈ N, b>1 ⇒ ∃ únicos c0, c1, ... 
cn ∈ N, menores ou iguais a b, com 
a=c0+c1b+c2b
2+...+cnb
n (teo.1); 
expansão relativa a uma base aplica 
sucessivamente a divisão euclidiana, 
condições de divisibilidade. 
 
4) Jogo de Nim: --. 
 
5) Máximo Divisor Comum: 
a, b ∈ Z, não simultaneamente 
nulos, d ∈ Z é divisor comum se d|a 
e d|b; 
MDC é único d = (a,b) se d|a, d|b e 
todo divisor comum é divisor de d; 
(a, b) = (b, a); 
(0, a) = |a|; 
(a, a) = |a|; 
(1, a) = 1; 
(a, b) = (-a, b) = (a, -b) = (-a, -b); 
∀ b ∈ Z, a|b ⇔ (a,b) = |a|; 
∃ (a, b-na) ⇒ ∃ (a, b) = (a, b-na) 
(Lema de Euclides); 
a, m ∈ N, a>1 ⇒ ((am – 1) ÷ (a-1), 
a – 1) = (a - 1, m) (exemplo 1); 
a, b ∈ N, a ≤ b, a = 1 ou a = b ou 
a|b ⇒ (a,b) = a; 
1 < a < b e a não divide b, b = aq1 
+ r1, 0 < r1 < a, prosseguindo a 
divisão até que rn|rn-1 ⇒ (a,b) = rn 
(algoritmo de Euclides). 
Exemplo: (372, 162) 
372=162x2+48;162=48x3+18;48=
18x2+12;18=1x12+6. Como 6|12, 
(372, 162)=6. Usando as 
expressões de trás para frente, 
podemos exprimir (372,162) como 
um múltiplo de 372 mais um múltipo 
de 162: 6 =18-1x12=18–1x(48-
18x2) = 18-48+18x2=3x18-
48=3x(162-3x48)–48=3x162-
10x48= 3x 162-10x(372-
162x2)=23x162+ (-10)x372 
(algoritmo de Euclides estendido). 
 
6) Propriedades do mdc: 
a, b ∈ Z, não ambos nulos, I(a,b) = 
{xa + yb; x, y ∈ Z}, d = min I(a,b) 
∩ N ⇒ d = (a,b) e I(a,b) = dZ = 
{ld; l ∈ Z} (teo.1); 
a, b ∈ Z, não ambos nulos, n ∈ N ⇒ 
(na, nb) = n(a,b) (cor.2); 
a, b ∈ Z, não ambos nulos ⇒ 
(a/(a,b),b/(a,b))= 1 (cor.3); 
a, b ∈ Z, primos entre si ⇔ ∃ n, m ∈ 
Z | na+nb=1 (prop.4); 
a, b, c ∈ Z, a|b.c e (a,b)=1 ⇒ a|c 
(teo.5, lema de Gauss); 
a, b, c ∈ Z, b, c não ambos nulos, 
b|a e c|a ⇔ bc / (b,c) | a (cor.6); 
(a1, ..., an) = (a1, ..., (an-1, an)) 
(prop.7). 
 
7) Mínimo Múltiplo Comum: 
[a,b] = m ⇔ m é múltiplo comum 
de a e b e, se c é múltiplo comum 
de a e b, m|c; 
a, b ∈ N, não nulos, ∃ [a,b] e 
[a,b](a,b) = ab (prop.1); 
a, b ∈ N, primos entre si, [a,b] = ab 
(cor.2); 
[a1, ..., an] = [a1, ..., [an-1, an]] 
(prop.3). 
 
8) Equações Diofantinas 
Lineares: 
aX + bY = c, com a, b, c, X, Y ∈ Z, 
a, b ≠ 0 admite solução ⇔ (a,b)|c 
(prop. 1); 
(a,b) = 1 ⇒ há solução; 
(x0, y0) é solução ⇒ (x0 + tb, y0 – 
ta) é solução (prop.2); 
a, b, c ∈ N, (a,b)=1, c pode ser 
escrito de modo único como 
na+mb, 0≤n< b, m ∈ Z (prop. 3); 
a, b ∈ N, (a,b) = 1, S(a,b) 
semigrupo gerdo por a e b, S(a,b) = 
{xa + yb, x, y ∈ N U {0}}; 
aX + bY = c tem solução se, e 
somente se, c ∈ S(a,b) ⇔ ∃ n, m ∈ 
N U {0}, n < b, univocamente 
determinados, tais que c = na + mb 
(prop.4); 
lacunas L(a,b) = N – S(a,b) = {na – 
mb ∈ N, n, m ∈ N, n < b} (cor.5); 
aX + bY = c, (a,b) = 1 tem solução 
natural ⇔ c ∉ L(a,b) (teo.6), que é 
finito e tem como maior elemento 
máx L(a,b)= (b-1)a–b; 
a equação tem solução natural, 
portanto, se c > (b-1)a – b; 
x0 = m, y0 = n ⇒ x=n+tb; y=m–ta, 
t ∈ N U {0}, m – ta ≥ 0 (prop.7). 
 
9) Atividade Especial Revisão: -- 
 
10) Expressões Binômias: 
Seja sequência (an)n tal que, ∀ 
m≥n, (am,an)=(an,ar) ⇒ (am,an) = 
a(m,n) (prop. 1); 
d = (m,n) ⇒ (am-1,an-1) = ad-1 
(prop. 2); 
n = mq + r ⇒ (an+1,am-1) = (am-1; 
ar+1) (lema 3); 
m = nq + r ⇒ (am-1,an+1) = 
(an+1,ar-1), se q par, ou 
(an+1;ar+1), se q ímpar (lema 4); 
m = nq + r ⇒ (am+1; an+1) = 
(an+1; ar+1), se q par, ou (an+1; ar-
1); se q ímpar (lema 5); 
a, n, m ∈ N, n|m e m/n é par ⇒ 
(am+1; an+1) = 1, se a par, ou 2, se 
a ímpar (prop.6); 
a≥2 ⇒ (am-1, an-1) = a(m,n) – 1 e 
(am±1, an±1) pode assumir apenas 
os valores 1, 2 ou a(m,n)+1 (teo.7); 
(am+1; an+1) = a(n,m) + 1, se k = 
[m,n]/(m,n) ímpar; 2, se k par e a 
ímpar; 1, se k e a pares (cor. 9); 
(am – 1, an + 1) = a(n,m) + 1, se 
m/(m,n) par e n/(m,n) ímpar; 2, 
caso contrário e a ímpar; 1, caso 
contrário e a par (cor. 10). 
 
11) Números de Fibonacci: 
n,m ∈ N, n≥2 ⇒ un+m = un-
1um+unum+1; (un+1,un)=1 (lema 1, 
PIF); n|m ⇒ un|um (lema 2, PIF); 
(um,un) = u(m,n) (teo. 3); un | um ⇔ 
n|m (cor. 4).