Science:Math Exam Resources/Courses/MATH312/December 2010/Question 08/Solution 1

By Fermat's Little Theorem, we have that

$\displaystyle x^{52578}\equiv 1\mod {52579}$.

The given problem tells us that

$\displaystyle x^{5}\equiv 1\mod {52579}$

Using the Euclidean Algorithm, we can find integers a and b such that

$\displaystyle 5a+52578b=\gcd(52578,5)=1$.

Thus we have that

$\displaystyle x\equiv x^{5a+52578b}\equiv x^{5a}x^{52578b}\equiv (x^{5})^{a}(x^{52578})^{b}\equiv 1\mod {52579}$

and this completes the proof. The other property that we used about 52579 is that 52578 and 5 are coprime.