(I) Ao determinar todos os primos entre 2 e 143 utilizando o crivo de Eratóstenes, o primeiro momento em que podemos ter certeza de que todos os números não riscados já são primos ocorre após riscarmos os múltiplos dos primos p tais que:
(a) p <= 139
(b) p <= 10
(c) p <= 71
(d) p <= 11
(e) p <= 12
(II) Considere as seguintes equações diofantinas:
(i) x+4 y=10
(ii) 2 x+4 y=10
(iii) 2 x+4 y=11
(iv) x+4 y=11
É correto afirmar que:
(a) Apenas (i), (ii) e (iii) possuem solução.
(b) Apenas (i), (ii) e (iv) possuem solução.
(c) Apenas (i), (iii) e (iv) possuem solução.
(d) Apenas (ii), (iii) e (iv) possuem solução.
(e) Nenhuma das opções anteriores.

Passo 1

Beleza, o exercício tem dois “pernadas” de teoria de números:
I) Sobre o crivo de Eratóstenes para achar todos os primos entre 2 e 143. A pergunta é: depois de riscarmos os múltiplos de quais primos p a gente já pode garantir que todo número não riscado é primo?
II) Quatro equações diofantinas (equações lineares ax+by=c) e precisamos descobrir quais têm solução inteira.
O que vamos usar:
  • Para o crivo, a ideia de que basta riscar múltiplos de primos até raizN.
  • Para as diofantinas, o fato de que ax+by=c tem solução inteira se e só se gcd(a,b) divide c.

Passo 2

Resolvendo a parte I (Crivo de Eratóstenes)
  1. A regra básica é: para determinar todos os primos até N, a gente só precisa riscar múltiplos dos primos p com p <= raizN.
  2. Aqui N=143, então raiz143approx11,96.
  3. Isso significa que já basta riscar múltiplos de todos os primos p <= 11.
    Logo a resposta para I) é a opção (d): p<=11.

Passo 3

Resolvendo a parte II (Equações diofantinas)
Regra: a equação ax+by=c tem solução inteira iff gcd(a,b)mid c.
Vamos cada uma:
(i) x+4y=10
  • gcd(1,4)=1 e 1mid10. Então tem solução.
(ii) 2x+4y=10
  • gcd(2,4)=2 e 2mid10. Então tem solução.
(iii) 2x+4y=11
  • gcd(2,4)=2 e 2notmid11. Então NÃO tem solução.
(iv) x+4y=11
  • gcd(1,4)=1 e 1mid11. Então tem solução.
Só (i), (ii) e (iv) funcionam, ou seja, alternativa (b).

Resposta

I) (d)
II) (b)

Exercícios relacionados