# Thread: Proof of congruence result.

1. ## Proof of congruence result.

How do I prove that

(5k+1)^5^n is congruent to 1 (mod 5^n+1) ?

Can I deduce from this result that no number congruent to 1 mod 5 is a primitive root mod 5^m, for any m greater than or equal to 1?

2. Originally Posted by Cairo
How do I prove that

(5k+1)^5^n is congruent to 1 (mod 5^n+1) ?

Can I deduce from this result that no number congruent to 1 mod 5 is a primitive root mod 5^m, for any m greater than or equal to 1?

$(5k+1)^{5^n}=\sum\limits_{i=0}^{5^n}\binom{5^n}{i} (5k)^i=1+\sum\limits_{i=1}^{5^n}\binom{5^n}{i}(5k) ^i$

and as $\binom{5^n}{i}$ is divisible by $5^n\,\,\forall i\geq 1$ (proof...?) , we are then done.

Tonio

3. $\binom{5^n}{i}$ isn't divisible by $5^n$ for $i=5^n$. But anyway, the congruence is mod $5^n+1$.

4. Originally Posted by HappyJoe
$\binom{5^n}{i}$ isn't divisible by $5^n$ for $i=5^n$. But anyway, the congruence is mod $5^n+1$.

Of course: the sum should have been split into three parts: for $i=0\,,\,i=5^n\,,\,1\leq i\leq 5^n-1$

Tonio

5. Sorry, the congruence is modulo 5^(n+1).

I've tried using induction to prove the result, but got lost.

6. Originally Posted by Cairo
Sorry, the congruence is modulo 5^(n+1).

I've tried using induction to prove the result, but got lost.
Tonio's post still applies.