Results 1 to 6 of 6

Thread: Proof of congruence result.

  1. #1
    Member
    Joined
    May 2008
    Posts
    140

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by Cairo View Post
    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?

    $\displaystyle (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 $\displaystyle \binom{5^n}{i}$ is divisible by $\displaystyle 5^n\,\,\forall i\geq 1$ (proof...?) , we are then done.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    $\displaystyle \binom{5^n}{i}$ isn't divisible by $\displaystyle 5^n$ for $\displaystyle i=5^n$. But anyway, the congruence is mod $\displaystyle 5^n+1$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by HappyJoe View Post
    $\displaystyle \binom{5^n}{i}$ isn't divisible by $\displaystyle 5^n$ for $\displaystyle i=5^n$. But anyway, the congruence is mod $\displaystyle 5^n+1$.

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

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    140
    Sorry, the congruence is modulo 5^(n+1).

    I've tried using induction to prove the result, but got lost.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Cairo View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 23rd 2010, 07:20 AM
  2. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 22nd 2010, 02:50 PM
  3. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 20th 2010, 12:30 PM
  4. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 5th 2009, 09:34 AM
  5. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 24th 2008, 07:16 AM

Search Tags


/mathhelpforum @mathhelpforum