Eulers totient function

**Jones** · January 10th 2009, 03:15 PM

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

**ThePerfectHacker** · January 10th 2009, 03:29 PM

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)$ .

**person8901** · January 11th 2009, 04:19 PM

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

**Jones** · January 14th 2009, 06:06 PM

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 [Math]25^{40} [/tex] when the gcd is not 1

**chiph588@** · January 14th 2009, 07:10 PM

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

Thread: Eulers totient function

LinkBack

Thread Tools

Display

Eulers totient function

Similar Math Help Forum Discussions

totient function

Eulers Totient

Totient Function

Euler totient function

Eulers totient function

Search Tags