What is the relationship between modulo and $\log_2$ in this problem?

Question

Here's a screenshot of a diagram from my computer architecture course. You don't need to understand the technical terms here. It's essentially mapping locations from one piece of memory to locations in another piece of memory.

According to the book, we determine the mapping based on the following formula:

$\text{cacheLineNumber} \equiv \text{memoryAddress} \pmod{\text{numberOfLinesInCache}}$

For example, if we're looking at $\text{memoryAddress} = 00001$, and we have $\text{numberOfLinesInCache} = 8$ as in this diagram, then we have $1 \equiv 1\pmod{8}$. Thus, that memory address should map to the cache line numbered $001$.

Below the diagram is an explanation noting that this is the equivalent of using the lower $3$ bits of the given memory address. But I don't understand what the mathematical motivation is for this discovery. I see that it's true, but I don't get it.

Answer 1

Note that a number $$N = b_{n} b_{n-1} \cdots b_{4}b_{3}b_{2}b_{1}{}_{\text{two}} = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+\cdots+2^{n-3}b_n).$$ Therefore, $$N \equiv b_1 + 2b_2 + 4b_3 +0 \equiv b_3 b_2 b_1 {}_{\text{two}}\pmod{8}.$$ Following the above procedure, it is easy to observe that $$b_{n} b_{n-1} \cdots b_{4}b_{3}b_{2}b_{1}{}_{\text{two}} \equiv b_{m} b_{m-1} \cdots b_{1}{}_{\text{two}} \pmod{2^{m}},$$ where $m \le n$.

Answer 2

I felt the other answer still didn't clear up my confusion, but messing around with the numbers on paper, I managed to arrive at an explanation (I think this is somewhat similar to what @Math Lover was saying, but the answer he/she gave was a bit confusing):

If I consider $00101$, that's:

$0*2^4+0*2^3+1*2^2+0*2^1+1*2^0$

And we can isolate $2^3 = 8$ from the two frontmost terms (in fact, from all terms in front of $2^3$, no matter how many bits there are in the string:

$2^3 (0) + (1*2^2 + 0*2^1 + 1*2^0)$

And that matches the format of:

$n = dq + r$

Where $r$ is the remainder.