# Thread: help with modular congruence

1. ## 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?

2. Originally Posted by coatesdr
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.$

3. Originally Posted by NonCommAlg
$\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 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 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 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$

4. Originally Posted by Drexel28
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.

5. Originally Posted by NonCommAlg
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?

6. Originally Posted by Drexel28
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.

7. Originally Posted by NonCommAlg
if you don't mind, i'll take a look at it later. gotta go now.