Matemática para Ensino Superior (53)

Prévia do material em texto

CENTRO DE CIÊNCIAS E TECNOLOGIA - CCT
DEPARTAMENTO DE MATEMÁTICA
Luiz Lima de Oliveira Junior
MA14 - Unidade 20
Campina Grande - PB
2013
1 -Ache o resto da divisão de
(a) 560 por 26.
Solução:
1o - Maneira: 52 ≡ −1 (mod 26) =⇒ 560 ≡ 1 (mod 26).
2o - Maneira: Como (5, 26) = 1 então pelo (Teorema Euler) Teorema 5, 5ϕ(26) ≡ 1
(mod 26), onde Como 26 = 2 ·13 então ϕ(26) = ϕ(2 ·13) Prop. 7= ϕ(2)ϕ(13) = (2−
1) · (13− 1) = 12. Assim, 512 ≡ 1 (mod 26) =⇒ (512)5 ≡ 15 (mod 26) =⇒ 560 ≡ 1
(mod 26). Portanto o resto da divisão de 560 por 26 é 1.
(b) 3100 por 10.
Solução: ϕ(10) = ϕ(2 · 5) = ϕ(2) ·ϕ(5) · (2− 1) · (5− 1) = 4 Pelo teorema de Euler,
temos que 34 ≡ 1 (mod 10), logo, 3100 = 3(4·5) ≡ 30 ≡ 1 (mod 10). Segue que o
resto da divisão de 3100 por 10 é 1.
2 - Mostre que, se m > 2, então ϕ(m) é par.
Solução: Se m > 2, é um número primo e ϕ(m) = m− 1, é é um número par. Suponha
agora que m seja composto:
Então ϕ(m) = (pα1−11 p
α2−1
2 · . . . · pαrr − 1) · (p1 − 1) · (p2 − 1) · . . . · (pr − 1)
Assim,
i) se m for ı́mpar, então os primos pi, i = 1, ..., r são ı́mpares. Logo, (p1 − 1), (p2 −
1), . . . , (pr − 1) são pares. Então ϕ(m) é par.
ii) se m for par, então pi é par para algum i, logo ϕ(m) é par.
3 - Mostre que, se p é um número primo, então, para todo a ∈ Z e para todo k ∈ N,
tem-se que
ak(p=1)+1 ≡ a (mod p)
Demonstração:
4 -
1
(a) Mostre que
∑
(i,m)=1
i<m
i =
1
2
mϕ(m).
Demonstração: Seja a1, a2, . . . , aϕ(m) os inteiro i menores que m e primos com m. Como
(a,m) = 1 se, e somente se, (m − a,m) = 1, os inteiro positivos menores que m e que
são primos com m podem ser expressos pelas diferenças:
n− a1, n− a2, . . . , n− aϕ(m).
Portanto,
a1 + a2 + . . .+ aϕ(m) = n− a1 + n− a2 + . . .+ n− aϕ(m)
= mϕ(m)− (a1 + a2 + . . .+ aϕ(m))
O que implica
2(a1 + a2 + . . .+ aϕ(m)) = mϕ(m) =⇒ a1 + a2 + . . .+ aϕ(m) =
1
2
mϕ(m)
(b) Mostre que, se m1 . . .mϕ(m) é um sistema reduzido de reśıduos módulo m, então m
divide m1 . . .mϕ(m).
5 -Resolva em m ∈ N as equações
(a) ϕ(m) = 12 (c) ϕ = 16
(b) ϕ(m) = 8 (d) ϕ = 24
6 - Supondo que (a,m) = (a− 1,m) = 1, mostre que:
1 + a+ a2 + . . .+ aϕ(m)−1 ≡ 0(mod. m)
Demonstração:
Como (a,m) = 1, então aϕ(m) ≡ 1(mod. m). Logo: 1 + a + a2 + . . . + aϕ(m)−1 ≡
0(mod. m) é equivalente à 1 + a+ a2 + . . .+ aϕ(m)−1 + aϕ(m) ≡ 0(mod. m). Dáı, queremos
provar que:
a+ a2 + aϕ(m) =
a(aϕ(m) − 1)
(a− 1)
.
Sabemos que m não divide a e m não divide (a−1). Ainda temos que m divide (aϕ(m)−1).
Como (a− 1)|aϕ(m) − 1, temos que m
∣∣∣∣a(aϕ(m) − 1)(a− 1) . Dáı,
a(aϕ(m) − 1)
(a− 1)
≡ 0(mod. m)
2
7 -Mostre que, se ϕ(m) = 2r, para algum r ∈ N, então m é um produto de uma potência
de 2 e de primos de Fermat distintos1.
Demonstração: Seja m = pα11 . . . p
αk
r a decomposição de m em fatores primos, onde 2 =
p1 < p2 < . . . < pk. Pelo Teorema 17 (Lucas), temos:
ϕ(m) = pα0−11 p
α2−1
2 . . . p
αk−1
k (p1 − 1) · . . . · (pk − 1) = 2
r
Como p2, . . . , pk são diferentes de 2, devemos ter α1 = ... = αk = 1. Além disso,
pi− 1 = 2αi , para i = 1, ..., k, logo, pi = 2βi + 1. Como pi é primo, segue-se da proposição
1 (unidade 15) que βi = 2
ni para algum ni ∈ N. Logo
m = 2α0(22
n1 + 1) . . . (22
nk + 1),
onde (22
n1 + 1) . . . (22
nk + 1) são primos de Fermat distintos.
8 -Supondo que (m;n) = 1, mostre que mϕ(n) + nϕ(m) ≡ 0(mod. nm)
9 - Sejam a,m ∈ Z, com m > 1, tais que (a;m) = 1. Mostre que, se n1 ≡ n2
(mod ϕ(m)), então an1 ≡ an2 (mod m).
10 - Mostre que 2730|n13 − n, para todo n ∈ Z.
Demonstração: Inicialmente, note que 2370 = 2 · 3 · 5 · 7 · 13. Vamos mostrar que
2, 3, 5, 7, 13|n13 − n, para todo n inteiro.
• Pelo teorema 5, nϕ(2) ≡ 1 (mod 2). Então, n1 ≡ 1 (mod 2). Dáı, pelo corolário 4
da unidade 18, n12 ≡ 112 (mod 2), ou seja, n12 ≡ 1 (mod 2). Logo, pelo corolário
11 da unidade 18, n13 ≡ n (mod 2) e 2|n13 − n.
• Pelo teorema 5, nϕ(3) ≡ 1 (mod 3). Então, n2 ≡ 1 (mod 3). Dáı, pelo corolário 4
da unidade 18, n12 ≡ 16 (mod 3), ou seja, n12 ≡ 1 (mod 3). Logo, pelo corolário
11 da unidade 18, n13 ≡ n (mod 3) e 3|n13 − n.
• Pelo teorema 5,nϕ(5) ≡ 1 (mod 5). Então, n4 ≡ 1 (mod 5). Dáı, pelo corolário 4
da unidade 18, n12 ≡ 13 (mod 5), ou seja, n12 ≡ 1 (mod 5). Logo, pelo corolário
11 da unidade 18, n13 ≡ n (mod 5) e 5|n13 − n.
• Pelo teorema 5, nϕ(7) ≡ 1 (mod 7). Então, n6 ≡ 1 (mod 7). Dáı, pelo corolário 4
da unidade 18, n12 ≡ 12 (mod 7), ou seja, n12 ≡ 1 (mod 7). Logo, pelo corolário
11 da unidade 18, n13 ≡ n (mod 7) e 7|n13 − n.
1 Essa equação aparece na resolução dada por Gauss do problema clássico da construtibilidade com
régua e compasso dos poĺıgonos regulares inscritos numa circunferência.
3
• Pelo teorema 5, nϕ(13) ≡ 1 (mod 13). Então, n12 ≡ 1 (mod 13). Dáı, pelo corolário
11 da unidade 18, n13 = n (mod 13) e 13|n13 − n.
Portanto, 2730|n13 − n, para todo n inteiro.
11 - Sejam a ∈ Z e n, r ∈ N, com (r, n) = 1. Mostre que no conjunto
{a, a+ r. . . . , a+ (n− 1)r},
há exatamente ϕ(n) números primos com n.
12 - Mostre que o número primo p é o menor inteiro maior do que 1 que divide o número
(p− 1)! + 1.
13 - Mostre que se p > 2 é um número primo, então
(a) p
∣∣∣∣(p− 2)!− 1;
Demonstração: Pelo Teorema de Wilson, se p é um número primo, então
(p− 1)! ≡ −1 (mod p)⇐⇒ p
∣∣∣∣[(p− 1)! + 1].
Como (p− 1)! = (p− 1)(p− 2)! = p(p− 2)!− (p− 2)!. Assim,
p
∣∣∣∣[(p− 1)! + 1] =⇒ p∣∣∣∣[p(p− 2)!− (p− 2)! + 1] =⇒ p∣∣∣∣(p(p− 2)!− [(p− 2)!− 1]).
Como p divide a soma e p
∣∣∣∣[p(p − 2)! então pela proposição 3 da unidade 1, p divide a
outra parcela, isto é,
p
∣∣∣∣(p− 2)!− 1.
(b) p
∣∣∣∣(p− 3)!− (p− 1)2 .
Demonstração: Pelo Teorema de Wilson, se p é um número primo, então
(p− 1)! ≡ −1 (mod p)⇐⇒ p
∣∣∣∣(p− 1)! + 1.
Então,
p
∣∣∣∣(p− 1)! + 1− p⇐⇒ p∣∣∣∣(p− 1)!− (p− 1)⇐⇒ (p− 1)! ≡ (p− 1) (mod p). Dáı,
4
(p− 1)(p− 2)! ≡ (p− 1) (mod p) (p−1,p)=1⇐⇒
(p− 2)! ≡ 1 (mod p)⇐⇒(p− 2)(p− 3)! ≡ 1 (mod p)⇐⇒
p(p− 3)!− 2(p− 3)! ≡ 1 (mod p).
Como p
∣∣∣∣p(p− 3)!, então −2(p− 3)! ≡ 1 (mod p) =⇒ 2(p− 3)! ≡ −1 (mod p), ou seja,
p
∣∣∣∣2(p− 3)! + 1 =⇒ 2(p− 3)! + 1 = pk
=⇒ 2(p− 3)! + 1− p = pk − p
=⇒ 2(p− 3)!− (p− 1) = p(k − 1)
Como 2(p− 3)! é par e p− 1 também é pois, p > 2 e primo. Então k− 1 é par. Portanto,
(p− 3)!− (p− 1)
2
= p
(
k − 1
2
)
=⇒ p
∣∣∣∣(p− 3)!− (p− 1)2 .
14 -Seja p > 3 um número primo.
(a) Mostre que p! e (p− 1)!− 1 são primos entre si.
(b) Prove que, se n ∈ N e n ≡ (p−1)!−1(mod.p!), então os (p−2) inteiros que precedem
n e os p inteiros sucedem n são compostos.
15 -Seja p um número primo e a ∈ N. Mostre que
(a) ap + (p− 1)!a ≡ 0(mod. p).
(b) (p− 1)!ap + a ≡ 0(mod. p).
16 - Seja p um número primo tal que p ≡ 1 mod.4. Mostre que[(
p− 1
2
)
!
]2
≡ −1 mod. p.
17 -Seja p um número primo tal que p ≡ 3 mod.4. Mostre que[(
p− 1
2
)
!
]2
≡ 1 mod. p.
5
18 -Seja p um número primo ı́mpar e seja N = 1·3·5 · · · (p−2). Mostre que N ≡ 1mod p
ou N ≡ −1modp.
19 -Seja p um número primo ı́mpar. Mostre que
(a) 12 · 32 · 52 · · · (p− 2)2 ≡ 22 · · · 42 . . . (p− 1)2(mod. p).
(b) Se p ≡ 1(mod. 4), então 22 · · · 42 . . . (p− 1)2 ≡ −1(mod. p).
(c) Se p ≡ 3(mod. 4), então 22 · · · 42 . . . (p− 1)2 ≡ 1(mod. p).
1 Exerćıcios Suplementares
20 - Se n ∈ N então ϕ(n)|n se, e somente se, n é da forma 1, 2a, 2a3b, onde a, b ∈ N.
21 - Sejam m,n ∈ N e d = (m,n). Mostre que ϕ(mn) = dϕ(m)ϕ(n)
ϕ(d)
.
22 - Mostre que ϕ(m2) = mϕ(m) para todo m ∈ N.
Demonstração: Como (m,m) = m. Então pelo exerćıcio anterior.
ϕ(mm) =
mϕ(m)ϕ(m)
ϕ(m)
= mϕ(m).
23 - Mostre que, d|n, então ϕ(d)|ϕ(n).
24 - Mostre que, se r1, . . . rs e r
′
1, . . . r
′
t são sistema reduzidos de reśıduos respectivamente
módulo m e m′, então os números rim
′ + r′jm onde 1 ≤ i ≤ s e 1 ≤ j ≤ t formam um
sistema reduzido de reśıduos módulo mm′.
25 - Utilize o problema anterior para dar uma outra prova da Proposiçao 3.
26 - Encontre o algarismo da unidade do número 2323
2323
Demonstração: Para resolução da questão iremos considerar:Corolário I - Para todo n ∈ N, a, b ∈ Z, se a ≡ b (mod m), então tem-se que an ≡ bn
(mod m).
Proposição II - Sejam a, b, c, d,m ∈ Z, com m > 1 . Se a ≡ b (mod m) e c ≡ (mod m),
então ac ≡ bd (mod m).
Proposição III - Seja m ∈ N. Para todos a, b, c ∈ Z, tem-se que, se a ≡ b (mod m) e
b ≡ c (mod m) então a ≡ c mod m. Note inicialmente que
6
234 = 279841 ≡ 1 mod 10
Pelos corolário I, temos:
(234)5 ≡ 15 mod 10
2320 ≡ 1 mod 10
Temos também que
233 = 12167 ≡ 7 mod 10
Agora, pela proposição II e pelas congruências
2320 ≡ 1 mod 10
e
233 = 1267 ≡ 7 mod 10
segue, que
2320.233 ≡ 1.7 mod 10
2323 ≡ 7 mod 10
Aplicando o corolário I na congruência anterior temos que
(2323)4 ≡ 74 mod 10
e
(2323)3 ≡ 73 mod 10
Mas,
74 = 2401 ≡ 1 mod 10
e
73 = 343 ≡ 3 mod 10
Pela proposição III, segue que
(2323)4 ≡ 1 mod 10
e
(2323)3 ≡ 3 mod 10
7
Aplicando novamente o corolário I a congruência (2323)4 ≡ 1 mod 10, temos
((2323)4)5 ≡ 15 mod 10
ou seja,
(2323)20 ≡ 1 mod 10
Pela proposição II e pelas congruências (2323)20 ≡ 1 mod 10 e (2323)3 ≡ 3 mod 10, segue
que
(2323)20.(2323)3 ≡ 1.3 mod 10
Dáı,
(2323)23 ≡ 3 mod 10
Aplicando mais uma vez o corolário I e as proposições IIeIII a congruência anterior,
temos que
((2323)23)4 ≡ 34 mod 10
e, 34 = 81 ≡ 1 mod 10
Dáı,
((2323)23)4 ≡ 1 mod 10
Agora,
(((2323)23)4)5 ≡ 15 mod 10
((2323)23)20 ≡ 1 mod 10
e
((2323)23)3 ≡ 33 mod 10
Sendo, 33 = 27 ≡ 7 mod 10, temos
((2323)23)3 ≡ 7 mod 10
Dáı,
((2323)23)20.((2323)23)3 ≡ 1.7 mod 10
Logo,
((2323)23)23 ≡ 7 mod 10
Portanto, o algarismo da unidade do número 2323
2323
é 7.
Boa Sorte
8
	Exercícios Suplementares