I'm having a tough time understanding why $(a^x \bmod p)^y \bmod p$ is equal to $a^{xy}\bmod p$.
Does this have a mathematical proof? Please advise.
Basic question about mod
-
1@Ross: Given the original text of the question (in the revision history), I think that's what was intended. – 2019-01-28
5 Answers
The proof is clearer using congruences vs. normal forms (least remainders). To translate between the two languages note that $\rm\ A\ mod\ m\ =\ a\ mod\ m\ \iff\ A\equiv a\ \ (mod\ m)\:,\:$ i.e. $\rm\ m\ |\ A-a\:.\:$ Now the sought result follows by induction after applying the following ubiquitous
Congruence Product Rule $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$
Proof $\rm\:\ \ m\: |\: A-a,\ B-b\:\ \Rightarrow\:\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $
It's usually simpler to work with congruences rather than the binary $\bmod$ operator, and then go tot he binary operator at the end.
Given an integer $n$, we say that $a\equiv b\pmod{n}$ ("$a$ is congruent to $b$ modulo $n$") if and only if $n$ divides $b-a$. It is easy to show that "congruent modulo $n$" is an equivalence relation; that is, $a\equiv a \pmod{n}$ for every $a$; if $a\equiv b\pmod{n}$ then $b\equiv a\pmod{n}$; and if $a\equiv b\pmod{n}$ and $b\equiv c\pmod{n}$, then $a\equiv c\pmod{n}$.
Proposition. The following are equivalent:
- $a\equiv b\pmod{n}$.
- $n$ divides $a-b$.
- $a = b+kn$ for some integer $k$.
- $a$ and $b$ have the same remainder when divided by $n$.
Proof. (1)$\Leftrightarrow$(2): This is the definition.
(2)$\Rightarrow$(3): Since $n$ divides $a-b$, there exists $k$ such that $nk = a-b$; hence $a=b+nk$, as claimed.
(3)$\Rightarrow$(4). Let $b=qn+r$, with $0\leq r\lt |n|$. Then $a=b+kn = qn+r+kn = (q+k)n+r$, with $0\leq r\lt |n|$. By the uniqueness clause of the division algorithm, it follows that $r$ is also the remainder of $a$ when divided by $n$.
(4)$\Rightarrow$(2). If $a=qn+r$, $b=pn+r$, $0\leq r\lt|n|$, then $a-b = (q-p)n$, so $n$ divides $a-b$. QED
Condition (4) tells you that if you have an equality between expressions involving remainders of numbers, they are equivalent to the corresponding congruence. In your question, this means that the desired equality holds if and only if $a^{xy}$ is congruent to $(a^x)^y$ modulo $n$, which holds because they are in fact equal. But to get it more carefully:
Corollary. Let $n$ be a positive integer. Then every integer $a$ is congruent modulo $n$ to one and only one of $0$, $1$, $2,\ldots,n-1$.
Proof. Dividing $a$ by $n$ we have $a = qn + r$, $0\leq r\lt n$. Then $a\equiv r\pmod{n}$; so every integer is congruent to at least one of $0,\ldots,n-1$. For uniqueness, let $i,j$ be integers, $0\leq i,j\leq n-1$ such that $i\equiv j\pmod{n}$. Without loss of generality, assume $i\leq j$. Then $0\leq j-i\lt n$, and $n$ divides $j-i$; the only possibility is for $j-i=0$, so $j=i$. QED
Definition. Let $a$ be an integer, $n$ a positive integer. We define $a\bmod n$ ("$a$ mod $n$") to be the unique nonnegative integer $i$, $0\leq i\lt n$, such that $a\equiv i\pmod{n}$. That is, $a\equiv (a\bmod n)\pmod{n}$, and $0\leq (a\bmod n)\lt n$.
Theorem. If $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then $a+c\equiv b+d\pmod{n}$ and $ac\equiv bd\pmod{n}$.
Proof. Our hypothesis are that $n$ divides both $a-b$ and $c-d$. Therefore, it divides their sum, $(a+c)-(b+d)$ (which implies $a+c\equiv b+d\pmod{n}$); it also divides $(a-b)c$ and $b(c-d)$; adding these latter two gives that $ac-bd$ is a multiple of $n$, so $ac\equiv bd\pmod{n}$. QED
Corollary. If $a\equiv b\pmod{n}$, and $r$ is a positive integer, then $a^r\equiv b^r\pmod{n}$.
Now consider $(a^x)^y$ and $a^{xy}$.
Note that $(a^x)^y = a^{xy}$, so $(a^x)^y\equiv a^{xy}\pmod{n}$. Also, since $a^x \equiv (a^x\bmod n)\pmod{n}$, then $(a^x)^y \equiv (a^x\bmod n)^y\pmod{n}$. Since $a^{xy}\equiv (a^x)^y\pmod{n}$, and $(a^x)^y\equiv (a^x\bmod n)^y\pmod{n}$, then $a^{xy}\equiv (a^x\bmod n)^y\pmod{n}$.
And since $a^{xy}\equiv (a^x\bmod n)^y\pmod{n}$, then $a^{xy}$ and $(a^x\bmod n)^y$ have the same remainder when divided by $n$; that is, $a^{xy}\bmod n = (a^x\bmod n)^y \bmod n,$ as desired.
-
0See also [here](http://math.stackexchange.com/a/614944/242) for more on the difference between mod as a binary operator vs. ternary congruence. – 2015-03-02
Since this was migrated from SO, I suspect that by "$n\bmod m$", you mean the remainder when $n$ is divided by $m$, typically with $0\le n . Now (assuming $y$ is an integer), when you take $(a^x\bmod p)^y=n^y=(a^x-kp)^y$ and expand the rightmost expression using the binomial theorem, you'll get $a^{xy}$ plus a whole bunch of terms that have a factor of $p$ and thus don't affect $(a^x\bmod p)^y\bmod p$, so that your end result will be equal to $a^{xy}\bmod p$.
-
1@Jyrki: I have mixed feelings about the notation and terminology, having done lots of both math and programming. As to the issue of how it's defined on the programming side, it can be language specific, as [C99 and its derivatives, including Objective-C, define $a\%b$ with a<0 to be negative](http://stackoverflow.com/questions/2430817#2430817), but sometimes it's implementation-specific. [The Wikipedia article on the modulo operation](http://en.wikipedia.org/wiki/Modulo_operation) is$a$good source for what symbol and which definition is used in each of a variety of languages. – 2011-06-28
You should be able to prove from first principles that $(a\mod p)(b \mod p) \mod p = (ab)\mod p$ for all integers $a, b$. Now you can prove your statement by induction on $y$.
-
2In the current context, this is absolutely the right approach, even though translating the problem into language that we mathematicians are more comfortable with, and then translating back, certainly works. – 2011-06-27
All you need to prove is that if $a \equiv b \mod n$ then $a^m \equiv b^m \mod n$.
While this follows by induction from the product rule as mentined above, you can also prove it directly the following way:
In $n$ divides $a-b$, then $n$ also divides
$(a-b)[a^{n-1}+a^{n-2}b+...+b^{n-1}]= a^n-b^n \,.$
-
0But the inductive step for $\ a-b\ |\ a^n - b^n\ $ is not as evident as that for $\ a\equiv b\ \Rightarrow\ a^n\equiv b^n\ $. Using congruences has the effect of normalising the induction step to an obvious form, here an instance of the product rule. It converts a statement involving divisibility *relations* to a statement involving arithmetical (ring) *operations* - permitting us to use our well-practiced arithmetical skills. – 2011-06-27