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)\]

## primitive root problem.

- afif mansib ch
**Posts:**85**Joined:**Fri Aug 05, 2011 8:16 pm**Location:**dhaka cantonment

- Phlembac Adib Hasan
**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 :

Hint :

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

### Re: primitive root problem.

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:afif mansib ch wrote: ↑Thu Apr 12, 2012 10:23 amthis 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

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

Now, let's consider your expression:

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