Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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

share|cite|improve this question

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.

share|cite|improve this answer

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.

enter image description here

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.

enter image description here

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.

share|cite|improve this answer

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

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

share|cite|improve this answer

Your Answer


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.