¿Cómo encontrar el número de enteros positivos n tales que n<=164 y el MCD (n,164) = 4?

Bueno, he aquí un problema bastante sencillo. Por medio anda la función indicador (también llamada indicatriz, totalizador o totient): la función φ (phi) de Euler.

Se define como φ(1) = 1, y si m > 1 →

φ(m) = (DEF) =

= número de enteros positivos menores o iguales que m y primos con m.

Entonces, sea (n, 164) = 4 (en teoría de números es costumbre omitir las letras MCD, y escribir solo el paréntesis, con los enteros positivos cuyo máximo común divisor se representa).

Luego n debe ser múltiplo de 4, pues 4 divide a n; digamos n = 4m, con m entero positivo.

También es 164 = 4*41 (dividiendo por 4 el 164 se encuentra esta descomposición).

Hay una propiedad básica del máximo común divisor, que debe conocerse:

(ag, bg) = g * (a, b) (la demostración es muy sencilla).

Así que aplicando esta propiedad general, si n verifica la hipótesis del problema →

(n, 164) = (4m, 164) = (4m, 4*41) = 4* (m, 41) = 4 → (m, 41) = 1.

n ≤ 164 → 4m ≤ 164 → m es un entero positivo tal que m ≤ 41.

Todo se reduce a averiguar cuántos enteros positivos m, menores o iguales que 41, son primos con 41, o sea, el máximo común divisor de cualquiera de esos números y 41 debe ser 1. Por definición de la función indicador de Euler, el número de enteros positivos menores que cierto entero positivo N y primos con N (esto significa que su MCD con N es 1) es φ(N) ; así pues,

el número de enteros positivos buscado será φ(41).

Como para todo número primo p es -evidentemente- φ(p) = p - 1, y 41 es primo, resulta:

φ(41) = 40.

(Ninguno de los números 1,2,3,…40 es divisible por 41, único factor que podrían tener en común con el número primo 41, luego todos son primos con 41).

SOLUCIÓN:

El número de enteros positivos n tales que n ≤ 164 y el MCD (n,164) = 4 es 40.

Y se verifica por tanto que (4*1, 164) = (4*2, 164) = (4*3, 164) = …= (4*40, 164) = 4.