Euler's totient/phi function

If gcd(a,n) = 1 and gcd(a-1,n) = 1 then prove that

1 + a + a^2 + a^3 + ... + a^(phi-1) = 0 (mod n)

Where phi = phi(n) is the Euler phi/totient function.

= means "is congruent to"

I can prove this if n is a prime number, but I need the proof for any n > 1.

a and n are integers, of course.
LVL 1
acerolaAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
NetminderConnect With a Mentor Commented:
Closed, 250 points refunded.
Netminder
Site Admin
0
 
bastibartelCommented:
Hi there ?

I don't exactly undertand your notation:
1 + a + a^2 + a^3 + ... + a^(phi-1) = 0 (mod n)

the part w/o (mod n) does not depend on n

Secondly, can you prove it for n=1 ?

Cheers,
Sebastian
0
 
acerolaAuthor Commented:
phi = phi(n) (phi is a function of n)

For n=1 it is trivial, since all numbers are congruent to zero modulus 1.

I have already solved it. The sum is a geometric series. The first element is 1 and the scale facor is a, so:

a^0 + a^1 + a^2 + a^3 + ... + a^(phi-1) = (a^(phi) - 1)/(a - 1)

We know that:

a^(phi(n)) = 1 (mod n)

So:

a^(phi) - 1 = 0 (mod n)
since gcd(a-1,n) = 1, we can divide both sides by (a-1)
(a^(phi) - 1)/(a-1) = 0 (mod n)

That's it. I didn't realize that it was a geometric series. I was trying to solve it using Newton's binomial...
0
 
bastibartelCommented:
*closed* :-)
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.