Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$. The hint is to look at the table of $\Bbb Z/7\Bbb Z$ powers of $2 \bmod 7$, and to notice how they repeat. I'm not sure if I should use proof by induction or how to prove it.
Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$
-
0i get the idea now, but i am having trouble figuring out what to really show and how in the proof – 2012-11-04
5 Answers
Referring to your list, in the comments below your question:
"i have done whole table for $\mathbb{Z}/7\mathbb{Z}$ so the power of $2^n - 1 \pmod{7} = 2, 4 ,1 , 2, 4, 1$ etc"
Do you notice that the $n$ from which you derived every third value (in your list), minus 1, is a multiple of 3? That may sound confusing, sorry. I can try to clarify...$n = 3: 2^3\equiv 0 \pmod{7}$; $n=6: 2^6−1 = 64-1 = 63 \equiv 0 \pmod{7}$...
$2^4 - 1 \equiv 1 \pmod{7}$ and we want only values of n such that $2^n -1 \equiv 0 \pmod{7}$
What you're trying to show, or need to show, that for all and only such $n$, $n \equiv 0 \pmod{3}$.
First, note that what your being asked to show is bi-directional: $\iff$, so you need to show that $\text{for all}\;\;n,\;\; \text{if}\;\; 2^n-1\equiv 0 \pmod{7}\implies n\mid 3\tag{1}$ AND you need to show that, for all $n$ $3\mid n \implies 2^n -1 \equiv 0 \pmod{7}.\tag{2}$ Are you comfortable with proof by induction? That would work nicely for part (2).
For part (1), as suggested in Pantelis's answer, your task is reduced to three cases; every $n \in \mathbb{N}$, either
$(1.1)\;\;n\mid 3$ (there is some $k$ such that $n = 3k$), or
$(1.2)\;\;n$, when divided by 3, has a remainder of 1 (there is some $k$ such that $n = 3k + 1$), or else,
$(1.3)\;\;n$, when divided by 3 has a remainder of 2 (there is some $k$ such that $n = 3k + 2$).
(where $k$ in each case, is an integer $\geq 0$.)
More specifically, if you start with proving $(2)$, which is perfectly acceptable, it will be fairly easy to establish the case of $(1.1)$ for $(1)$
Once you've dealt with case $(1.1)$, then you simply need to use that case to deal with cases $(1.2) \text{ and}\;(1.3)$ for establishing $(1)$.
-
0My pleasure, Jack. Sometimes notation can get in the way of understanding what's going on, or how to begin... – 2012-11-05
It's true if $\rm n < 3.$ Else $\rm\:7\mid 2^n\! -\! 1 = 7\cdot 2^{n-3}\! + 2^{n-3}\!-\!1$ $\!\iff\!$ $\rm7\mid 2^{n-3}\!-\!1$ $\!\iff\!$ $\rm 3\mid n\,$ by induction.
The inductive step exploits the cyclicity $\rm mod\ 7\!:\ f(n\!+\!3)\equiv f(n)\:$ for $\rm\:f(n) = 2^n\!-1\:$ since $\:2^3\!\equiv 1.$
You need to use two facts. $8 \equiv 1 \ (7)$ and second each natural number $n$ has the form $3k$, $3k+1$, $3k+2$.
-
0For example: If $n=3k+1$ then $$2^{3k+1} \equiv 2\cdot 8^k (7)$$ – 2012-11-04
There are also elementary ways to prove it that don’t use the hint. You should ignore this if it confuses you, but if it doesn’t, you may find it a nice way to look at the problem.
The binary representations of $7$ and $2^n-1$ are $111$ and $\underbrace{11\dots 11}_n$, respectively. If $n=3m$, write $2^n-1$ as
$\underbrace{111~111~\dots~111~111}_{m\text{ groups of }3}\;;$
it’s then clear from the grade-school long division algorithm that
$\underbrace{111~111~\dots~111~111}_{m\text{ groups of }3}=111\cdot1~\underbrace{001~\dots~001~001}_{m-1\text{ groups}}\;,$
where the quotient $1~\underbrace{001~\dots~001~001}_{m-1\text{ groups}}$ is clearly an integer.
On the other hand, if $n=3m+1$, then $2^n-1$ has the binary representation
$\underbrace{111~111~\dots~111~111}_{m\text{ groups of }3}~1\;,$
and if $n=3m+2$, $2^n-1$ has the binary representation
$\underbrace{111~111~\dots~111~111}_{m\text{ groups of }3}~11\;.$
Dividing these by $111_{\text{two}}$ gives you the quotient
$1~\underbrace{001~\dots~001~001}_{m-1\text{ groups}}~0$ with remainder $1$ in the first case and $1~\underbrace{001~\dots~001~001}_{m-1\text{ groups}}~00$ with remainder $11_{\text{two}}$ in the second, and the non-zero remainders show that $7\not\mid 2^n-1$ in these two cases.
A more general version is the following:
If $f_m(x) = \displaystyle \sum_{k=0}^{m} x^k$ divides $p_n(x) = x^n -1$, then $(m+1) \vert n$.
Your result can be obtained by taking $m = 2$ and $x=2$.
Proof:
The proof of the above claim follows immediately from the remainder theorem.
The roots of $f_m(x)$ are the $m$ complex roots of unity i.e. $\zeta_1,\zeta_2, \ldots, \zeta_{m-1}, \zeta_{m}$, where $\zeta_k = \exp \left(\dfrac{2 \pi ki}{m+1}\right)$ Since $f_m(x) \vert p_n(x)$, we need that $p_n(\zeta_k) = 0$. In particular, we need that $p_n(\zeta_1) = 0$. Hence, we get that $\zeta_1^n = 1$ But we know that the least number $\ell$ such that $\zeta_1^{\ell} = 1$ is $\ell = m+1$. Hence, $(m+1) \vert n$.