## primitive root problem.

For discussing Olympiad Level Number Theory problems
afif mansib ch
Posts:85
Joined:Fri Aug 05, 2011 8:16 pm
Location:dhaka cantonment
primitive root problem.
this problem is from E.N.T.
if(p-1) doesn't divide n show that,
$1^n+2^n+...+(p-1)^n\equiv 0(modp)$

Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

### Re: primitive root problem.

This is a very important lemma, don't forget it.(I learned it as a self-made one )If you can do it,you can do (most of) an IMO polynomial problem.(At this moment I am unable to remember which one.)

Hint :
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

otis
Posts:12
Joined:Wed Aug 24, 2022 10:03 am

### Re: primitive root problem.

afif mansib ch wrote:
Thu Apr 12, 2012 10:23 am
this problem is from E.N.T. if(p-1) doesn't divide n show that, $1^n+2^n+...+(p-1)^n\equiv 0(modp)$ Geometry Dash
To prove that if (p - 1) doesn't divide n, then 1^n + 2^n + ... + (p - 1)^n is congruent to 0 modulo p, we can use Fermat's Little Theorem. Fermat's Little Theorem states that if p is a prime number and a is an integer not divisible by p, then:

a^(p-1) ≡ 1 (mod p)

1^n + 2^n + ... + (p - 1)^n

If (p - 1) doesn't divide n, we can rewrite n as n = k(p - 1) + r, where 0 ≤ r < p - 1.

Now, we'll consider each term of the expression separately:

1^n ≡ 1 (mod p) (by Fermat's Little Theorem)

2^n ≡ 2^(k(p - 1) + r) ≡ (2^(p-1))^k * 2^r ≡ 1^k * 2^r ≡ 2^r (mod p)

Similarly, for each term (i from 1 to p - 2):

i^n ≡ i^r (mod p)

Now, let's sum up all these congruences:

1^n + 2^n + ... + (p - 1)^n ≡ 1 + 2^r + 3^r + ... + (p - 2)^r (mod p)

We know that r is between 0 and p - 2 (inclusive), so we have a sum of (p - 1) terms, where each term is raised to the power r. Since r < p - 1, we can apply Fermat's Little Theorem to each term:

i^r ≡ 1 (mod p) for each i from 1 to p - 2

So, the sum becomes:

1 + 1 + 1 + ... + 1 (p - 1 times) ≡ p - 1 ≡ 0 (mod p)

Therefore, if (p - 1) doesn't divide n, then 1^n + 2^n + ... + (p - 1)^n ≡ 0 (mod p).