Additive identity in $\mathbb{Z}_{7}$

Question

The problem consists of two parts: 1)Prove that for some integer $m,$ $3^{m} = 1$ in the integers modulo 7, $\mathbb{Z}_{7}$, which i have done.

The second part asks to use this fact to deduce that $7$ divides $1 + 3^{2001}.$

The way i look at it, we look at $1 + 3^{2001}$ in $\mathbb{Z}_{7}$ and what we get is $3^{m} + 3^{l},$ where $2001 = 7p + l.$ So the question is then to show that $3^{m} + 3^{l} = 0_{\mathbb{Z}_{7}},$ a.k.a. $7 | 3^{m} + 3^{l}.$

A hint would be appreciated. Thanks in advance.

Answer 1

Hint:

Presumably, you've discovered that $3^6 \equiv 1 \pmod{7}$.

Now, $3^{1998} = (3^6)^{333}$. What would this be equivalent to $\pmod{7}$?

What about $3^{2001}$?

Finally, what about $3^{2001} + 1$?

Answer 2

Doing the first part should show you specifically what (smallest, positive) integer works, i.e. 6. Along the way, you see that $3^3\equiv -1\mod 7$. So now we look at

$$2001=6\cdot 333+3\implies 3^{2001}\equiv 1^{337}\cdot (-1)\mod 7.$$

From there you add $1$ and the result is immediate.

Answer 3

Hint $\ {\rm mod}\,\ 7\!:\,\ \color{#c00}{3^{\large 3}\equiv -1}\,\Rightarrow\, {3^{\large 2001}}\!+\!1\equiv (\color{#c00}{3^{\large 3}})^{\large 667}\!+\!1\equiv (\color{#c00}{-1})^{\large 667}\!+\!1\equiv \color{#c00}{-1}+1\equiv 0,\ $ where we employed the Congruence Product, Power and Sum Rules proved below.

---

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)} $

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $

Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)$

Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Proof $\ $ By induction on $\, n = $ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $< n.\,$ By induction $\,g(A)\equiv g(a)\,$ so $\, \color{#0a0}{A g(A)\equiv a g(a)}\,$ by the Product Rule. Hence $\,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,$ by the Sum Rule.

Beware $ $ that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv\, a^b$ is not generally true (unless $\rm B = b,\,$ so it follows by applying the Polynomial Rule with $\,f(x) = x^{\rm b}).$