(a^k(p-1)+ b) mod(p) here p is a prime number and a,b,k is an integer greater than 1 and a not divisble by p. Is this value same as (a^b)mod(p)? [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

According to Fermat's Little theorem a^(p-1) mod(p) is 1. So a^k(p-1) mod(p)will also be 1 by splitting into k parts and apply modulus independently we get '1'. Am I missing something?

Answer 1

We know,

((a mod N) * (b mod N)) mod N = (a*b) mod N

a^(p-1) mod p = 1

Thus

( a^(p-1) * a^(p-1) * a^(p-1) * ... * a^(p-1) ) mod p = ( 1 * 1 * 1 * ... * 1) mod p = 1

Tada.

Answer 2

You are right. In general, the equation holds as a^(k*phi(n)+b) is congruent with a^b modulo n where phi denotes the Euler-phi function, and a is relative prime to n.