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.

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.

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

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

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.

Netminder

Site Admin