Lista 3 - Numeros primos, mdc e mmc

Prévia do material em texto

Universidade Federal do Ceara´
Campus de Quixada´
Matema´tica Discreta
Primos, Fatorac¸a˜o, MDC e MMC
1. Mostre que 101 e´ primo.
Suponha por absurdo que 101 na˜o e´ primo. Se 101 na˜o e´ primo enta˜o 101 possui um divisor primo menor ou igual
√
101. Os u´nicos primos
menores
√
101 sa˜o 2,3,5 e 7. Pore´m, 101 ≡ 1 (mod 2), 101 ≡ 2 (mod 3), 101 ≡ 1 (mod 5) e 101 ≡ 3 (mod 7). Nenhum dos nu´meros
primos menores que
√
101 dividem 101. Logo, 101 e´ primo.
2. Mostre que os nu´meros primos sa˜o infinitos.
Suponha por absurdo que existe uma quantidade finita de nu´meros primos {p1, p2, p3, . . . , pn} com todos pi > 1. SejaA = p1p2 . . . pn+
1. Pelo Teorema Fundamental da Aritme´tica, A e´ primo ou A pode ser escrito como o produto de dois ou mais primos. Se A e´ primo enta˜o
chegamos em uma contradic¸a˜o porque assumimos que todos os primos esta˜o na lista {p1, p2, p3, . . . , pn}. SeA e´ composto enta˜o suponha
que exista algum p ∈ {p1, p2, p3, . . . , pn} tal que p|A. Como p|p1p2 . . . pn, enta˜o p|A − p1p2 . . . pn = 1. Logo, na˜o existe nenhum
p ∈ {p1, p2, p3, . . . , pn} que divide A, caso contra´rio, p ≤ 1. Portanto, chegamos em uma contradic¸a˜o porque assumimos que a lista de
primos estava completa. (Observe que esta prova e´ na˜o construtiva, a partir de n primos, podemos encontrar um primo que na˜o esta´ lista.)
3. Usando o me´todo anterior, encontre um nu´mero primo que na˜o esta´ na seguinte lista de primos:
(a) {2,3} Considere A = 2 ∗ 3 + 1 = 7. Como 7 e´ primo, encontramos um primo que na˜o esta´ lista.
(b) {2,7} Considere A = 2 ∗ 7 + 1 = 15. Como 15 na˜o e´ primo, todo divisor primo de 15 na˜o esta´ lista, ou seja, {3,5}.
(c) {2,3,5} Considere A = 2 ∗ 3 ∗ 5 + 1 = 61. Como 61 e´ primo, encontramos um primo que na˜o esta´ lista.
4. O valor da func¸a˜o φ de Euler para o nu´mero inteiro positivo n e´ definido como sendo o nu´mero de inteiros positivos menores ou iguais a
n que sa˜o relativamente primos de n (primos entre si).
Dado uma fatorac¸a˜o em primos de n, ou seja, n = pα11 p
α2
2 . . . p
αk
k , onde p1, . . . , pk sa˜o primos distintos e os expoentes αi ≥ 1 para
todo i. O valor da func¸a˜o φ de Euler para um inteiro positivo n e´ definido pela seguinte fo´rmula:
φ(n) = n(1− 1
p1
)(1− 1
p2
) . . . (1− 1
pn
) (1)
Por exemplo, φ(12) = |{n|mdc(n, 12) = 1}| = |{1, 5, 7, 11}| = 4. A fatorac¸a˜o de 12 e´ 22 × 31. Logo,
φ(12) = 12(1− 1
2
)(1− 1
3
) = 12(
1
2
)(
2
3
) = 4 (2)
Adapte o algoritmo de fatorac¸a˜o em primos para calcular φ(n)
function EULER(n)
res← n
i← 2
while n > 1 do
cont← 0
while n%i == 0 do
n← n/i
cont← cont+ 1
end while
if cont > 0 then
res = (res ∗ (i− 1))/i
end if
i← i+ 1
end while
return res
end function
5. Use o algoritmo de Euclides para encontrar
(a) mdc(12,18)
Pelo Algoritmo de Euclides,
mdc(12, 18) = mdc(18, 12) = mdc(12, 6) = mdc(6, 0) = 6 (3)
(b) mdc(1331,1001)
Pelo Algoritmo de Euclides,
mdc(1331, 1001) = mdc(1001, 330) = mdc(330, 11) = mdc(11, 0) = 11 (4)
(c) mdc(201,111)
Pelo Algoritmo de Euclides,
mdc(201, 111) = mdc(111, 90) = mdc(90, 21) = mdc(21, 6) = mdc(6, 3) = mdc(3, 0) = 3 (5)
6. Se o produto de dois nu´meros inteiros e´ 273852711 e seu ma´ximo divisor comum e´ 23345, qual e´ o mı´nimo mu´ltiplo comum entre eles?
Seja a e b dois inteiros tal que ab = 273852711 e mdc(a, b) = 23345. Enta˜o,
mdc(a, b)×mmc(a, b) = ab (6)
Logo, mmc(a, b) = 243451711
1
7. Mostre que mdc(11n+ 5, 7n+ 3) e´ 2 se n e´ ı´mpar e 1 se n e´ par.
Vamos mostrar que se n e´ ı´mpar enta˜o mdc(11n+ 5, 7n+ 3) = 2.
Seja um inteiro n = 2k + 1. Vamos calcular
mdc(11(2k + 1) + 5, 7(2k + 1) + 3) = mdc(22k + 11 + 5, 14k + 7 + 3) = mdc(22k + 16, 14k + 10) (7)
1 1 1 2 1 k
22k + 16 14k + 10 8k + 6 6k + 4 2k + 2 2k 2
8k + 6 6k + 4 2k + 2 2k 2 0
8. Use o algoritmo de Euclides estendido para expressar o mdc(252, 198) como combinac¸a˜o linear de 252 e 198.
R Q m n
252 * 1 0
198 * 0 1
54 1 1 -1
36 3 -3 4
18 1 4 -5
0 2
Logo, mdc(252,198) = 18 = 252(4) + 198(-5).
9. Se b|a e c|a e mdc(b, c) = 1 enta˜o bc|a
Seja a = bk e a = cj. Pelo algoritmo de euclides estendido, sabemos que existem r, s ∈ Z tal que br + cs = 1.
Logo,
br + cs = 1
abr + acs = a Multiplicando por a
cjbr + bkcs = a Substituindo os valores de a
bcjr + bcks = a
bc(jr + ks) = a
Conclu´ımos que bc|a.
10. Se mdc(n, 6) = 1 enta˜o 12|n2 − 1.
Todo nu´mero n pode ser escrito como 6k, 6k+1, 6k+2, 6k+3, 6k +4, 6k+5.
Caso 1: Se n = 6k enta˜o mdc(6k,6) = 6. Como a premisa e´ falsa, enta˜o a implicac¸a˜o e´ verdadeira.
Caso 2: Se n = 6k+1 enta˜o mdc(6k+1,6) = 1. Enta˜o, n2 − 1 = (6k + 1)2 − 1 = 36k2 + 12k + 1− 1 = 12(3k2 + k)
Caso 3: Se n = 6k+2 enta˜o mdc(6k+2,6) = 2. Como a premisa e´ falsa, enta˜o a implicac¸a˜o e´ verdadeira.
Caso 4: Se n = 6k+3 enta˜o mdc(6k+3,6) = 3. Como a premisa e´ falsa, enta˜o a implicac¸a˜o e´ verdadeira.
Caso 5: Se n = 6k+4 enta˜o mdc(6k+4,6) = 2. Como a premisa e´ falsa, enta˜o a implicac¸a˜o e´ verdadeira.
Caso 6: Se n = 6k+5 enta˜o mdc(6k+5,6) = 1. Enta˜o, n2 − 1 = (6k + 5)2 − 1 = 36k2 + 60k + 25− 1 = 12(3k2 + 5k + 2)
11. Resolva as seguintes congrueˆncias usando o inverso encontrado no exerc´ıcio anterior:
(a) 2x ≡ 7 (mod 17)
Como mdc(17,2)=1, podemos usar o algoritmo de Euclides Estendido para encontrar o inverso multiplicativo de 2 mo´dulo 17
R Q m n
17 * 1 0
2 * 0 1
1 8 1 -8
0 2 X X
Logo, 17(1) + 2(-8) = 1. Implicando que, 2(−8) ≡ 1 (mod 17).
Assim,
2x ≡ 7 (mod 17)
2(−8)x ≡ 7(−8) (mod 17)
x ≡ −56 (mod 17)
ou ainda,
x ≡ 17(−4) + 12 (mod 17)
x ≡ 12 (mod 17)
12. Resolva os seguintes sistemas de congrueˆncia linear
(a) x ≡ 3 (mod 6)
x ≡ 4 (mod 7)
Se x ≡ 3 (mod 6) enta˜o x = 6k + 3. Substituindo na equac¸a˜o seguinte, temos
6k + 3 ≡ 4 (mod 7)
6k + 3− 3 ≡ 4− 3 (mod 7)
6k ≡ 1 (mod 7) (3)
Como mdc(6,7)=1, podemos encontrar facilmente uma combinac¸a˜o linear de 6 e 7 igual a 1. 7(1) + 6(-1) = 1. Logo,
6(−1) ≡ 1 (mod 7).
Multiplicando por (-1), obtemos
6(−1)k ≡ 1(−1) (mod 7)
k ≡ −1 (mod 7)
ou ainda, k ≡ 7(−1) + 6 (mod 7)
k ≡ 6 (mod 7)
ou seja, k = 7s+ 6.
Substituindo o valor de k, temos que x = 6k + 3 = 6(7s+ 6) + 3 = 42s+ 36 + 3 = 42s+ 39, ou seja, x ≡ 39 (mod 42).
2