Vivemos em um mundo onde a informação corre os continentes num piscar de olhos. Sites de buscas permitem que um pesquisador, em…

Vivemos em um mundo onde a informação corre os continentes num piscar de olhos. Sites de buscas permitem que um pesquisador, em questão de segundos, obtenha centenas de informações sobre um determinado assunto, ou seja, o mundo em um clique. Isso ocorre pelo fato de existir um banco de dados enorme e certamente um algoritmo de busca muito eficiente. A matemática, e em particular a teoria dos números, contribui para que tudo isso possa ocorrer. Uma função que tem muita aplicabilidade na computação é a função φ de Euler, cuja definição é: “para todo número inteiro positivo n ≠ 0, temos φ (n) = quantidade de números inteiros positivos menores que n e primos entre si de n, isto é, a função conta a quantidade de inteiros positivos r<n, tais que mdc (r,n)=1”. Como, por exemplo, φ (10)=4, pois os únicos números positivos menores e primos de 10 são 1, 3 , 7 e 9. De maneira geral, se p é um número primo, então φ (pk)=pk-1(p-1), para todo número inteiro estritamente positivo k. Com base nessas informações, marque a alternativa que tem o valor de φ (3125) correto: