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
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