# Expected value of the remainder when a random variable is divided by a number

Let $$a,b,c,d,e,f$$ be integers selected from the set $$\{1,2,\cdots, 100\}$$ uniformly and at random with replacement. Let $$M=a+2b+4c+8d+16e+32f$$. What is the expected value of the remainder when $$M$$ is divided by $$64$$?

Let $$f_n(x)$$ be the remainder when $$x$$ is divided by $$2^n$$. Then we are interested in finding $$E(f_6(M))$$. Since both the expected value and $$f_n$$ are linear, we can find the expected value of each term and then sum them together in the end to get the answer.

Now $$E(f_6(a))=\sum_{k=1}^{100}f_6(k)\cdot \frac{1}{100}=26.82$$.

Now since $$ac\equiv bc \pmod{nc}$$ iff $$a\equiv b\pmod{n}$$, we can calculate

$$E(f_6(2b))=2\cdot E(f_5(b))=2\cdot \sum_{k=1}^{100}f_5(k)\cdot \frac{1}{100}=29.96$$

And similarly $$E(f_6(4c))=29.2, E(f_6(8d))=27.68, E(f_6(16e))=24, E(f_6(32f))=16$$ and hence $$E(f_6(M))=5456 \pmod{64}=16$$.

But this is a question from a math competition training set, so I suspect there is a much quicker and elegant way to solve it, is there such a way? Thanks in advance.

• I think the claim that $f_n$ is linear is problematic. For instance $0 = (4 \text{ mod } 4) \neq 2\cdot (2 \text{ mod }4) = 4$. $f_n$ is only linear mod $2^n$. Nov 25, 2021 at 9:24
• @Ishigami Where does $5456$ in $E(f_6(M)) = 5456 \pmod{64}$ come from? Nov 26, 2021 at 1:47

I think there would have been a highschool math solution to this problem if the integers were instead drawn uniformly from $$\left\{ 1,2,3...64\right\}$$ . Then, regardless of the remainder stemming from $$2b+4c+8d+16e+32f$$, the $$a$$ -term would make the final remainder uniformly drawn from $$\left\{ 0,1,2...63\right\}$$. Why? Say e.g. that the remainder from $$2b+4c+8d+16e+32f$$ happens to be $$15$$. If we then draw $$a=49$$ the final remainder will be $$0$$ ; if we draw $$a=50$$ the final remainder will be $$1$$; if we draw $$a=51$$ the final remainder will be $$2$$ and so on with equal chance for all potential outcomes. And this logic goes through regardless of what the remainder from $$% 2b+4c+8d+16e+32f$$ happen to be. So the expected remainder would then be $$% 63/2=31.5$$. The same logic would apply if the integers were drawn from $$% \left\{ 1,2,3...64N\right\}$$. But I can't see any way of extending this line of reasoning to the case when all integers are drawn from $$\left\{ 1,2,3...100\right\}$$.