3
$\begingroup$

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.

  • 0
    i have done whole table for Z/7Z so the power of 2 mod 7 = 2, 4 ,1 , 2, 4, 1 etc2012-11-04
  • 0
    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$.2012-11-04
  • 0
    i don't think so.2012-11-04
  • 0
    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 ?2012-11-04
  • 0
    oo yeah i get the idea then $2^4-1 = 1 (mod 7), 4/3= 1 mod 3?2012-11-04
  • 0
    i get the idea now, but i am having trouble figuring out what to really show and how in the proof2012-11-04

5 Answers 5

4

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

  • 0
    the problem is that i don't know how to proof it and show it, just pick a random number or use induction or what2012-11-04
  • 0
    what would you use for part 1?2012-11-04
  • 0
    That's where the hint given by Pantelis above comes in, which is clarified further in a comment below that answer...2012-11-04
  • 0
    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?2012-11-05
  • 0
    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$.2012-11-05
  • 0
    Similarly, 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
  • 0
    you 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 do2012-11-05
  • 0
    You 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
  • 0
    thank you very much for that long explanation to make it clear for me, appreciate it.2012-11-05
  • 0
    My pleasure, Jack. Sometimes notation can get in the way of understanding what's going on, or how to begin...2012-11-05
2

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

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

  • 0
    where did you get that and how do i go from there? proof by induction?2012-11-04
  • 0
    Perhaps, @Pantelis, you can add the word "or" as in $3k, 3k+1$, $\underline{or} \;3k+2$2012-11-04
  • 0
    For example: If $n=3k+1$ then $$2^{3k+1} \equiv 2\cdot 8^k (7)$$2012-11-04
1

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.

1

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