What is the biggest $n$ in $4^n$ that divides $7^{2048} - 1$?

Question

A few days ago I stumbled on the following question, it was used in the Museum of mathematics masters tournament:

What is the biggest integer $n$ in $4^n$, that divides $7^{2048} - 1$?

a) 1

b) 3

c) 5

d) 7

It was not phrased exactly like this, but it is similar enough.

Using ghci and a python terminal I guessed the answer is 7. But I don't know how to go about it using only pen and paper.

Answer 1

Let $\, \upsilon_p(n)\, $ denote $\, m\, $ s.t. $\, p^m\mid n\, $ and $\, p^{m+1}\nmid n$.

LTE (Lifting The Exponent Lemma):

$a,b$ odd, $n$ even$\ \Rightarrow\,\, \upsilon_2(a^n-b^n)=\upsilon_2(a-b)+\upsilon_2(a+b)+\upsilon_2(n)-1$

$7,1$ are odd, $2048$ is even, so

$\upsilon_2(7^{2048}-1^{2048})=\upsilon_2(7-1)+\upsilon_2(7+1)+\upsilon_2(2048)-1=1+3+11-1=2\cdot \textbf{7}$

Answer 2

You can write \begin{align*} 7^{2048} - 1 &= 7^{2048} - 1^{2048} \\ &= (7^{1024} + 1)(7^{512} + 1)(7^{256} + 1)(7^{128} + 1)(7^{64} + 1)(7^{32} + 1)(7^{16} + 1)(7^{8} + 1)(7^{4} + 1)(7^{2} + 1)(7 + 1)(7-1) \end{align*}

For all $k \geq 2$, $7^{2^k} + 1 \equiv (-1)^{2^k} + 1 \equiv 2 \mod 4$, so each term of the form $(7^{2^k} + 1)$ has only one factor of 2. The $(7+1)$ term has 3 factors of 2 and the $(7-1)$ has one factor of 2. So the highest power of 2 that divides $7^{2048} + 1$ is $1\cdot 10 + 3 + 1 =14$, which means for you $n=\lfloor 14/2 \rfloor = 7$.

Answer 3

Lemma: if $4\mid n-1$,then $$||n^k-1||_4=||n-1||_4+||k||_4$$($a=||n||_b$ is the bigger power of b such that $b^a\mid n$) this is a famous lemma whose proof is by induction on $k$ 4|7^2-1 so we have $||(7^2)^{1024}||=5+2=7$$

Answer 4

Well, you are looking to find the largest $n$ such that $7^{2048}\equiv1$ (mod $4^n$) and, since $7$ and $4^n$ are coprime you know $7^{\varphi(4^n)}\equiv1$ (mod $4^n$) from Euler's theorem. And $\varphi(4^n)=\varphi(2^{2n})=2^{2n-1}(2-1)=2^{2n-1}$.

Now, $2048=2^{11}=2^{2\times6-1}=\varphi(4^6)$. So $n=6$ is a lower bound.

Sadly, I expect that's the easy part. You'll need another approach to test whether $n=7$ also works.

Answer 5

As $2048=2^{11},$

$$(8-1)^{2048}-1=-1+(1-8)^{2048}$$

$$=-1+1-2048\cdot8+\binom{2048}28^2-\binom{2048}38^3+\cdots$$

$$=-2^{11}2^3+2^{10}\cdot2047\cdot2^6-2^92^{11}\cdot2047\cdot341+\cdots\text{ as }2046=6\cdot341$$

$$=2^{14}[-1+2^2\cdot2047-2^6\cdot2047\cdot341+\text{ higher powers of }2]$$

Clearly, $-1+2^2\cdot2047-2^6\cdot2047\cdot341+\text{ higher powers of }2$ is odd