# computation of powers using Fermat’s little theorem

A straightforward application of Fermat’s theorem consists of rewriting the power of an integer mod $n$. Suppose we have $x\equiv {a}^{b}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ with $a\in \mathcal{U}(n)$. Then, by Fermat’s theorem we have

$${a}^{\varphi (n)}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn),$$ |

so

$$x\equiv {a}^{b}{(1)}^{k}\equiv {a}^{b}{({a}^{\varphi (n)})}^{k}\equiv {a}^{b+k\varphi (n)}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$$ |

for any integer $k$. This means we can replace $b$ by any integer congruent^{} to it mod $\varphi (n)$. In particular we have

$$x\equiv {a}^{b\%\varphi (n)}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$$ |

where $b\%\varphi (n)$ denotes the remainder of $b$ upon division by $\varphi (n)$.

This can be used to make the computation of large powers easier. It also allows one to find an easy to compute inverse to ${x}^{b}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ whenever $b\in \mathcal{U}(n)$. In fact, this is just ${x}^{{b}^{-1}}$ where ${b}^{-1}$ is an inverse to $b$ mod $\varphi (n)$. This forms the base of the RSA cryptosystem where a message $x$ is encrypted by raising it to the $b$th power, giving ${x}^{b}$, and is decrypted by raising it to the ${b}^{-1}$th power, giving

$${({x}^{b})}^{{b}^{-1}}\equiv {x}^{b{b}^{-1}},$$ |

which, by the above argument, is just

$${x}^{b{b}^{-1}\%\varphi (n)}\equiv x,$$ |

the original message!

Title | computation of powers using Fermat’s little theorem |
---|---|

Canonical name | ComputationOfPowersUsingFermatsLittleTheorem |

Date of creation | 2013-03-22 13:17:42 |

Last modified on | 2013-03-22 13:17:42 |

Owner | basseykay (877) |

Last modified by | basseykay (877) |

Numerical id | 5 |

Author | basseykay (877) |

Entry type | Example |

Classification | msc 11-00 |