Acurtar o cálculo do inverso multiplicativo modular

Presentamos un novo artigo de Andrés Ventas.

Inverso multiplicativo modular

Resolver o inverso multiplicativo módulo $b$ é unha tarefa común na teoría de números. Aparece a miúdo na solución de sistemas de congruencias.

A forma estándar de atopar un inverso multiplicativo módulo $b$ é usar o algoritmo de Euclides estendido. Nun artigo de 1999, Glasby compara os dous métodos máis usados actualmente para o algoritmo euclidiano estendido: recorrencia cara atrás e recorrencia cara adiante. O método aquí presentado é máis curto en ambos os casos.

O problema que temos que resolver é atopar o $x$ da ecuación $ax\equiv 1(\mathrm{mod}b),a<b$. Se temos $a>b$ o xeito máis sinxelo é substituír $a$ por $amodb$. O noso algoritmo usa as propiedades das fraccións continuas mixtas, que traducido ao algoritmo de Euclides sería usar a función teito ou a función chan dependendo do menor residuo.

Necesitamos que os dous números implicados sexan coprimos, e aquí podemos ver un exempliño que se saca a ollo:

Dado que $gcd(3,10)=1$, a congruencia linear $3x\equiv 1(\mathrm{mod}10)$ terá solucións, é dicir, existirán inversos multiplicativos modulares de $3$ módulo $10$. De feito, o $7$ satisfai esta congruencia (é dicir, $21-1=20$). Por tanto $7$ é un inverso modular de $3$ módulo $10$.

Outros números enteiros tamén satisfán a congruencia, por exemplo $17$ e $-3$ (é dicir, $3(17)-1=50$ e $3(-3)-1=-10$). En particular, cada número enteiro en $\bar{7}$ satisfará a congruencia xa que estes enteiros teñen a forma $7+10r$ para algún enteiro $r$ e

$$3(7+10r)-1=21+30r-1=20+30r=10(2+3r),$$

é divisíbel por $10$.

Exemplo máis elaborado: Inverso multiplicativo modular

$91x\equiv 1(\mathrm{mod}254)$ $\mathbf{\text{Mediante o algoritmo de Euclides estendido.}}$

índice i	Cociente $q_{i+1}$ $\lfloor r_i/r_{i+1}\rfloor$	resto $r_i$	$s_i$	$t_i$
0		$254$	1	0
1		$91$	0	1
2	2	72	1	2
3	1	19	1	3
4	3	15	4	11
5	1	4	5	14
6	3	3	19	53
7	1	1	24	x=67
8	3	0	91	254

Os $s_i$ e os $t_i$ obtéñense coa mesma recorrencia que nas fraccións continuas, isto é $s_{i+1}=q_{i+1}{s}_i+s_{i-1}$ e $t_{i+1}=q_{i+1}{t}_i+t_{i-1}$, $s_i$ comezando por $(1,0)$ e $t_i$ por $(0,1)$. Maxicamente o inverso multiplicativo modular aparece na columna das $t_i$.

Efectivamente $x=67$ e temos $91\cdot 67=6097\equiv 1(\mathrm{mod}254)$ pois $254\cdot 24=6096$.

Completamente máxico non o é, pois existen varias probas e está tamén relacionado coa identidade de Bézout.

Algoritmo mixto para obter o inverso multiplicativo modular

Sexa $ax\equiv 1(\mathrm{mod}b),a<b$, a congruencia para a que procuramos o inverso multiplicativo.

1. Bucle principal.

$$ 1.1.Comezando con $a_0=a,b_0=b$, aplicamos $\lceil {\displaystyle \frac{b_i}{a_i}}\rfloor =(k_i,\pm )$ ata obtermos $b_n=k_n{a}_n\pm 1$. Isto quere dicir que en cada división ficamos co divisor $k_i$ que teña menor resto ao aplicar a función chan ou a función teito e no caso de ser chan anotamos ese coeficiente cun signo $\mathbf{\text{"+"}}$ e se a función usada foi a teito marcamos o coeficiente cun signo $\mathbf{\text{"-"}}$.

$$ 1.2. Ao mesmo tempo, obtemos $a^{-1}(\mathrm{mod}b)$. $x_{-1}=1,x_0=k_0;x_i:k_i\cdot x_{i-1}\pm x_{i-2}$.

(Note que o signo da recurrencia $i$ é o signo da operación previa $\lceil k_{i-i}\rfloor ,\pm$).

2. Paso final.

