PDF de programación - Números y hoja de cálculo VIII

Números y hoja de cálculo VIII



Curso 2015-16



Colección Hojamat.es

© Antonio Roldán Martínez

http://www.hojamat.es

1





PRESENT ACIÓN



El octavo volumen de resúmenes del blog “Números y
hoja de cálculo”, correspondiente a la temporada 2015-
16, contiene una cantidad de material superior a los
anteriores. La causa es la inclusión de nuestros
números arolmar, que no tienen gran interés teórico,
pero que nos han servido para practicar el
descubrimiento de propiedades, como
los
semiprimos enlazados.

la de



El resto de temas presenta una distribución similar a la
de publicaciones anteriores: predominio de
las
cuestiones de divisibilidad y números primos junto a
otras cuestiones de Combinatoria, números poligonales
y comprobación de conjeturas. A lo largo de los años se
han convertido en los fundamentos del blog.



Una agradable novedad han sido
las sucesiones
curiosas, que si tampoco tiene gran interés teórico,



2


amenizan
entretenidas.
Intentaremos
sucesivas entradas del blog.

cuestiones matemáticas

resultan
incluir alguna más en

y



3





CONTENIDO



Presentación ............................................................ 2

Contenido ................................................................. 4

Grupos de potencias en Zn ..................................... 6

Índice o gaussiano de un resto en Zn ..................... 6

Subgrupos cíclicos en Zm* ..................................... 17

Raíces primitivas ................................................... 24

Índices modulares ................................................. 32

Sucesiones curiosas.............................................. 39

Sucesión de Recamán .......................................... 39

Sucesión de Golomb ............................................. 51

Números belgas .................................................... 59

Sucesión de Mian-Chowla ..................................... 66

La permutación Yellowstone ................................. 74

Siempre aparecen los primos ............................... 84

Los interprimos ..................................................... 84

¿Qué hay entre dos primos consecutivos? ........... 94

“Palprimos” (primos palindrómicos) ..................... 113



4





Semiprimos consecutivos .................................... 120

Otra vez los poligonales ...................................... 129

Damos vueltas a los triangulares cuadrados ....... 129

Comprobación de conjeturas .............................. 149

Primos de Fibonacci ............................................ 149

Conjetura de Oppermann .................................... 156

Algo de Combinatoria .......................................... 163

Función “parking” ................................................ 163

Rachas de dígitos ............................................... 168

Volvemos a los números AROLMAR .................. 176

Historia y generación .......................................... 176

Diferencias .......................................................... 187

Coincidencias ...................................................... 196

¿Qué hay entre dos arolmar? ............................. 204

Semiprimos arolmar ............................................ 212

Semiprimos arolmar enlazados ........................... 221

Números “arolmar” con más de dos factores....... 230

Números “superarolmar” ..................................... 242

Números arolmar cuadráticos ............................. 252

Miscelánea ............................................................ 264

Una curiosidad sin importancia ........................... 264

5



GRUPOS DE POTENCIAS EN ZN


ÍNDICE O GAUSSIANO D E UN RESTO EN ZN

Iniciamos hoy el desarrollo de
teoría
perteneciente a la Aritmética Modular, la de las raíces
primitivas y temas afines.

toda una

Teoría previa

Resumimos brevemente
teoría previa que es
conveniente conocer antes de seguir esta serie de
temas:

la

Comenzamos con la estructura Zm formada por los
restos posibles al dividir un número entre m. Ya sabes
que este conjunto es la base de la Aritmética Modular (o
del reloj)

Puedes repasar las páginas

http://es.wikipedia.org/wiki/Aritm%C3%A9tica_modu
lar

http://hojamat.es/sindecimales/congruencias/teoria/t
eorcong.htm

http://mathworld.wolfram.com/ModularArithmetic.ht
ml



6


Este conjunto Zm con la suma y la multiplicación forma
un anillo cíclico de m elementos. Por esta estructura
cíclica se pensó en llamarles anillos por primera vez.
Es un anillo con unidad, por lo que puede contener
elementos inversibles. De ellos trataremos aquí.

Un elemento A de Zm es inversible si existe otro
elemento X de Zm tal que A*X1 (mod m). Esta
ecuación se sabe que tiene solución única siempre que
A sea primo con el modulo m. Luego los restos
primos con m son inversibles.

Por el contrario, si A y m tienen un divisor común, para
que la ecuación tuviese solución debería ser divisor
también de 1, lo que es imposible. Si el elemento A
tiene divisores comunes con m, entonces A no es
inversible.

