Pregunta básica sobre mod

Question

Estoy teniendo un momento difícil entender por qué es igual a $(a^x \bmod p)^y \bmod p$ $a^{xy}\bmod p$.
¿Tiene esto una prueba matemática? Aconseje por favor.

Answer 1

Normalmente es más sencillo trabajar con congruencias en lugar de binario $\bmod$ operador, y luego ir a tot el operador binario al final.

Dado un entero $n$, podemos decir que $a\equiv b\pmod{n}$ ("$a$ es congruente a $b$ modulo $n$") si y sólo si $n$ divide $b-a$. Es fácil mostrar que "congruentes modulo $n$" es una relación de equivalencia; es decir, $a\equiv a \pmod{n}$ por cada $a$; si $a\equiv b\pmod{n}$$b\equiv a\pmod{n}$; y si $a\equiv b\pmod{n}$$b\equiv c\pmod{n}$,$a\equiv c\pmod{n}$.

La proposición. Los siguientes son equivalentes:

1. $a\equiv b\pmod{n}$.
2. $n$ divide $a-b$.
3. $a = b+kn$ para algunos entero $k$.
4. $a$ $b$ tienen el mismo resto al dividir por $n$.

Prueba. (1)$\Leftrightarrow$(2): Esta es la definición.

(2)$\Rightarrow$(3): Desde $n$ divide $a-b$ existe $k$ tal que $nk = a-b$; por lo tanto $a=b+nk$, como se reivindica.

(3)$\Rightarrow$(4). Deje $b=qn+r$,$0\leq r\lt |n|$. A continuación,$a=b+kn = qn+r+kn = (q+k)n+r$,$0\leq r\lt |n|$. Por la singularidad de la cláusula del algoritmo de la división, se deduce que el $r$ es también el resto de $a$ cuando se divide por $n$.

(4)$\Rightarrow$(2). Si $a=qn+r$, $b=pn+r$, $0\leq r\lt|n|$, a continuación,$a-b = (q-p)n$, lo $n$ divide $a-b$. QED

La condición (4) nos dice que si tenemos una igualdad entre expresiones que tratan de los restos de los números, que son el equivalente a los correspondientes de la congruencia. En su pregunta, esto significa que la deseada igualdad ocurre si y sólo si $a^{xy}$ es congruente a $(a^x)^y$ modulo $n$, el cual tiene porque, de hecho son iguales. Pero para obtener más detenidamente:

Corolario. Deje $n$ ser un entero positivo. Luego cada entero $a$ es congruente modulo $n$ a uno y sólo uno de $0$, $1$, $2,\ldots,n-1$.

Prueba. Dividiendo $a$ $n$ hemos $a = qn + r$, $0\leq r\lt n$. A continuación,$a\equiv r\pmod{n}$; por lo que cada entero es congruente con al menos uno de $0,\ldots,n-1$. La unicidad, deje $i,j$ ser enteros, $0\leq i,j\leq n-1$ tal que $i\equiv j\pmod{n}$. Sin pérdida de generalidad, supongamos $i\leq j$. A continuación,$0\leq j-i\lt n$, e $n$ divide $j-i$; la única posibilidad es $j-i=0$, lo $j=i$. QED

Definición. Deje $a$ ser un número entero, $n$ un entero positivo. Definimos $a\bmod n$ ("$a$ mod $n$") a ser el único número entero no negativo $i$, $0\leq i\lt n$, tal que $a\equiv i\pmod{n}$. Es decir, $a\equiv (a\bmod n)\pmod{n}$, e $0\leq (a\bmod n)\lt n$.

Teorema. Si $a\equiv b\pmod{n}$$c\equiv d\pmod{n}$,$a+c\equiv b+d\pmod{n}$$ac\equiv bd\pmod{n}$.

Prueba. Nuestra hipótesis se que $n$ divide tanto a a$a-b$$c-d$. Por lo tanto, se divide a su suma, $(a+c)-(b+d)$ (lo que implica,$a+c\equiv b+d\pmod{n}$); también se divide $(a-b)c$$b(c-d)$; la adición de estos dos últimos le da a ese $ac-bd$ es un múltiplo de a $n$, lo $ac\equiv bd\pmod{n}$. QED

Corolario. Si $a\equiv b\pmod{n}$, e $r$ es un entero positivo, entonces $a^r\equiv b^r\pmod{n}$.

Ahora considere el$(a^x)^y$$a^{xy}$.

Tenga en cuenta que $(a^x)^y = a^{xy}$, lo $(a^x)^y\equiv a^{xy}\pmod{n}$. También, desde la $a^x \equiv (a^x\bmod n)\pmod{n}$,$(a^x)^y \equiv (a^x\bmod n)^y\pmod{n}$. Desde $a^{xy}\equiv (a^x)^y\pmod{n}$, e $(a^x)^y\equiv (a^x\bmod n)^y\pmod{n}$,$a^{xy}\equiv (a^x\bmod n)^y\pmod{n}$.

Y desde $a^{xy}\equiv (a^x\bmod n)^y\pmod{n}$, $a^{xy}$ $(a^x\bmod n)^y$ tienen el mismo resto al dividir por $n$; es decir, $$a^{xy}\bmod n = (a^x\bmod n)^y \bmod n,$$ como se desee.

Answer 2

Ya que este se ha migrado desde ENTONCES, sospecho que por "$n\bmod m$", significa que el resto al $n$ se divide por $m$, normalmente con $0\le n<m$ (posiblemente negativo si $n<0$). En esta interpretación, vamos a llamar a $n=a^x\bmod p$, lo que significa que $a^x=n+kp$ o $n=a^x-kp$ para algunos entero $k$ e con $0\le n<p$. Ahora (suponiendo $y$ es un número entero), cuando tome $(a^x\bmod p)^y=n^y=(a^x-kp)^y$ y ampliar el extremo derecho de la expresión utilizando el teorema del binomio, obtendrá $a^{xy}$, además de un montón de términos que tienen un factor de $p$ y por lo tanto no afectan $(a^x\bmod p)^y\bmod p$, por lo que su resultado final será igual a $a^{xy}\bmod p$.

Answer 3

Debe ser capaz de demostrar de primeros principios que $(a\mod p)(b \mod p) \mod p = (ab)\mod p$ % enteros todos $a, b$. Ahora puede probar su estado de cuenta por inducción en $y$.

Answer 4

Tienes que demostrar es que si $a \equiv b \mod n$ y $a^m \equiv b^m \mod n$.

Mientras que esto sigue por la inducción de la regla de producto como mentined arriba, usted puede también probarlo directamente de la siguiente manera:

En $n$ divide $a-b$, a continuación, divide también a $n$

$$(a-b)[a^{n-1}+a^{n-2}b+...+b^{n-1}]= a^n-b^n \,.$$

Answer 5

La prueba es más clara utilizando congruencias vs formas normales (menos residuos). Para traducir entre la nota de dos idiomas que $\rm\ A\ mod\ m\ =\ a\ mod\ m\ \iff\ A\equiv a\ \ (mod\ m)\:,\:$ es decir $\rm\ m\ |\ A-a\:.\:$ ahora el resultado buscado sigue por la inducción después de aplicar la siguiente ubicua

Regla de congruencia producto $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$

Prueba $\rm\:\ \ m\: |\: A-a,\ B-b\:\ \Rightarrow\:\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $