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.

$\endgroup$
  • $\begingroup$ i have done whole table for Z/7Z so the power of 2 mod 7 = 2, 4 ,1 , 2, 4, 1 etc $\endgroup$ – Jack F Nov 4 '12 at 22:10
  • $\begingroup$ 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$. $\endgroup$ – JavaMan Nov 4 '12 at 22:13
  • $\begingroup$ i don't think so. $\endgroup$ – Jack F Nov 4 '12 at 22:16
  • $\begingroup$ 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 ? $\endgroup$ – Jack F Nov 4 '12 at 22:22
  • $\begingroup$ oo yeah i get the idea then $2^4-1 = 1 (mod 7), 4/3= 1 mod 3? $\endgroup$ – Jack F Nov 4 '12 at 22:26
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Jack F Nov 4 '12 at 22:42
  • $\begingroup$ what would you use for part 1? $\endgroup$ – Jack F Nov 4 '12 at 22:51
  • $\begingroup$ That's where the hint given by Pantelis above comes in, which is clarified further in a comment below that answer... $\endgroup$ – Namaste Nov 4 '12 at 22:58
  • $\begingroup$ 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? $\endgroup$ – Jack F Nov 5 '12 at 0:02
  • $\begingroup$ 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$. $\endgroup$ – Namaste Nov 5 '12 at 0:21
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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