1. ## Eulers totient function

Hi,

I need to show that [Math]11^{40} + 33^{40} + 51^{40} + 97^{40}[/tex] is 4 in [Math]Z_{100}[/tex] 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 [Math] (11^{2})^{20} = (21^{2})^{10} [/tex]and so forth but that's a bit tedious...

/Jones

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

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

Thus, $\displaystyle 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, $\displaystyle \phi (100) = 40$ thus if $\displaystyle \gcd(a,100) = 1$ then $\displaystyle a^{\phi(100)} = a^{40} \equiv 1 (\bmod 100)$.

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

Thus, $\displaystyle 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 [Math]25^{40} [/tex] 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.