Results 1 to 7 of 7

Math Help - help with modular congruence

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    7

    help with modular congruence

    I apologize if this isn't advanced enough for this forum, but I'm not sure it belongs in pre-university algebra help either...

    ---

    I don't even know where to begin this problem... any suggestions?

    Find (modulo 7) from k=1->300.

    I know for any numbers k of the form 7n k^k reduces to zero, 7n+1 reduces to 1, and 7n-1 forms an alternating sequence of 1 and -1. Beyond that I have no ideas. Thoughts?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by coatesdr View Post
    I apologize if this isn't advanced enough for this forum, but I'm not sure it belongs in pre-university algebra help either...

    ---

    I don't even know where to begin this problem... any suggestions?

    Find (modulo 7) from k=1->300.

    I know for any numbers k of the form 7n k^k reduces to zero, 7n+1 reduces to 1, and 7n-1 forms an alternating sequence of 1 and -1. Beyond that I have no ideas. Thoughts?
    you should've posted your question in the "number theory" subforum not in here. i'll still answer your question only because it's not a bad question:

    first of all note that if p > 2 is a prime number and 1 < j < p, then S(j)=\sum_{r=0}^{p-2} j^r \equiv 0 \mod p. the reason is that (j-1)S(j) \equiv 0 \mod p, because j^{p-1} \equiv 1 \mod p.

    so, if s \geq 0 is an integer, then \sum_{r=0}^{p-2} j^{r+s} \equiv 0 \mod p. use this result to prove that \sum_{r=0}^{(p-1)p} j^r \equiv j^{p-1} \equiv 1 \mod p. \ \ \ \ \ \ (*)

    now let A=\sum_{k=1}^{300}k^k. then: A \equiv \sum_{j=1}^6 \sum_{r=0}^{42} (7r+j)^{7r+j} \equiv \sum_{j=1}^6 j^j \sum_{r=0}^{42}j^r = 43 + \sum_{j=2}^6 j^j \sum_{r=0}^{42} j^r \mod 7. now by (*): \ \ \sum_{r=0}^{42} j^r \equiv j^6 \equiv 1 \mod 7. therefore: A \equiv 43 + \sum_{j=2}^6 j^j \mod 7.

    we have \sum_{j=2}^6 j^j \equiv 2^2 + 3^3 + (-3)^4 + (-2)^5 + (-1)^6 \equiv 4 -1 -3 - 4 + 1 \equiv -3 \mod 7. hence A \equiv 40 \equiv 5 \mod 7.
    Last edited by NonCommAlg; November 23rd 2009 at 08:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by NonCommAlg View Post
    \sum_{r=0}^{np} j^r \equiv j^n \mod p. \ \ \ \ \ \ (*)
    Is that right? For n=1 don't we have that \sum_{r=0}^{n}\jmath^r=\sum_{r=0}^{p-2}\jmath^{r}+\jmath^{p-1}+\jmath^{p}\equiv 1+\jmath ? I may be missing something.

    Also, here is an alternate way. It is similar to NCA's. I hope I didn't make a fatal error. A verification would be much appreciated.

    Problem: Compute \mathcal{J}=\sum_{\jmath=1}^{300}\jmath^{\jmath}\t  ext{ mod }7

    Solution:

    Lemma: If p is prime and 1<\jmath<p then \sum_{r=0}^{p(p-1)}\jmath^r\equiv1\text{ mod }p.

    Proof: Note that by the geometric sum we have that \left(\jmath-1\right)\sum_{r=0}^{p(p-1)}\jmath^r=\jmath^{p(p-1)+1}-1=\jmath\cdot\left(\jmath^p\right)^{p-1}-1\quad\color{red}(1). Now note that since 1<\jmath<p and p is prime that (\jmath,p)=1. Therefore, Fertmat's little theorem dictates that \jmath^{p}\equiv \jmath\text{ mod }p\implies \left(\jmath^p\right)^{p-1}\equiv\left(\jmath\right)^{p-1}\equiv1. This implies by \color{red}(1) that \left(\jmath-1\right)\sum_{r=0}^{p(p-1)}\jmath^r\equiv\jmath-1\text{ mod }p. Lastly noting that 0<\jmath-1<p-1\implies(\jmath,p)=1 means that \jmath-1 has a multiplicative inverse \text{ mod }p finishes the argument. \blacksquare

    Next noting, as NCA did, that if one writes out some terms of \mathcal{J} that one will notice that \mathcal{J}=\sum_{\jmath=1}^{6}\sum_{r=0}^{42}\lef  t(7r+\jmath\right)^{7r+\jmath}+\sum_{r=0}\left(7r\  right)^{7r}\equiv\sum_{\jmath=1}^{6}\sum_{r=0}^{42  }\left(7r+\jmath\right)^{7r+\jmath} =43+\sum_{\jmath=2}^{6}\sum_{r=0}^{42}\left(7r+\jm  ath\right)^{7r+\jmath}\text{ mod }7\quad\color{red}(2). Also,

    since the binomial theorem readily tells us that every term, save \jmath^{7r+\jmath}, will have a coefficent of 7r that \left(7r+\jmath\right)^{7r+\jmath}\equiv\jmath^{7r  +\jmath}=\jmath^{\jmath}\cdot\left(\jmath^7\right)  ^r\equiv \jmath^\jmath\cdot\jmath^r\text{ mod }7. Therefore, {\color{red}(2)}\implies \mathcal{J}\equiv43+\sum_{\jmath=2}^{6}\sum_{r=0}^  {42}\left\{\jmath^\jmath\cdot\jmath^r\right\}=43+\  sum_{\jmath=2}^{6}\jmath^{\jmath}\sum_{r=0}^{42}\j  math^r\text{ mod }7. And noticing the inner sum satisfies the conditions of the lemmaf or each fixed \jmath that we may conclude that \sum_{r=0}^{42}\jmath^r\equiv1\text{ mod }7. Thus \mathcal{J}\equiv43+\sum_{\jmath=2}^{6}\jmath^{\jm  ath}=43+1^1+2^2+3^3+\left(-3\right)^3+\left(-2\right)^5+\left(-1\right)^6=40\equiv5\text{ mod }7
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Drexel28 View Post
    Is that right? For n=1 don't we have that \sum_{r=0}^{p}\jmath^r=\sum_{r=0}^{p-2}\jmath^{r}+\jmath^{p-1}+\jmath^{p}\equiv 1+\jmath ? I may be missing something.
    no, you're not missing anything. that n should be replaced by p-1. however, this will not change any part of my solution.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by NonCommAlg View Post
    no, you're not missing anything. that n should be replaced by p-1. however, this will not change any part of my solution.
    Not to be a bother O Great NCA, but are there any flaws in my solution?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Drexel28 View Post
    Not to be a bother O Great NCA, but are there any flaws in my solution?
    if you don't mind, i'll take a look at it later. gotta go now.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by NonCommAlg View Post
    if you don't mind, i'll take a look at it later. gotta go now.
    Sounds good compadre.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 04:40 PM
  2. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 1st 2009, 12:16 PM
  3. Replies: 0
    Last Post: May 28th 2009, 10:07 AM
  4. Modular help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 5th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum