# proof of a corollary to Euler-Fermat theorem

This is an easy consequence of Euler-Fermat theorem:

Let ${d}_{i},{m}_{i}$ be defined as in the parent entry. Then $\mathrm{gcd}(a,{m}_{s})=1$ and Euler’s theorem implies:

$${a}^{\varphi ({m}_{s})}\equiv 1mod{m}_{s}$$ |

Note also that each of ${d}_{s-1},\mathrm{\dots},{d}_{0}$ divides $a$, so $\prod {d}_{i}$ divides ${a}^{s}$, so $\prod {d}_{i}$ divides ${a}^{\varphi ({m}_{s})+s}-{a}^{s}$. Also, $\mathrm{gcd}(\prod {d}_{i},{m}_{s})=1$ and ${m}_{s}\cdot \prod {d}_{i}=m$. Therefore:

$${a}^{\varphi ({m}_{s})+s}\equiv {a}^{s}modm$$ |

which is what the corollary claimed.

Title | proof of a corollary to Euler-Fermat theorem |
---|---|

Canonical name | ProofOfACorollaryToEulerFermatTheorem |

Date of creation | 2013-03-22 14:23:20 |

Last modified on | 2013-03-22 14:23:20 |

Owner | alozano (2414) |

Last modified by | alozano (2414) |

Numerical id | 5 |

Author | alozano (2414) |

Entry type | Proof |

Classification | msc 11-00 |