Question

Find the last two digits of $3^{1000}$ .   How do I know phi(100) = 2^2 * 5^2 *(1- 1/2)* (1-1/5) ???? This appears and feels it has been done out of thin air. Then, Fermitas ?!?

Answer 1

Question asked:

To prove:

$\phi (100)=2^{2}\times 5^{2}\times (1-\frac{1}{2})\times (1-\frac{1}{5})$

Proof:

$\phi (n)$ is the number of positive integers $\leq$ n that are relatively prime to n.

$\phi (n)$ is called Euler's totient.

Example :

$\phi (9)=6,$

   since 1,2,3,4,5,7 and 8 are relatively prime to n.

Formula to find Euler's totient $\phi (n)$ :

Step 1:

Express n in terms of its relatively prime numbers as follows:

$n=P^{^{a}}_{_{1}}\times P^{^{b}}_{_{2}}\times P^{^{c}}_{_{_{3}}}\times ...$

where P₁, P₂, P_{3, ... are prime factors of n.}

_Then,

_{Euler totient} $\phi (n)$ is given by:

$\phi (n)=n\times (1-\frac{1}{P_{_{1}}})\times (1-\frac{1}{P_{2}})\times (1-\frac{1}{P_{_{3}}})\times ...$    (1)

Here,

n = 100

Expressing n in terms of prime factors, we get:

100 = 2² X 5²

Now, applyig formula (1), we get:

$\phi (100)=100\times (1-\frac{1}{2})\times (1-\frac{1}{5})$

i.e.,

$\phi (100)=2^{2}\times 5^{2}\times (1-\frac{1}{2})\times (1-\frac{1}{5})$

This is the required result.