Se o número das operacións de truncado (función chan, símbolo $+$) é par daquela $a^{-1}(\mathrm{mod}b)=x_n$ noutro caso $a^{-1}(\mathrm{mod}b)=b-x_n$.

Exemplos co algoritmo mixto

Nunha notación compacta podemos escribir tres filas. A fila superior contén os coeficientes da división enteira mixta, a segunda fila contén os residuos da operación e a terceira a recorrencia coa que obtemos a inversa multiplicativa modular. A recorrencia no algoritmo mixto pode ser sumando $t_{i+1}=q_{i+1}{t}_i+t_{i-1}$ ou restando $t_{i+1}=q_{i+1}{t}_i-t_{i-1}$ dependendo de se o coeficiente anterior se obtivo con función chan (+) ou teito (-).

$61x\equiv 1(\mathrm{mod}2114)$.

$q_i$		${35}^{-}$	$3^{-}$	${10}^{+}$
$r_{i-1}$	2114	$61$	$21$	$2$	$1$
$t_i$	1	$35$	$104$	$1005$	$x=2114-1005=1109$

Comprobamos $x=1109$, temos $61\cdot 1109=67649\equiv 1(\mathrm{mod}2114)$ pois $32\cdot 2114=67648$.

Nota: no exemplo de enriba non chegamos a utilizar a recorrencia positiva pois só temos función chan no último coeficiente que non chegamos a usar pois o signo da recorrencia vai dependendo do coeficiente anterior.

$91x\equiv 1(\mathrm{mod}254)$. Este é o mesmo exemplo que fixemos enriba.

$q_i$		$3^{-}$	$5^{-}$	$5^{-}$
$r_{i-1}$	254	91	19	4	1
$t_i$	1	3	14	67	$x=67$

E efectivamente temos outra vez $91\cdot 67=6097$ e $254\cdot 24=6096$, só con 3 divisións en vez de 6.

Bibliografia

1. S. P. Glasby, Extended Euclid’s algorithm via backward recurrence relations, Mathematics Magazine, 72(3)(1999), 228–230.
2. Galipedia, Algoritmo de Euclides estendido
3. Galipedia, Inverso multiplicativo modular
4. Cálculos online do inverso multiplicativo modular
5. Galipedia, Identidade de Bézout

Os conceptos na aula de matemáticas

Os profesores de matemáticas vémonos de cote fronte ao reto de introducir na aula novos conceptos. Algúns do gremio consideran fundamental establecer desde o primeiro momento unha definición precisa dos conceptos a traballar. Recordo o caso dun compañeiro que aos alumnos de 15 anos lles introducía os vectores libres como unha relación de equivalencia no conxunto de vectores fixos; despois aínda lles demostraba, entre outras cousas, que as operacións con esas clases de equivalencia non dependían do representante elixido. Algúns dos seus alumnos acudiran a min, desesperados, para que lles explicara algo diso. Despois dalgúns intentos só puiden certificar que era imposible que eses rapaces chegaran a entender outra cousa que as matemáticas eran incomprensibles. Tiñan moi claro que esta materia era  unha fonte de angustias e un obstáculo para o desenvolvemento dos seus estudos.

Hai profesores que, polo contrario, consideran que na clase de matemáticas é superfluo tratar os conceptos. O fundamental é traballar os procedementos. Unha vez aprendidos estes, o resto non importa. Así as clases consisten en practicar unha cadea interminable de algoritmos, moitas veces sen razón ningunha. 

Fronte a estas dúas posturas teño un fermoso recordo como alumno. O profesor pedíranos que pensáramos no concepto máis fundamental, no máis simple das matemáticas.

- Sumar - dixo alguén

- Non hai nada máis simple que facer sumas? - interveu o profesor

- Non. Multiplicar, ou restar, é máis difícil -respondeulle o rapaz

- Pero antes de saber sumar, non tes que saber nada? Que necesitas para saber sumar?

- Os números!

- Ben, estamos buscando o máis fundamental. Cales son os números máis simples, aqueles a partir dos que podemos ir construíndo todos os demais?

- O 1, o 2, o 3,... e así. Os números naturais, os positivos.

- E non hai nada máis fundamental aínda que os números?

- Non -foi a nosa resposta.

- Ben. Imaxinade que imos moi atrás no tempo, que pertencemos a unha sociedade moi primitiva, que apenas ten coñecementos pero xa son agricultores e gandeiros. Por suposto, non hai escolas e non coñecen os números pero teñen un rabaño de ovellas que sacan a pastar. Ao cabo do día interésalles saber se deixaron algunha perdida no monte. Como o poden saber?

