# Thread: Eulers totient function

1. ## Eulers totient function

Hi,

I need to show that $$11^{40} + 33^{40} + 51^{40} + 97^{40}$$ is 4 in $$Z_{100}$$ using the totient function. The problem as i see it, is that 100 is not a prime number. i could of course go the long way $$(11^{2})^{20} = (21^{2})^{10}$$and so forth but that's a bit tedious...

/Jones

2. Note, $\phi (100) = 40$ thus if $\gcd(a,100) = 1$ then $a^{\phi(100)} = a^{40} \equiv 1 (\bmod 100)$.

Then, $\gcd(11,100) = \gcd(33,100) = \gcd(51,100) = \gcd(97,100) = 1$.

Thus, $11^{40}+33^{40}+51^{40} + 97^{40} \equiv 1+1+1+1 = 4(\bmod 100)$.

3. It doesnt have to be prime if you know the zeta function, the two numbers just have to have a gcd of 1.

4. Originally Posted by ThePerfectHacker
Note, $\phi (100) = 40$ thus if $\gcd(a,100) = 1$ then $a^{\phi(100)} = a^{40} \equiv 1 (\bmod 100)$.

Then, $\gcd(11,100) = \gcd(33,100) = \gcd(51,100) = \gcd(97,100) = 1$.

Thus, $11^{40}+33^{40}+51^{40} + 97^{40} \equiv 1+1+1+1 = 4(\bmod 100)$.
Thank you, how would this be different if we had for example $$25^{40}$$ when the gcd is not 1

5. You would have to treat numbers like 2, 5, 25, 26, ... as special cases and work them out by hand.