I have found that the answer to my question is

a^((b^c) % prime — 1) % prime

But I don't know a proof, can anyone tell me the proof or give me a tutorial to read it. Thanks

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

I have found that the answer to my question is

a^((b^c) % prime — 1) % prime

But I don't know a proof, can anyone tell me the proof or give me a tutorial to read it. Thanks

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 16:13:08 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Fermat's little theorem states that for a prime $$$p$$$ and any integer $$$a$$$ such that $$$0 < a < p$$$,

In other words, the powers of $$$a$$$ modulo $$$p$$$ repeat with a period of $$$p-1$$$.

This is further generalized by Euler's theorem which implies the powers of $$$a$$$ repeat with a period of $$$p-1$$$. This can be even further generalized with Lagrange's theorem for groups.

Yeah, Fermat's Little Theorem basically finishes off this problem, since we have a period p-1, now all we need to do is find $$$b^c \mod p-1$$$ (just use binary exponentiation) and then find $$$a^{(\text{this number})} \mod p$$$. One more generalized formula is Euler's Totient Theorem, which states that $$$a^{\phi(x)} \equiv 1$$$ $$$(\text{mod }x)$$$ where $$$\gcd(a, x)=1$$$.

https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/

You can use above link for better understanding.