Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $r(n)$ be the remainder of $2^n$ divide by $n$, such as $r(6)=4,r(p)=2(2<p\in \mathbb P)$.

Denote $$a_n=\frac{1}n\sum_{k=1}^n\frac{r(k)}k.$$ Is it true that $a_n<\frac{1}2 \forall n\in \mathbb N$?

Since $0\leq r(k)<k,0\leq a_n<1$, it seems that $\lim_{n\to \infty}a_n=\dfrac{1}2$, if it exist.


Denote $$a(m,n)=\frac{1}{n-m+1}\sum_{k=m}^n\frac{2^k\mod k}k,$$ then $a_n=a(1,n).$


share|cite|improve this question
There's this "any" ambiguity again. Is the question abount $\exists n\colon a_n<\frac12$ or $\forall n\colon a_n<\frac12$? – Hagen von Eitzen Aug 10 '13 at 10:01
@Hagen von Eitzen For all. – Next Aug 10 '13 at 10:28

I don't know whether the answer is yes or no, but I want to make the following points:

  • If $n$ is a small multiple of a prime then $r(n)$ is likely to be a small power of $2$.
  • Taking this into account leads us to expect that $f(n):=\frac1n\sum_{k=1}^n \frac{r(k)}k$ will be approximately $\frac12 - \frac{c}{\log n}$ for some small constant $c$.
  • It follows that $f(n)$ should be much smaller than $1/2$ for any $n$ within our computational capabilities, but that this discrepancy should become tiny when $n$ is enormous.

In other words: the values of $f(n)$ that we can compute should be significantly less than $1/2$, but it should not be inferred that the same is true when $n\to\infty$.

As noted in Peter Košinár's comment, Fermat's little theorem implies that $2^p\equiv 2\pmod{p}$ for any prime $p$, so $r(p)=2$ whenever $p$ is an odd prime. Moreover, for any $j$ we have $2^{jp}\equiv 2^j\pmod{p}$, so if $2^{jp}\equiv 2^j\pmod{j}$ and $\gcd(j,p)=1$ then the Chinese Remainder Theorem implies that $2^{jp}\equiv 2^j\pmod{j}$. Thus $r(jp)=2^j$ if $2^{jp}\equiv 2^j\pmod{j}$ and $\gcd(j,p)=1$ and $jp>2^j$. The first few instances of this are:

  • $r(p)=2$ when $p$ is an odd prime
  • $r(2p)=2^2$ when $p$ is an odd prime
  • $r(3p)=2^3$ when $p>3$ is prime
  • $r(4p)=2^4$ when $p>3$ is prime
  • $r(5p)=2^5$ when $p>5$ is a prime with $p\equiv 1\pmod{4}$
  • $r(6p)=2^6$ when $p>7$ is prime
  • $r(7p)=2^7$ when $p>13$ is a prime with $p\equiv 1\pmod{3}$
  • $r(8p)=2^8$ when $p>61$ is prime
  • $r(9p)=2^9$ when $p>53$ is prime

To see how these results affect $f(n)$, consider just the contribution from prime values of $k$ in the interval $[1,n]$. If we expect that $r(k)\approx k/2$ on average, then the contribution of prime $k$'s to $f(n)$ would be approximately $$ \frac{1}n\sum_{\substack{1\le k\le n \\ k \text{ prime}}} \frac{1}2 = \frac1n\cdot\frac{\pi(n)}2 \approx\frac{1}{2\log n},$$ where $\pi(n)$ is the number of primes in the interval $[1,n]$, and we have used the estimate $\pi(n)\approx n/\log n$. Since $r(k)=2$ when $k$ is an odd prime, the actual contribution of primes to $f(n)$ is $$ \frac1n\sum_{\substack{3\le k\le n \\ k \text{ prime}}} \frac2k \approx 2\frac{\log\log n}n.$$ This last quantity is vastly smaller than $1/\log n$, so by comparison it is approximately zero. Hence the contribution of prime $k$'s to $f(n)$ is less than the expected contribution by roughly $1/(2\log n)$. Similar computations for $k$'s which are small multiples of primes will yield smaller discrepancies than this. Thus it seems reasonable to expect that $$f(n)\approx \frac12 - \frac{c}{\log n}$$ for some small constant $c$.

However, there is more going on than the above instances of $r(jp)=2^j$. Here is some numerical data to this end. Among all odd $n$ in the interval $[1,10^6]$, we have

  • $r(n)=2$ for $245$ non-primes $n$
  • $r(n)=2^3$ for $380$ values $n$ not of the form $3p$ with $p$ prime
  • $r(n)=2^5$ for $321$ values $n$ not of the form $5p$
  • ...
  • $r(n)=2^{15}$ for $424$ values $n$ not of the form $15p$
  • $r(n)=2^{17}$ for $105$ values $n$ not of the form $17p$
  • $r(n)=2^{19}$ for $35$ values $n$ not of the form $19p$.

These values are interesting because, if $t$ is any integer which is not of the form $2^k$ with $k$ odd, then there are at most $46$ $n$'s for which $r(n)=t$. By contrast, if $t=2^k$ with $k$ odd and $1\le k\le 17$, then there are at least $105$ values $n$ for which $r(n)=t$ but $n$ does not have the form $kp$ with $p$ prime. This means that there should be a causal reason why the values $t=2^k$ occur so often, even when we ignore values $n=kp$ with $p$ prime.

The above data was for odd $n$. The situation for even $n$ is analogous. Namely, among all even $n$ in the interval $[1,10^6]$, any integer $t$ which is not of the form $4^k$ will occur as $r(n)$ for at most $101$ values of $n$. On the other hand, for instance, there are $798$ $n$'s in this interval for which $r(n)=2^8$ but $n\ne 8p$ (with $p$ prime).

Question: why are the powers of $2$ occurring so often as values of $r(n)$, even if we insist that $n$ not be a small multiple of a prime?

share|cite|improve this answer
Actually, $r(n)$ is never equal to $1$... but it is "unusually often" equal to a small power of 2 (e.g. $2$ for primes and 2-PRPs; but also $4$, $8$ and some other values occur pretty often). If we ignore the cases when $r(n)$ is a power of 2, the average seems to be oscillating around $\frac{1}{2}$ pretty nicely. – Peter Košinár Aug 10 '13 at 21:40
In particular, numbers of the form $n=pq$ with $p$ and $q$ odd primes and $p$ small seem to exhibit such behaviour "more often"; satisfying $2^n\equiv 2^p\pmod n$ (FLT gives us the equality modulo $q$ for free). They are not the only ones, though... and accounting for them in the estimate might be quite tricky. – Peter Košinár Aug 10 '13 at 21:58
Peter Košinár comments that $r(n)$ is never equal to $1$. Here's a proof: let $p$ be the smallest prime dividing $n$, and let $\ell$ be the order of $2$ mod $p$. Then $2\le\ell\le p-1$, so $\ell$ cannot divide $n$, which means that $2^n\not\equiv 1\pmod{p}$. – Michael Zieve Aug 11 '13 at 12:20

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.