Lista de exercicios Equacoes diofantinas, congruencias e classes de residuos em Z, funcao de Euler

Prévia do material em texto

Universidade de Bras´ılia
Departamento de Matema´tica– IE
A´lgebra 1 – Turma C
Semana 4 – Lista de exerc´ıcios
Temas abordados: Equac¸o˜es diofantinas, congrueˆncias e classes de res´ıduos em Z;
func¸a˜o de Euler.
(1) Calcule os seguintes valores da func¸a˜o φ de Euler:
a) φ(125);
b) φ(16200);
c) φ(2097).
(2) Calcule o valor de m sabendo que:
(a) φ(m) = 22;
(b) φ(m) = 23;
(c) φ(m) = 24;
(d) φ(m) = 25;
(f) φ(m) = 32 · 2;
(g) φ(m) = 10.
(3) Resolva as seguintes equac¸o˜es diofantinas.
(a) 7x− 9y = 1;
(b) 4x− 3y = 2;
(c) 6x+ 4y = 3;
(d) 6x+ 4y = 6;
(e) 12x− 18y = 360;
(f) 144x+ 125y = 329;
(g) 36x− 21y = 31;
(h) 350x− 91y = 731;
(i) 49x− 70y = 39.
(4) Sejam a, b, c ∈ Z, com a, b na˜o nulos simultaneamente. Prove que todas as
soluc¸o˜es (quando existirem) da equac¸a˜o ax+ by = c sa˜o da forma
x =
b
MDC(a, b)
k + x0, y = − a
MDC(a, b)
k + y0,
onde k ∈ Z e (x0, y0) e´ uma soluc¸a˜o particular da equac¸a˜o diofantina.
[Dica: Primeiro verifique que as expresso˜es para x e y dadas satisfazem a
equac¸a˜o e depois verifique que uma soluc¸a˜o inteira qualquer da equac¸a˜o tem
que ser da forma dada.]
(5) Escreva as tabelas da adic¸a˜o e da multiplicac¸a˜o de Z/6Z e Z/11Z.
(6) Fac¸a o que se pede nos itens abaixo, com respeito a classes de res´ıduos em
Z:
a) Ache os elementos invers´ıveis em Z/6Z,Z/7Z e em Z/8Z;
b) Ache os inversos de 5¯, 4¯, 8¯ em Z/9Z e os inversos de 3¯, 4¯, 5¯ em Z/7Z.
1
2
(7) Dados n,m ∈ N definimos(
n
m
)
=
n!
(n−m)!m! , para 0 ≤ m ≤ n.
(a) Seja p um primo qualquer e 1 ≤ k < p, com p, k ∈ Z. Prove que(
p
k
)
≡ 0 mod p;
(b) Usando o item (a) prove que se p e´ um inteiro primo, com p ≥ 2 enta˜o
(x+ y)p ≡ xp + yp mod p, ∀x, y ∈ Z.
(8) Resolva as seguintes congrueˆncias:
(a) 3x ≡ 5 mod 7
(b) 4x ≡ 2 mod 3
(c) 7x ≡ 21 mod 49
(d) 3x ≡ 1 mod 6
(e) 18x ≡ 12 mod 42
(f) 12x ≡ 9 mod 15
(g) 240x ≡ 148 mod 242
(h) 6125x ≡ 77 mod 189
Universidade de Bras´ılia
Departamento de Matema´tica – IE
A´lgebra 1 – Turma C
Semana 4 – Soluc¸o˜es
Temas abordados: Equac¸o˜es diofantinas, congrueˆncia e classes de res´ıduos em Z,
func¸a˜o de Euler.
Exerc´ıcios:
(1) Calcule os seguintes valores da func¸a˜o φ de Euler:
(a) φ(125) = φ(53) = 53 − 52 = 100,
(b) φ(16200) = φ(233452) = φ(23)φ(34)φ(52) = (23− 22)(34− 33)(52− 5) =
4 · 54 · 20 = 4320
(c) φ(2097) = φ(32233) = φ(32)φ(233) = (32 − 3)232 = 6 · 232 = 1392.
(2) Calcule o valor de m sabendo que:
(a) φ(m) = 22, temos m ∈ {5, 8, 10, 12};
(b) φ(m) = 23, temos m ∈ {15, 16, 20, 24, 30} ;
(c) φ(m) = 24, temos m ∈ {17, 32, 34, 40, 48, 60} ;
(d) φ(m) = 25, temos m ∈ {51, 64, 68, 80, 96, 102, 120};
(e) φ(m) = 32 · 2, temos m ∈ {19, 27, 38, 54};
(f) φ(m) = 10, temos m ∈ {11, 22}.
(3) Resolva as seguintes equac¸o˜es diofantinas:
(a) 7x− 9y = 1; todas as soluc¸o˜es sa˜o da forma
{x = 4 + 9k, y = 3 + 7k, k ∈ Z}.
(b) 4x− 3y = 2; todas as soluc¸o˜es sa˜o da forma
{x = 2 + 3k, y = 2 + 4k, k ∈ Z}.
(c) 6x+ 4y = 3; como MDC(6, 4) = 2 - 3, enta˜o na˜o ha´ soluc¸o˜es.
(d) 6x+ 4y = 6; todas as soluc¸o˜es sa˜o da forma
{x = 1 + 2k, y = −3k, k ∈ Z}.
(e) 12x− 18y = 360; todas as soluc¸o˜es sa˜o da forma
{x = 30 + 3k, y = 2k, k ∈ Z}.
(f) 144x+ 125y = 329; todas as soluc¸o˜es sa˜o da forma
{x = 116 + 125k, y = −131− 144k, k ∈ Z}.
(g) 36x− 21y = 31; como MDC(36,−21) = 3 - 31, enta˜o na˜o ha´ soluc¸o˜es.
(h) 350x − 91y = 731; como MDC(350,−91) = 7 - 731, enta˜o na˜o ha´
soluc¸o˜es.
(i) 49x− 70y = 39; como MDC(49,−70) = 7 - 39, enta˜o na˜o ha´ soluc¸o˜es.
(4) Sejam a, b, c ∈ Z, com a e b na˜o-nulos simultaneamente. Prove que todas as
soluc¸o˜es (quando existirem) da equac¸a˜o ax+ by = c sa˜o da forma
x =
b
MDC(a, b)
k + x0 y = − a
MDC(a, b)
k + y0,
onde k ∈ Z e (x0, y0) e´ uma soluc¸a˜o particular da equac¸a˜o diofantina.
1
2
Prova: Lembramos que a equac¸a˜o possui soluc¸a˜o se e somente seMDC(a, b) | c.
Primeiro vamos verificar que as expresso˜es para x e y dadas sa˜o sempre
soluc¸a˜o da equac¸a˜o. Seja (x0, y0) uma soluc¸a˜o particular, enta˜o temos que
ax0 + by0 = c e segue da´ı que
a(x0 +
b
MDC(a, b)
k) + b(y0 − a
MDC(a, b)
k) = ax0 +
ab
MDC(a, b)
k + by0 − ba
MDC(a, b)
k
= ax0 + by0 = c, ∀k ∈ Z
Agora vamos provar que qualquer soluc¸a˜o inteira da equac¸a˜o dada tem que
ser da forma desejada. Seja (x, y) uma soluc¸a˜o, ou seja, vale que ax+by = c.
Como (x0, y0) e´ outra soluc¸a˜o, temos que ax0+by0 = c. Em particular, temos
a(x− x0) + b(y − y0) = c− c = 0. Segue que:
a
MDC(a, b)
(x− x0) + b
MDC(a, b)
(y − y0) = 0,
ou seja,
(∗) a
MDC(a, b)
(x− x0) = − b
MDC(a, b)
(y − y0).
Notamos que aMDC(a,b) | − bMDC(a,b)(y−y0), mas comoMDC( aMDC(a,b) ,− bMDC(a,b)) = 1,
enta˜o devemos ter aMDC(a,b) | (y − y0). Disso tudo, pode-se concluir que
y − y0 = a
MDC(a, b)
h, para algumh ∈ Z.
Substituindo o resultado anterior em (∗) temos:
a
MDC(a, b)
(x− x0) = − b
MDC(a, b)
(
a
MDC(a, b)
h
)
,
o que implica
x− x0 = − b
MDC(a, b)
h, para algumh ∈ Z.
Conclu´ımos que
x = x0 − b
MDC(a, b)
h, y = y0 +
a
MDC(a, b)
h,
e fazendo k = −h temos
x = x0 +
b
MDC(a, b)
k, y = y0 − a
MDC(a, b)
k, k ∈ Z,
como quer´ıamos demonstrar.
(5) Escreva as tabelas da adic¸a˜o e da multiplicac¸a˜o de Z/6Z e Z/11Z.
+ 0¯ 1¯ 2¯ 3¯ 4¯ 5¯
0¯ 0¯ 1¯ 2¯ 3¯ 4¯ 5¯
1¯ 1¯ 2¯ 3¯ 4¯ 5¯ 0¯
2¯ 2¯ 3¯ 4¯ 5¯ 0¯ 1¯
3¯ 3¯ 4¯ 5¯ 0¯ 1¯ 2¯
4¯ 4¯ 5¯ 0¯ 1¯ 2¯ 3¯
5¯ 5¯ 0¯ 1¯ 2¯ 3¯ 4¯
· 0¯ 1¯ 2¯ 3¯ 4¯ 5¯
0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯
1¯ 0¯ 1¯ 2¯ 3¯ 4¯ 5¯
2¯ 0¯ 2¯ 4¯ 0¯ 2¯ 4¯
3¯ 0¯ 3¯ 0¯ 3¯ 0¯ 3¯
4¯ 0¯ 4¯ 2¯ 0¯ 4¯ 2¯
5¯ 0¯ 5¯ 4¯ 3¯ 2¯ 1¯
3
+ 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0
0¯ 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0
1¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0 0¯
2¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0 0¯ 1¯
3¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0 0¯ 1¯ 2¯
4¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0 0¯ 1¯ 2¯ 3¯
5¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0 0¯ 1¯ 2¯ 3¯ 4¯
6¯ 6¯ 7¯ 8¯ 9¯ 1¯0 0¯ 1¯ 2¯ 3¯ 4¯ 5¯
7¯ 7¯ 8¯ 9¯ 1¯0 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯
8¯ 8¯ 9¯ 1¯0 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯
9¯ 9¯ 1¯0 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯
1¯0 1¯0 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯
· 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0
0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯ 0¯
1¯ 0¯ 1¯ 2¯ 3¯ 4¯ 5¯ 6¯ 7¯ 8¯ 9¯ 1¯0
2¯ 0¯ 2¯ 4¯ 6¯ 8¯ 1¯0 1¯ 3¯ 5¯ 7¯ 9¯
3¯ 0¯ 3¯ 6¯ 9¯ 1¯ 4¯ 7¯ 1¯0 2¯ 5¯ 8¯
4¯ 0¯ 4¯ 8¯ 1¯ 5¯ 9¯ 2¯ 6¯ 1¯0 3¯ 7¯
5¯ 0¯ 5¯ 1¯0 4¯ 9¯ 3¯ 8¯ 2¯ 7¯ 1¯ 6¯
6¯ 0¯ 6¯ 1¯ 7¯ 2¯ 8¯ 3¯ 9¯ 4¯ 1¯0 5¯
7¯ 0¯ 7¯ 3¯ 1¯0 6¯ 2¯ 9¯ 5¯ 1¯ 8¯ 4¯
8¯ 0¯ 8¯ 5¯ 2¯ 1¯0 7¯ 4¯ 1¯ 9¯ 6¯ 3¯
9¯ 0¯ 9¯ 7¯ 5¯ 3¯ 1¯ 1¯0 8¯ 6¯ 4¯ 2¯
1¯0 0¯ 1¯0 9¯ 8¯ 7¯ 6¯ 5¯ 4¯ 3¯ 2¯ 1¯
(6) • Lembrando que a¯ e´ invers´ıvel em Z/nZ se e somente se MDC(a, n) = 1,
temos que
- os elementos invers´ıveis em Z/6Z sa˜o: {1¯, 5¯};
- os elementos invers´ıveis em Z/7Z sa˜o {1¯, 2¯, 3¯, 4¯, 5¯, 6¯}, e
- os elementos invers´ıveis em Z/8Z sa˜o {1¯, 3¯, 5¯, 7¯}.
• Encontre os inversos de 5¯, 4¯, 8¯ em Z/9Z e os inversos de 3¯, 4¯, 5¯ em Z/7Z.
Lembramos que encontrar o inverso de a¯ em Z/nZ e´ equivalente a so-
lucionar a congruencia linear ax ≡ 1 mod n. Temos que:
Em Z/9Z,
(5¯)−1 = 2¯, (4¯)−1 = 7¯, (8¯)−1 = 8¯;
Em Z/7Z,
(3¯)−1 = 5¯, (4¯)−1 = 2¯, (5¯)−1 = 3¯.
(7) Dados n,m ∈ N, definimos(
n
m
)
=
n!
(n−m)!m! , para 0 ≤ m ≤ n.
4
(i) Seja p um primo e 1 ≤ k < p, com p, k ∈ Z. Prove que(
p
k
)
≡ 0 mod p;
(ii) Usando o item (i) prove que se p e´ um inteiro primo, com p ≥ 2, enta˜o
(x+ y)p ≡ xp + yp mod p ∀x, y ∈ Z.
Prova:
(i) Notamos que, por definic¸a˜o,
(
p
k
)
= p!(p−k)!k! e, portanto,(
p
k
)
(p− k)!k! = p! = p(p− 1)!
Assim, p | (pk)(p− k)!k!. Como 1 ≤ k ≤ p− 1, temos que
MDC(p, (p− k)!k!) = 1,
e, como p e´ um nu´mero primo, a u´nica possibilidade que resta e´
p |
(
p
k
)
,
como quer´ıamos.
(ii) Temos que
(x+ y)p =
p∑
k=0
(
p
k
)
xp−kyk = xp +
p−1∑
k=1
(
p
k
)
xp−kyk + yp ≡ xp + yp mod p,
ja´ que pelo item (i)
∑p−1
k=1
(p
k
)
xp−kyk ≡ 0 mod p.
(8) Resolva as seguintes congrueˆncias:
Lembramos que dada
ax ≡ b mod n,
essa equac¸a˜o tem soluc¸o˜es se e somente se MDC(a, n) | b, e nesse caso te-
mos exatamente MDC(a, n) soluc¸o˜es distintas mod n calculadas da seguinte
forma:
x0, x0 +
n
MDC(a, n)
, x0 + 2
n
MDC(a, n)
, . . . , x0 + (MDC(a, n)− 1) n
MDC(a, n)
.
Aqui, x0 e´ uma soluc¸a˜o particular qualquer da equac¸a˜o diofantina ax−ny =
b.
(a) 3x ≡ 5 mod 7; como MDC(3, 7) = 1 e 1|5, enta˜o existe uma u´nica
soluc¸a˜o mod7, que e´ x = 4.
(b) 4x ≡ 2 mod 3; como MDC(4, 3) = 1 e 1|2, enta˜o existe uma u´nica
soluc¸a˜o mod3, que e´ x = 2.
(c) 7x ≡ 21 mod 49; como MDC(7, 49) = 7 e 7|21, enta˜o existem 7 soluc¸o˜es
distintas mod49, que sa˜o {x = 3, x = 10, x = 17, x = 24, x = 31, x =
38, x = 45}
(d) 3x ≡ 1 mod 6; como MDC(3, 6) = 3 e 3 - 1, enta˜o na˜o existem soluc¸o˜es.
5
(e) 18x ≡ 12 mod 42; como MDC(18, 42) = 6 e 6|12, enta˜o existem 6
soluc¸o˜es distintas mod42, que sa˜o {x = 3, x = 10, x = 17, x = 24, x =
31, x = 38}
(f) 12x ≡ 9 mod 15; como MDC(12, 15) = 3 e 3|9, enta˜o existem 3 soluc¸o˜es
distintas mod15, que sa˜o {x = 2, x = 7, x = 12}
(g) 240x ≡ 148 mod 242; como MDC(240, 242) = 2 e 2|148, enta˜o existem
2 soluc¸o˜es distintas mod242, que sa˜o {x = 47, x = 168}
(h) 6125x ≡ 77 mod 189. como MDC(6125, 189) = 7 e 7|77, enta˜o exis-
tem 7 soluc¸o˜es distintas mod189, que sa˜o {x = 1, x = 28, x = 55, x =
82, x = 109, x = 136, x = 163}