Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Jun 27 '11 at 14:22

This question came from our site for professional and enthusiast programmers.

    
Related: math.stackexchange.com/questions/5366 –  Zev Chonoles Jun 27 '11 at 14:24
1  
@user817536: I added in the $p$ inside the parentheses. Please make sure this is what you meant. –  Ross Millikan Jun 27 '11 at 14:38
1  
@Ross: Given the original text of the question (in the revision history), I think that's what was intended. –  Isaac Jun 27 '11 at 14:40

5 Answers 5

up vote 6 down vote accepted

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<m$ (possibly negative if $n<0$). In this interpretation, let's call $n=a^x\bmod p$, which means that $a^x=n+kp$ or $n=a^x-kp$ for some integer $k$ and with $0\le n<p$. 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$.

share|improve this answer
    
What other interpretations for `n mod m' are there? (I am interested, not being sarcastic.) –  user1729 Jun 27 '11 at 14:45
2  
@Swlabr: I think it's much more common to write something like $(a\equiv b)\mod m$ (read "$a$ is congruent to $b$, mod $m$"), which is equivalent to $m|(a-b)$ (read "$a-b$ is divisible by $m$"). This isn't wholly different from the interpretation I describe for "$n\mod m$" in my answer, but I typically don't see "mod" used in a purely-mathematical context as a binary operator that returns the remainder. –  Isaac Jun 27 '11 at 14:49
2  
@Isaac: I changed the \mod to \bmod, since that is the version used when we are using it as a binary operator, a common practice in Computer Science. In principle it improves the spacing. And it actually does in real LaTeX, though the results here are mixed at best. MathJax, at least on my browser, has many spacing weaknesses. –  André Nicolas Jun 27 '11 at 16:28
1  
@Isaac: Yes. I don't know whether that behavior is defined by the language or the HW, though? At least Intel x86 family of processors took me by surprise here once :-) But your point stands, mod behaves unexpectedly with negative numbers. Why can't the programmers just give up on this, and agree that algebraists' notation is the only way, why, why, why? A pet peeve of mine :-) –  Jyrki Lahtonen Jun 28 '11 at 5:02
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, but sometimes it's implementation-specific. The Wikipedia article on the modulo operation is a good source for what symbol and which definition is used in each of a variety of languages. –  Isaac Jun 28 '11 at 5:12

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:

  1. $a\equiv b\pmod{n}$.
  2. $n$ divides $a-b$.
  3. $a = b+kn$ for some integer $k$.
  4. $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.

share|improve this answer
    
I've added this question to my favorites just for this explanation. Thank you for working through it in detail. –  ttt Jul 7 '11 at 15:50

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$.

share|improve this answer
2  
In 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. –  André Nicolas Jun 27 '11 at 17:00

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 \,.$$

share|improve this answer
    
The point of using congruences is that we can reuse our arithmetical intuition to make such inferences more evident. Namely, here it's the triviality $\ a\equiv b\ \Rightarrow\ a^n\equiv b^n\:,\ $ which is simply a special case of the congruence product rule. –  Bill Dubuque Jun 27 '11 at 18:12
    
I agree, but to formally prove this trivial implication one usually uses induction, which makes the proof a little more complicated than it needs. Also note that the inductive step is exactly the cancelation in the above telescopic sum. IMO it depends to whom the "proof" is addressed, if it is towards a mathematician/math student yes the product rule is the better approach...... Also I always find it easier to explain to a non-mathematician the product rule the following way: $a\equiv b \mod n \Rightarrow ax \equiv bx \mod n$... –  N. S. Jun 27 '11 at 18:52
    
Cont.... Then if $ a\equiv b$ and $c \equiv d$ we have $ac \equiv bc$ and $cb \equiv db$.... It is exactly the same proof, but more intuitive to a non-mathematician IMO :) –  N. S. Jun 27 '11 at 18:58
    
But 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. –  Bill Dubuque Jun 27 '11 at 19:54

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 $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.