 |
Voy a exponer en que consiste la función phi de Euler, por tener mucha importancia en la artirmética modular que estamos tratando actualmente en el foro y la teoría de números en general.
Lo haré en un post aparte al de la aritmética modular, para no liar más el post en cuestión.
Bién, vamos a ello. Un concepto primero que hay que entender, és el de dos números que son primos entre sí. Decimos que dos números son primos entre sí, si su máximo común divisor és la unidad. Es decir si no hay ningún número mayor que 1, que sea divisor de ambos,y lo expresamos diciendo que dos enteros positivos a y b son primos entre sí , sí y solo sí, mcd(a,b)=1.
Bién, sea ahora un entero positivo n cualesquiera. La función phi(n) nos da la cantidad de enteros positivos menores o iguales que n que son primos respecto a n.
Ejemplo : Phi(6)=2, porque existen 6 enteros positivos menores o iguales que n, a saber, 1,2,3,4,5,6, de los cuales solo dos, el 1 y el 5 cumplen que mcd(1,6)=1 y mcd(5,6)=1. Ello se debe a que por ejemplo 2 y 6 tienen por divisor común al 2 además del 1. 3 y 6 tienen por divisor común al 3 además del 1 etc....
Bién, ya sabemos en que consiste la función phi. Ahora nos interesaría saber si es posible calcular dicha función, sin tener que ir probando con todos los enteros menores o iguales que n, ya que eso sería una tarea muy laboriosa. Veremos que si conocemos la factorización en factores primos de n, podemos calcular con suma facilidad el valor de phi(n).
En primer lugar consideremos el caso en que n=p con p primo. Si p es primo, sus únicos divisores son la unidad y él mismo por definición. Ello quiere decir precisamente que para cualquier k entero positivo estrictamente menor que p, se cumplirá que mcd(k,p)=1. Por lo tanto phi(p)=p-1.
Ejemplo: Phi(7)=7-1=6 o Phi(13)=13-1=12
Comliquemos algo más las cosas....
Sea ahora n=p^m, es decir n és una potencia de algún número primo. De los números k que son enteros positivos menores o iguales que p^m, tenemos que solo la unidad y los múltiplos de p tienen algún divisor común con p^m. Ello quiere decir que existirán p^(m-1) números con algún divisor en común con p diferente de la unidad. Por lo tanto existirán p^m-p^(m-1)= (p-1)*p^(m-1) números tales que mcd(k,p^m)=1. Es decir tendremos que phi(p^m)=(p-1)*p^(m-1).
Ejemplo: phi(8)=phi(2^3)=(2-1)*2^2=4 o Phi(27)=phi(3^3)=(3-1)*3^2=18
Siguiendo consideraciones análogas, veriamos que si n=p^m*q^s con p y q primos, entonces phi(n)=(p-1)*p^(m-1)*(q-1)*q^(s-1), y en general si n=p1^e1*p2^e2*......*pn^en, siendo p1,p2,....,pn primos, tendriamos que phi(n)=(p1-1)*p1^(e1-1)*(p2-1)*p2^(e2-1)*......*(pn-1)*pn^(en-1).
Ejemplo: phi(18)=phi(2*3^2)=(2-1)*(3-1)*3=6 o phi(118125)=phi(3^3*5^4*7)=(3-1)*3^2*(5-1)*5^3*(7-1)=54000
La importancia de dicha función en la aritmética modular, és la siguiente. Si a y b son enteros positivos con mcd(a,b)=1, entonces a^phi(b)=1 (mod b) y b^phi(a)=1 (mod a). Este teorema se conoce como el teorema de Euler, y es una generalización del pequeño teorema de Fermat, que nos dice que dados dos enteros positivos a y p primos entre sí y siendo p un número primo, entonces a^(p-1)=1 (mod p).
No voy a dar demostración por el momento del teorema de Euler, ya que todavía hemos de avanzar en el post de aritmética modular lo suficiente, para poder hacerlo. Lo que sí diré de momento, es que este teorema nos sirve para simplificar expresiones del tipo a^n cuando trabajamos módulo b con mcd(a,b)=1.
Ejemplo : 5^(14)=(5^6)^2*5^2=1^2*5^2=4 (mod 7)
Digamos para finalizar, que estos teoremas se usan también para realizar tests probabilísticos para determinar si un número és primo, y en la criptografía RSA, entre otras cosas. Sin embargo dejaremos para futuros posts estos temas, pues para este tenemos ya material suficiente. Eso sí, antes de acabar, mencionemos que como consecuencia directa de estos teoremas, tenemos lo que se conoce como teorema de Wilson, que nos dice que un éntero positivo p es primo, sí y solo sí, (p-1)!=(p-1) (mod p). Teorema de importancia teórica, pero por desgracia de poca importancia practica, debido al gran número de operaciones que requiere para valores grandes de p.
|
| |
|
8/10/2006 09:59
La función phi de Euler
