# When is $\left\lfloor \frac {7^n}{2^n} \right\rfloor \bmod {2^n} \ne 0\;$?

Is

$$\left\lfloor \frac {7^n}{2^n} \right\rfloor \bmod{2^n} \ne 0\;$$

always true when $n \ge 3$.

Baker's theorem on transcendental numbers that provide bounds for diophantine equations may be useful, but I will leave that to the experts.

-

One approach would be $7^n = (8 - 1)^n = (2^3 - 1)^n$. Doing binomial expansion, we get $7^n/2^n = 2^n x + k$ (k is sum of all binomial terms $i < n /3$). Little improved because it leaves less terms than above, but essentially same methodology.

-

The question can be restated whether $7^n <2^n \pmod {4^n}$

We can express this also in the number-system to base $2^n$, then
$\qquad 7^n \underset{\text{base } 2^n}{=} "c_n \ b_n \ a_n"$ where $c_n , b_n, a_n$ are the "digits",

$\qquad \qquad$ and valid cases are where we have
$$\qquad 7^n-1 \underset{\text{base } 2^n}{=} "c_n \ 0 \ a_n"$$

As well we can ask, whether there is a number $m$ in the range $7^n -1 \ge m \ge 7^n - (2^n-1)$ such that $$m= k \cdot 2^{2n} \tag 1$$ The latter point of view shall be discussed below.

First we introduce the "residue" $r$ such that we write $m_{n,r} =7^n-r$ where $1 \le r \le 2^n-1$ and $r$ is odd.

With this we find, that for the most residue classes the highest power of 2 occuring in $m_{n,r}$ is $3$, and this excludes then immediately a lot of nontrivial solutions.
Higher powers of $2$ occur only for residues $r \equiv 1 \text{ or } r \equiv 7 \pmod {16}$ so we need only to test $m_{n,1}, m_{n,17}, m_{n,33},... m_{n,2^n-1}$ and $m_{n,7}, m_{n,23}, m_{n,49},... m_{n,2^n-9}$

If we test for the introducing example with residue $r=1$, literally "one step aside from the powers of $7$" we get the sequence $e_{n,1}$ of powers of $2$ which are factor as $7^n -1 = 2^{e_{n,1}} \cdot x$ $$\begin{array} {r|rrrrrrrrrr} n&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17& \cdots \\ \hline e&\cdot&1&4&1&5&1&4&1&6&1&4&1&5&1&4&1&7&1& \cdots \end{array}$$ In this table, if we had a solution for your problem, the power of $2$ as factor at some $n$ should be $2^{2n}$ but we see, that after one solution at $n=2$ and $e_{n,1}=4=2n$ the growth of the exponents of 2 is much delayed: obviously (and in fact) the exponents grow only logarithmically with $n$. So we even know that after that single solution we shall have no more else. Here is a extended table with the required exponents: $$\begin{array} {r|rrrrrrrrrr} n&0&1&2&3&4&5&6&7&8&9& \cdots \\ \hline m_n=7^n-1 &0&6&48&342 & \cdots\\ e=\{m_n,2\}&\cdot&1&4&1&5&1&4&1&6&1& \cdots \\ \hline \text{required e}=&0&2&4&6&8&10&12&14&16&18& \cdots \end{array}$$ The possible key of the problem is then, that the similar effect occurs for all (interesting) residues $r$ which we have to look at, and these are only $1,17,33,49,...,1+16k,...$ and $7,23,39,...,7+16k$ because with all other residues $r$ we have at most powers of $2$ with exponent $3$ and thus we cannot have a solution with $e=2n$ for $n \gt 1$.
For some choice of $n$ we need check residue classes $r \lt 2^n$ and only two of them in each interval of $16$.

The problem which is not yet solved by this all is, that the tables for $n$ and $e$ have a certain perturbation of the entries $e$ so that higher powers can occur earlier. That this actually does not occur sufficiently strong and that it does not provide a solution in empirically accessible ranges illustrates the following table.

The table shows in the grey columns the residues $r$, and in the rows the occurences of $e_{n,r}$ . For instance, the row at residue $r=1$ contains the exponents of the powers of $2$ in $7^n -1$ First column refers to $\{7^1-1,2\}$ where the braces mean $e=\{n,p\}$ the exponent with which the primefactor $p$ is factor of $n$, so $7^1-1=6$ has the primefactor 2 to the exponent 1. The same is valid for the values $n=1,3,5,7,...$ but is not documented in the table. The next column contains the exponent $\{7^2-1,2\} =4$ which is also valid for $n=2,6,10,14,...$. The third column contains the exponent $\{7^4-1,2\} =5$ which is also valid for $n=4 ,12,20,28,...$. And so on.

In general the columns follow only roughly(!) the powers of $2^c$ in $7^{2^c}$; the sequences of $n$ have with small perturbations compared with that of the sequences for residue $r=1$. However, a solution of the original problem could thus only occur, if the entries $e_{n,r}$ were about $2 \cdot 2^c$ and we see immediately, that for column-indexes $c \gt 4$ which would require $e_{n,r} = 2\cdot 2^4 = 32$ this very likely does not occur.

[update] Here is also an improved picture, where the lowest $n$ are made explicte with the exponents of the powers of $2$. I printed "n backtick e" in each cell. The yellow marked cells actually have $e_{n,r} \ge 2n$ and would give a solution $7^n-r \equiv 0 \pmod{4^n}$, but we ask only for solutions in the range $r \lt 2^n$ The ends of that ranges are marked by a bold underline and contain only the first entries of each columns down to that bold-underlined cells. Blue cell refer to $7^n-r$ which are negative and are not in the scope of our discussion.

Well, unfortunately this does not resolve the problem completely. But at least it gives a strong intuition - and possibly the path shown here can be followed later on.

-

The following may be a starting point:

Write $7^n \mod 4^n$: $$7^n =a\cdot 4^n + b \quad b<4^n$$ $$\left\lfloor \frac{7^n}{2^n} \right\rfloor \equiv \left\lfloor \frac b{2^n} \right\rfloor \pmod{2^n}$$ and this is $0$ iff $b<2^n$.

Well, $7^n=(2^3-1)^n=\displaystyle\sum_{0\le i\le n} \binom{n}{i} 2^{3i} \cdot (-1)^{n-i}$, and those with indices $3i\ge 2n$ vanish, thus $$7^n \equiv (-1)^n\sum_{ i < 2n/3 } \binom ni (-8)^{i} = ... \pmod{4^n}$$

-
I don't think that working with the binomial notation can simplify the problem. –  barto Oct 15 '12 at 19:04

A little re-arrangement of the floored division in the counter-example yielded:

$7^{n}\ mod\ 2^{n} = 7^{n} + k\cdot 4^{n}\ ;\ k < 0$ or:

$7^{n}\ mod\ 2^{n} \equiv 7^{n}\left (mod\ 4^{n}\right )$

The first form: $(7^{n}\ mod\ 2^{n}) - 7^{n} = k\cdot 4^{n}$, requires the lhs to be divisible by $4^{n}$, or have $(2n)$ trailing zeroes in binary. A search from $n = 3$ to $n = 2^{17}$ failed to find a candidate. I'm sure there's more to be done with the first form...

So: $7^{n}$ would require bits: [n, 2n-1] to be zero.

-