help with modular congruence

**coatesdr** · November 9th 2009, 02:26 PM

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?

**NonCommAlg** · November 10th 2009, 01:17 AM

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.$

**Drexel28** · November 23rd 2009, 06:20 PM

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<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$

**NonCommAlg** · November 23rd 2009, 07:26 PM

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.

**Drexel28** · November 23rd 2009, 07:27 PM

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?

**NonCommAlg** · November 23rd 2009, 07:29 PM

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.

**Drexel28** · November 23rd 2009, 07:33 PM

Originally Posted by NonCommAlg

if you don't mind, i'll take a look at it later. gotta go now.

Sounds good compadre.

Thread: help with modular congruence

LinkBack

Thread Tools

Display

help with modular congruence

Similar Math Help Forum Discussions

Modular Help

Modular

Congruence Theorem in Modular arithmetic and Euclid's lemma

Modular help

Search Tags