Results 1 to 7 of 7

Thread: 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle p > 2$ is a prime number and $\displaystyle 1 < j < p,$ then $\displaystyle S(j)=\sum_{r=0}^{p-2} j^r \equiv 0 \mod p.$ the reason is that $\displaystyle (j-1)S(j) \equiv 0 \mod p,$ because $\displaystyle j^{p-1} \equiv 1 \mod p.$

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

    now let $\displaystyle A=\sum_{k=1}^{300}k^k.$ then: $\displaystyle 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 $\displaystyle (*): \ \ \sum_{r=0}^{42} j^r \equiv j^6 \equiv 1 \mod 7.$ therefore: $\displaystyle A \equiv 43 + \sum_{j=2}^6 j^j \mod 7.$

    we have $\displaystyle \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 $\displaystyle A \equiv 40 \equiv 5 \mod 7.$
    Last edited by NonCommAlg; Nov 23rd 2009 at 07: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
    22
    Quote Originally Posted by NonCommAlg View Post
    $\displaystyle \sum_{r=0}^{np} j^r \equiv j^n \mod p. \ \ \ \ \ \ (*)$
    Is that right? For $\displaystyle n=1$ don't we have that $\displaystyle \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 $\displaystyle \mathcal{J}=\sum_{\jmath=1}^{300}\jmath^{\jmath}\t ext{ mod }7$

    Solution:

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

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

    Next noting, as NCA did, that if one writes out some terms of $\displaystyle \mathcal{J}$ that one will notice that $\displaystyle \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}$$\displaystyle =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 $\displaystyle \jmath^{7r+\jmath}$, will have a coefficent of $\displaystyle 7r$ that $\displaystyle \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, $\displaystyle {\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 $\displaystyle \jmath$ that we may conclude that $\displaystyle \sum_{r=0}^{42}\jmath^r\equiv1\text{ mod }7$. Thus $\displaystyle \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 $\displaystyle n=1$ don't we have that $\displaystyle \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 $\displaystyle n$ should be replaced by $\displaystyle 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
    22
    Quote Originally Posted by NonCommAlg View Post
    no, you're not missing anything. that $\displaystyle n$ should be replaced by $\displaystyle 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
    22
    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: Oct 11th 2010, 03:40 PM
  2. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 1st 2009, 11:16 AM
  3. Replies: 0
    Last Post: May 28th 2009, 09:07 AM
  4. Modular help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 5th 2007, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum