Questão de Fluência em Dados · FGV Receita Federal do Brasil 2023 - Manhã (nº 66)

O Algoritmo de Euclides é um método para encontrar o Máximo Divisor Comum (MDC) entre dois números inteiros, que é o maior número que divide ambos sem deixar resto. Ele funciona substituindo o par de números pelo menor deles e o resto da divisão do maior pelo menor, repetindo até que um dos números seja zero, momento em que o outro número é o MDC.

(A) Incorreta: O MDC de 90 e 15 não é 1. 1 seria o MDC se os números fossem primos entre si (coprimos).
(B) Incorreta: Embora 3 seja um divisor comum de 90 e 15, ele não é o máximo divisor comum. A armadilha aqui é confundir um divisor comum com o maior divisor comum. O algoritmo de Euclides busca especificamente o maior.
(C) Incorreta: 6 não é um divisor de 15, portanto não pode ser o MDC de 90 e 15.
(D) Correta: O código implementa o Algoritmo de Euclides. Vamos rastrear a execução com a = 90 e b = 15:

1. while b != 0 (15 != 0 é verdadeiro): a, b = b, a % b se torna a, b = 15, 90 % 15. Como 90 % 15 é 0, os novos valores são a = 15 e b = 0.
2. while b != 0 (0 != 0 é falso): O loop termina.
3. A função retorna o valor atual de a, que é 15. Portanto, o MDC de 90 e 15 é 15.
   (E) Incorreta: 75 não é um divisor de 15, nem de 90, portanto não pode ser o MDC.