Llamamos divisor de cero en un anillo a aquel
elemento A que multiplicado por cierto elemento no nulo
C del anillo, da un producto nulo: A*C=0. Si que A tiene
factores comunes con m, es un divisor de cero,
porque si D=MCD(A,m), tendremos que A=A’*D y
m=m’*D. Multiplicando A por m’ (que es no nulo) resulta
Am’=A’D*m/D=A’m, que es congruente con cero, luego

A*m’0 (mod m) y por tanto divisor de cero.

Los divisores de cero no son inversibles, porque si A
fuera inversible y divisor de cero, se daría una igualdad



7


del
tipo A*C=0 con C distinto de cero, pero
multiplicando por el inverso resultaría: A-1*A*C=C=A-1*0
lo que daría C=0 en contra de lo supuesto.

Así que:

 Si el elemento A es primo con el módulo m,
entonces es inversible, es decir, que existe
algún otro elemento B
tal que A*B=B*A=1.
Anteriormente vimos cómo encontrarlo mediante
el algoritmo extendido de Euclides

(http://hojaynumeros.blogspot.com.es/2012/06/la-
herencia-de-euclides-1-el-algoritmo.html).

 Si el elemento A no es primo con m, es un

divisor de cero, y por tanto no inversible.



Grupo de inversibles

El producto de dos inversibles A y B también lo es, y su
inverso es B-1*A-1, ya que

(B-1*A-1)*A*B=B-1*(A-1*A)*B=B-1*1*B=1

Como el 1 es inversible trivialmente y el inverso
también, tenemos que los inversibles forman grupo
abeliano para la multiplicación, llamado grupo de las
unidades Z*m



8


Como es conocido, la función indicatriz de Euler cuenta
los números menores que m y primos con él, por tanto,
el cardinal del grupo Z*m coincide con la indicatriz o
función φ(x) de Euler.

Se cumple el llamado Teorema de Euler

a(m) 1 (mod m)

para todo a primo con m o unidad.

Orden multiplicativo, índice o gaussiano de un
elemento

Dado un elemento inversible a, llamaremos orden de
ese elemento al mínimo número entero tal que ar1.
Según el teorema anterior, ese valor existe y puede ser
φ(m) y todos sus múltiplos. Si es menor, ha de ser un
divisor suyo. En efecto, supongamos que φ(m) no fuera
múltiplo del orden r. Entonces efectuando la división
entera entre ambos quedaría φ(m)=qr+s, con s<r.
Aplicamos esa potencia al elemento a y obtendríamos

1a φ(m) aqr+saqr*as as , luego as1 en contra del
carácter mínimo de r.

Así que el orden ha de ser un divisor de la función
φ(m). Toda potencia que sea igual a 1 tendrá un
exponente múltiplo de ese orden. Hay muchas formas
de representar el orden o gaussiano. Aquí por



9


comodidad tipográfica representaremos el gaussiano de
N respecto al módulo M como G(N,M)

Podíamos habernos ahorrado el razonamiento anterior
recordando el Teorema de Lagrange para grupos, que
afirma que el orden de un subgrupo H es divisor del
orden del grupo G. En este caso este último es φ(m) y
como las potencias de a forman un grupo monógeno,
su orden será divisor de φ(m).

Vemos algunos ejemplos:

Orden de 5 módulo 8: Como 5 es primo con 8 y φ(8)=4,

el orden podrá ser 2 o 4: 5^2=251(8, luego el orden de
5 con módulo 8 es 2, o G(5,8)=2

Orden del 3 respecto al 7: φ(7)=6, luego el orden podrá

ser 2, 3 o 6. Probamos: 3^2=92(7, 3^3=276(7,

3^6=7291 (7luego el orden o gaussiano de 3 es 6,
G(3,7)=6



Estudio con hoja de cálculo

Deseamos desarrollar este tema con calma. Así que
nos pararemos un poco, con la ayuda de la hoja de
cálculo alojada en



10


http://www.hojamat.es/sindecimales/congruencias/herra
mientas/herrcong.htm#gaussiano

Distinguiremos, en principio, tres niveles de complejidad
en el descubrimiento del gaussiano de un número.

NIVEL 1

La hoja funciona sólo con las fórmulas de celdas, sin
macros. Para ello basta escribir el número N y el
módulo M, y calcular en columna las potencias de N en
el grupo de las unidades Z*m. En la hoja hemos
incluido el cálculo del MCD(N,M), que ha de ser 1 y, en
caso contrario, se avisa del error.

En la imagen hemos escrito dos números no primos
entre sí y la hoja nos avisa:



Simultáneamente, en las columnas del NIVEL 1, se
construyen las potencias para ver cuál de ellas es igual
a 1, con lo que obtendremos el gaussiano de N. A
continuación reproducimos el cálculo correspondiente a
5 módulo 13:



11