1

I know this one's true, but I can't prove it. I've tried everything.

$$a^{b\bmod{(\theta(m))}}\bmod(m)=a^b\bmod(m)$$

Multiply the exponent with $m-1$ (assume $m$ is prime, it doesn't matter anymore) and it's opposite, but opposite where? the exponent is not under $\bmod m$. Why is this claim correct?

N. F. Taussig
  • 76,571
itaymeller
  • 41
  • We will want some conditions on $a$ or on $m$ or both. For example it is correct if $\gcd(a,m)=1$ (Euler's Theorem). – André Nicolas Feb 17 '15 at 17:07
  • Great! gcd(a,m) = 1! – itaymeller Feb 17 '15 at 17:09
  • Have you got it then? It comes down to writing $b=q\varphi(m)+r$, where $r$ (the remainder) is what's called $b\bmod{\varphi(m)}$ in your question. Then we use (Euler's Theorem) the fact that $a^{\varphi(m)}\equiv 1\pmod{m}$. – André Nicolas Feb 17 '15 at 17:13
  • How did I miss it.... I was solving a bigger problem that led me to this one: http://math.stackexchange.com/questions/1151816/modular-arithmetic-power - If you don't me asking, what does tobias means when he says if b is coprime to 2p? what if he isn't? – itaymeller Feb 17 '15 at 17:20
  • Recall that because of the Sophie Germain condition, $2p+1$ is prime, and therefore $\varphi(2p+1)=2p$. So to apply Euler's Theorem to $b^{c^d}$ we want $\gcd(b,\varphi(2p+1))=1$, that is, $\gcd(b,2p)=1$. I have not tracked down what happens in the other problem if this condition on $b$ is violated. – André Nicolas Feb 17 '15 at 17:35
  • Thanks alot man. This is exactly what i'm trying to solve. If it is divisible by both 2 and p, it is ofcourse 0, and its easy. If its coprime, I can apply that again. If it is divisible only by p or only by 2, I can't seem to figure what to do. – itaymeller Feb 17 '15 at 17:38

0 Answers0