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 $\gcd(a,m_{s})=1$ and Euler’s theorem implies:

 $a^{\phi(m_{s})}\equiv 1\mod m_{s}$

Note also that each of $d_{s-1},\ldots,d_{0}$ divides $a$, so $\prod d_{i}$ divides $a^{s}$, so $\prod d_{i}$ divides $a^{\phi(m_{s})+s}-a^{s}$. Also, $\gcd(\prod d_{i},m_{s})=1$ and $m_{s}\cdot\prod d_{i}=m$. Therefore:

 $a^{\phi(m_{s})+s}\equiv a^{s}\mod m$

which is what the corollary claimed.

Title proof of a corollary to Euler-Fermat theorem ProofOfACorollaryToEulerFermatTheorem 2013-03-22 14:23:20 2013-03-22 14:23:20 alozano (2414) alozano (2414) 5 alozano (2414) Proof msc 11-00