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 have done whole table for Z/7Z so the power of 2 mod 7 = 2, 4 ,1 , 2, 4, 1 etc – 2012-11-04
-
0Have you learned Fermat's little theorem? It states that $a^{p-1} \equiv 1 \pmod{p}$ for any $a$ such that $\gcd(a,p) = 1$. In other words, the multiplicative subgroup of $\mathbb{Z}/p \mathbb{Z}$ has order $p - 1$. – 2012-11-04
-
0i don't think so. – 2012-11-04
-
0i think i might know what you mean like 2^3-1=1 but then 3/3 =1 then like 2^4-1=1 3/4=1 ? – 2012-11-04
-
0oo yeah i get the idea then $2^4-1 = 1 (mod 7), 4/3= 1 mod 3? – 2012-11-04
-
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)$.
-
0the problem is that i don't know how to proof it and show it, just pick a random number or use induction or what – 2012-11-04
-
0what would you use for part 1? – 2012-11-04
-
0That's where the hint given by Pantelis above comes in, which is clarified further in a comment below that answer... – 2012-11-04
-
0im confused about proof by induction so assume that 3|n=>2^n-1 so then n+1/3=>2^(n+1)-1 = n/3 +1/3 = 2^n+1 so then 2^-1 +1/3? – 2012-11-05
-
0I'm having trouble making out your work without formatting, and the use of n + 1/3 or (n+1)/3...though you probably mean (n+1)|3. I think you might want to consider the cases separately, establishing that for all $n$ there is some $k\geq 0$ such that either (exclusively) $n=3k$, or...or $n = 3k+2$. Then show that only when $n = 3k$ is $2^n -1 \equiv 0 \pmod{7}$. You can prove $(1)$ without induction on n by proving it's contrapositive: suppose it is not the case that $3|n$...then (two cases to consider: 1.2, 1.3) ... then 7 does not divide $2^n - 1$. – 2012-11-05
-
0Similarly, you can prove $(2)$ by assuming that $7$ does not divide $2^n -1$...then...3 does not divide n... $A \implies B$ is equivalent to (not $B) \implies $ (not $A$)... – 2012-11-05
-
0you said to use induction on part 2 meaning 3|n => $2^n-1$ and thats what i was trying to do, so thats what i was trying to do – 2012-11-05
-
0You can use induction. But note that if 3|n, then 3|(n+3) and n|(n+6). I.e., if 3|n, then 3 will NOT divide n+1 or n + 2...There are really only 3 cases to consider...if 3|n, then there is some k such that n=3k: if you use induction on k, then you'll see 3|3(k+1) and 3(k+2).... – 2012-11-05
-
0thank you very much for that long explanation to make it clear for me, appreciate it. – 2012-11-05
-
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$.
-
0where did you get that and how do i go from there? proof by induction? – 2012-11-04
-
0Perhaps, @Pantelis, you can add the word "or" as in $3k, 3k+1$, $\underline{or} \;3k+2$ – 2012-11-04
-
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$.