Números coprimos.

(1/1)

7up:
Hola, me gustaría saber si hay algún método para saber qué números son coprimos entre 1 y [texx]n[/texx].
Así como para saber los números primos usamos la criba de Eratóstenes.
Sé que entre [texx]1[/texx] y [texx]n[/texx], el número de coprimos viene dado por la función de Euler, pero me gustaría saber cuáles son.
Por cierto, ¿posee el programa Derive, alguna función de este estilo?

¡Saludos!

el_manco:
Hola

 No estoy seguro de qué quieres contar exactamente.

 La función de Euler cuenta los números coprimos con uno dado menores que él:

 [texx]\varphi(m)=cardinal\{n\in N|n<m,\quad m.c.d(n,m)=1\}[/texx]

 Entonces cuando dices "saber que números son coprimos entre 1 y n", ¿te refieres a coprimos con n?. O quizá a parejas de números [texx](a,b)[/texx] coprimas entre si ([texx]m.c.d(a,b)=1,\quad 1<a,b,<n[/texx]).

Saludos.

7up:
Hola, me refería a los números coprimos con uno dado menores que él.
Por ejemplo, numeros coprimos con 5, y menores que él:
1,2,3 y 4

Gracias.

el_manco:
Hola

 Ah, entiendo. Puedes hacer una criba de Eratóstenes adaptada. Divides n en factores primos:

[texx] n=p_1^{k_1}\ldots p_s^{k_s}[/texx]

 y vas tachando los múltiplos de [texx]p_1[/texx], del [texx]p_2[/texx], hasta [texx]p_s[/texx].

Saludos.

Navegación

[0] Índice de Mensajes