GIIT_AMA_1718_T1_Tutorial 2

695 days ago by GIIT_AMA_1718

Teoría de números

Congruencias

Aunque Sage permite trabajar en congruencias, no es algo habitual en los lenguajes de programación, por lo que trataremos de definir nosotros mismos las operaciones. Recordemos que calcular el resto es %

32423432%4322 
       
4110
4110

Por otra parte, si queremos dividir un número en sus dígitos, usaremos digits()

32432423.digits() 
       
[3, 2, 4, 2, 3, 4, 2, 3]
[3, 2, 4, 2, 3, 4, 2, 3]
32432423.digits(base=2) 
       
[1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1,
1]
[1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1]
32432423.digits(base=255) 
       
[248, 195, 243, 1]
[248, 195, 243, 1]

La operación opuesta, es decir, dar una lista de dígitos y la base y obtener el número se puede realizar definiendo Z como un anillo de enteros:

Z = IntegerRing() Z([248, 195, 243, 1],base=255) 
       
32432423
32432423

Pero es más claro crearla nosotros mismos:

def base10(cifras,base): n=len(cifras) # Obtenemos el número de cifras numero=0 # Aquí guardaremos el número for k in [1..n]: # Recorremos las cifras (están ordenadas de menor a mayor potencia. numero+=cifras[k-1]*base^(k-1) # Usamos la expresión del número en una base return numero 
       
base10([248, 195, 243, 1],255) 
       
32432423
32432423

Criterios de divisibilidad

Vamos a crearnos una función que nos devuelva el criterio de divisibilidad módulo m de un número en base 10.

def criterio_divisibilidad(modulo): CD=[1] # Partimos de que 10^0 es congruente (igual) con uno n=1 # n recorrerá las potencias a las que elevaremos 10 r=10%modulo # Calculamos el resto de dividir 10 entre el módulo while not(r in CD): # Si no hemos repetido cifra CD+=[r] # La añadimos r=10*r%modulo # Calculamos la siguiente # Si tenemos hemos obtenido un número de la lista, a partir de ese punto se repetirá rep=CD.index(r) # Obtenemos la posición del elemento que se repite return [CD[:rep],CD[rep:]] # Devolvemos dos listas: La parte que se repite y la que no 
       
CD3=criterio_divisibilidad(3) CD3 
       
[[], [1]]
[[], [1]]
CD8=criterio_divisibilidad(8) CD8 
       
[[1, 2, 4], [0]]
[[1, 2, 4], [0]]
CD11=criterio_divisibilidad(11) CD11 
       
[[], [1, 10]]
[[], [1, 10]]
CD22=criterio_divisibilidad(22) CD22 
       
[[1], [10, 12]]
[[1], [10, 12]]

Para aplicar el criterio, dividimos el número en sus cifras y multiplicamos cada una por lo que diga el criterio.

# 31242 entre 22 (2*CD22[0][0]+4*CD22[1][0]+2*CD22[1][1]+1*CD22[1][0]+3*CD22[1][1])%22 
       
2
2
31242 % 22 
       
2
2

El método anterior es muy rústico, así que vamos a automatizarlo un poco. Primero, extendemos el criterio de divisibilidad hasta que tenga más cifras que el número al que se lo queremos aplicar. Para ello usamos que sumar listas las une y que multiplicarlas las repite.

CD22ext=CD22[0]+CD22[1]*5 CD22ext 
       
[1, 10, 12, 10, 12, 10, 12, 10, 12, 10, 12]
[1, 10, 12, 10, 12, 10, 12, 10, 12, 10, 12]

Ahora basta tomar las dos listas con la misma longitud, multiplicar los pares de elementos y sumar el resultado:

n=2742398412.digits() n 
       
[2, 1, 4, 8, 9, 3, 2, 4, 7, 2]
[2, 1, 4, 8, 9, 3, 2, 4, 7, 2]
m=sum(map(prod,zip(n,CD22ext[:len(n)]))) m 
       
446
446

Nótese que aplicar el criterio sólo reduce el tamaño del número. Para obtener el resto, aplicamos % (también podríamos definir la suma módulo m para obtenerlo en un único paso).

m % 22, 2742398412 % 22 
       
(6, 6)
(6, 6)

Potencias

Para obtener el resto de dividir una potencia entre un número, necesitaremos la función $\phi$ de Euler. En Sage esta función es euler_phi.

euler_phi(8) 
       
4
4

Recordemos que la función $\phi$ de un número n es el número de primos con él entre 1 y $n-1$.

n=8 sum([1 for i in [1..n-1] if gcd(n,i)==1]) 
       
4
4

Aunque es más rápido calcularla a partir de una descomposición en factores primos:

n=8 n*prod([ 1/m for m,_ in n.factor()]) 
       
4
4

Una vez tenemos la función $\phi$, el Teorema de Euler nos permite calcular potencias grandes:

# Vamos a intentar calcular el resto de n^a entre m, donde n=3243 a=12432 m=35 
       
# Comprobamos si la base y el módulo son primos entre sí gcd(n,35) 
       
1
1
# Como lo son, n^phi(m) es 1 módulo m n^euler_phi(m) % m 
       
1
1
# Luego basta elevar n al resto de dividir a entre phi(m) n^(a % euler_phi(m)) % m 
       
1
1
# Comprobamos n^a % m 
       
1
1

Ejercicios

1. Pasar los siguientes números a base 10:

  • $1010001001010_2$
  • $(43,34,31,23,43,10,32)_{64}$
  • $AF54A34A47$

2. Calcular los siguientes restos usando los criterios de divisibilidad: 34235235 entre 8, 423423432 entre 12, 432432423 entre 25, 4234324234 entre 35.

3. Definir una función que sume los números de una lista módulo un número. Es decir, los irá sumando de uno en uno y quedándose en cada paso con el resto.

4. Crea una función que calcule el resto de dividir un número entre otro usando los criterios de divisibilidad.

5. Calcula el resto de 342342 elevado a  32421 módulo 49.

6. Crea una función que reciba tres números n,a,m, compruebe si n y m son primos entre si y en dicho caso devuelva el resto de dividir n^a entre m.