Despois de algúns intentos e varios silecios, o profesor tivo que continuar.

- Se por cada ovella que sacan da corte colocan unha pedra e van facendo así un montón, cando volvan, poden ilas retirando e, se queda unha, por exemplo, saberán que terán que ir buscar unha ovella perdida no monte. 

- Pero iso é contar

- Non, non contan. Non din, 1, 2, 3,... senón que amontoan unha pedra por cada ovella.A cada ovella asígnanlle unha pedra, nada máis. Acabamos de ver un exemplo de algo máis fundamental que os números. Que son as pedras ou as ovellas? 

Por que poñería isto aquí?

Cómpre contextualizar a escena. Isto sucedeu hai 40 anos, de aí que os alumnos que estabamos nesa aula éramos alumnos da época das chamadas "matemáticas modernas". Todos oíramos falar unha e mil veces dos conxuntos.

- Efectivamente, o rabaño de ovellas forma un conxunto e o montón de pedras forma outro conxunto. Podédesme dar outros exemplos de conxuntos?

Non o lembro ben, pero é seguro que apareceron moitos exemplos tales como o conxunto de alumnos dese grupo, o subconxunto dos que tiñan gafas, o de todos os do insituto,o dos habitantes da vila, o dos coches dos profesores,...

- Todos os conxuntos son finitos, ou pode habelos con infinitos elementos?

- O conxunto dos números 1, 2, 3,.... é infinito. O dos primos, o dos decimais, - interviron varios alumnos

- Entón, para formar un conxunto, todos os elementos que o forman teñen que ter algo en común? Non podo formar un conxunto que teña como elementos un canguro, un triángulo e o planeta Marte?

Parecía haber consenso en que un conxunto podía estar formado por eses elementos, aínda que non tiveran relación entre si. 

- Os conxuntos son máis fundamentais que os números. Sen saber nada de números podemos traballar con conxuntos, tal e como fixemos co conxunto das pedras e o das ovellas. Entón estaría ben saber que é un conxunto, alguén o sabe?

Houbo moitas respostas: "un conxunto de cousas" (que obviamente non serve), "un grupo de cousas" (cando falamos de grupo entendemos que nos estamos a referir a cousas con algunha caracterísica común, e acabamos de ver que podemos formar conxuntos con elementos que non teñan nada en común), "unha colección de cousas" (aquí a obxección é a mesma que no caso anterior, falamos, por exemplo de coleccións de moedas ou de selos, que son todos elementos das mesmas características) "unha agrupación ..." (agrupación é o mesmo que grupo), "consiste en coller as cousas que queiramos..." (pero isto non é unha definición, é unha acción, é coma se dicimos que un cabalo serve para montar e non explicamos que é un animal),.... e así, unha tras outra todas as definicións tiveron algunha obxección por parte do profesor. Chegou un momento en que estaba claro que era o seu turno, el debía darnos a definición de "conxunto" e foi marabilloso: confesounos que tampouco era quen de explicar o que é un "conxunto". Quizais algúns se sentiron decepcionados ou enganados, pero pode ser que alguén sentira que, por primeira vez, estaba facendo matemáticas, pensando seriamente nas matemáticas.

- Os "conxuntos" son obxectos moi abstractos, é moi difícil definilos. Con todo, polos exemplos que foron aparecendo durante a clase vexo que temos unha idea intuitiva do que é un "conxunto" e iso chegaranos. O importante é que, cando traballemos cun conxunto, saibamos en todo momento se un elemento pertence ou non a ese conxunto. Aínda que ningunha das que apareceron é a definición ideal, moitas delas poden servirnos para traballar sen problemas coa teoría de conxuntos. É importante que recoñezamos esa eiva, quizais co tempo cheguedes a saber o porqué. De todas maneiras, insisto, non teremos ningunha dificultade porque vexo que todos temos unha boa idea do que son os conxuntos. Así, podemos copiar o seguinte na libreta:

Un conxunto X é unha colección de cousas ás que chamaremos elementos. Diremos que un elemento x pertence a X se forma parte do conxunto X. Isto escríbese $x\in X$. Se un elemento y está no conxunto X diremos que a non pertence a X. Escríbese $y\notin X$. Os conxuntos representarémolos sempre con letras maíusculas e os elementos con minúsculas.

Por exemplo, describiremos así o conxunto das letras vogais:$V=\{a,e,i,o,u\}=\left\{vogais\right\}$