# Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$

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.

-
What have you tried? Have you computed the powers of $2$ mod $7$? – JavaMan Nov 4 '12 at 22:06
i have done whole table for Z/7Z so the power of 2 mod 7 = 2, 4 ,1 , 2, 4, 1 etc – Jack F Nov 4 '12 at 22:10
Have 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$. – JavaMan Nov 4 '12 at 22:13
i don't think so. – Jack F Nov 4 '12 at 22:16
i 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 ? – Jack F Nov 4 '12 at 22:22

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

-
the problem is that i don't know how to proof it and show it, just pick a random number or use induction or what – Jack F Nov 4 '12 at 22:42
what would you use for part 1? – Jack F Nov 4 '12 at 22:51
That's where the hint given by Pantelis above comes in, which is clarified further in a comment below that answer... – amWhy Nov 4 '12 at 22:58
im 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? – Jack F Nov 5 '12 at 0:02
I'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$. – amWhy Nov 5 '12 at 0:21

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

-
where did you get that and how do i go from there? proof by induction? – Jack F Nov 4 '12 at 22:05
Perhaps, @Pantelis, you can add the word "or" as in $3k, 3k+1$, $\underline{or} \;3k+2$ – amWhy Nov 4 '12 at 22:07
For example: If $n=3k+1$ then $$2^{3k+1} \equiv 2\cdot 8^k (7)$$ – PAD Nov 4 '12 at 22:35

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

-