Aritmética modular

La aritmética modular es la aritmética que surge cuando ordenamos los enteros en espiral en vez de en línea recta. Es lo que usamos en los relojes, cuando decimos que las 15 horas son las 3 de la tarde. Matemáticamente,

\[ 15 \equiv 3 \pmod {12} \]

Es decir, el 15 y el 3 caen en la misma posición cuando contamos de 12 en 12.

Pequeño Teorema de Fermat

Pequeño Teorema de Fermat

Sean \(a\) un entero y \(p\) un número primo. Entonces

\[ a^p \equiv a \pmod p \]

De forma equivalente, cuando \(a\) y \(p\) son coprimos,

\[ a^{p-1} \equiv 1 \pmod p \]

Teorema de Euler

Este teorema es una generalización del PTF. Para \(p\) primo, \(\phi(p) = p-1\), ya que todos los enteros positivos menores que \(p\) son coprimos con \(p\).

Teorema de Euler

Si \(a\) y \(n\) son enteros positivos coprimos (es decir, tales que \(\text{mcd}(a, n)=1\)), entonces

\[ a^{\phi(n)} \equiv 1 \pmod n \]

Problemas

Múltiplos de 5

¿Para qué valores \(x\) de la base el número \(532_x\) es múltiplo de \(5\)?

Potencias de 2

Halla para qué valores de \(n\) el número \(2^n-1\) es múltiplo de

1. \(3\)
2. \(5\)
3. \(7\)