3
$\begingroup$

How can I prove that:

$ (g^b \bmod{p})^a \bmod{p} = (g^a \bmod{p})^b \bmod{p}$

where p is a prime number, g is a primitive root of p, and a and b are integers.

While I understand that $(g^b)^a = (g^a)^b$ , I cannot figure out how to deal with the mod functions...

1 Answers 1

4

You can expand $(g^b \bmod p)$ as $g^b + pK$ by the definition of $\text{mod}$.

Then $(g^b + pK)^a = g^{ab} + \binom{a}{1}g^{(a-1)b}pK + \ldots + (pK)^a$

Since all but the first of the terms in the binomial expansion contain a factor of $p$, $(g^b \bmod p)^a \equiv g^{ab} \pmod p$

  • 0
    How g^b mod p = g^b + pK?2014-07-25
  • 1
    @codeomnitrix, $a \equiv b\pmod c$ is a shorthand notation for $\exists k : a - b = ck$2014-07-30
  • 0
    are u sure about (g^b mod p)^a ≡ g^(ab) mod p? lets try with g = 2, a = 1, b = 3, p== 11 (2^3 mod 11) ^ 5 != 2 ^ (5*3) mod 11 as obviously 8^5 != 2^15 mod 112016-06-30
  • 0
    @DmitryMartovoi, I have no idea where your 5 came from, but yes, I am sure because I am completely convinced by the proof in the answer. I am also completely convinced that "*8^5 != 2^15 mod 11*" is obviously false: $8^5 = 2^{15}$ so there's no need to even compute the values mod 11.2016-06-30
  • 0
    @PeterTaylor pardon, there is a = 5 (not 1)2016-06-30
  • 0
    let $(g^b \mod p)=10 \mod 3=1$, what's $pK$ in this case? (this would be $10+3K$, so $K=-3$). So $K \in \mathbf{Z}$?2018-05-02
  • 0
    I think you are missing $\mod p$. i.e. $(g^b \mod p)^a \mod p \equiv g^{ab} \mod p$2018-05-02
  • 1
    @isquared-KeepitReal, yes, $K \in \mathbb{Z}$. I don't agree that I'm missing $\bmod p$ because that's $\equiv$ rather than $=$, but it would have been better to use $\pmod p$ rather than $\bmod p$ at the end of the last line. Possibly my TeX knowledge was deficient back in 2011. I have edited in the improvement.2018-05-02
  • 0
    @PeterTaylor yes, you are right.2018-05-02