Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

5 Answers 5

up vote 4 down vote accepted

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

share|improve this answer
    
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.$

share|improve this answer

You need to use two facts. $8 \equiv 1 \ (7)$ and second each natural number $n$ has the form $3k$, $3k+1$, $3k+2$.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.