# Count the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$

How I can calculate the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$.

I think that I have to solve the system of congruences:

$\qquad 4^x \equiv 33 \pmod{100}$

$\qquad8^x \equiv 37 \pmod{100}$

$\qquad\ x \equiv 39 \pmod{100}$

Someone can help me? Thank you

• Is this really algebra-precalculus? – Shahar Aug 21 '14 at 16:59
• Something's missing here. $20039,20139,20239,\ldots, 29839,29939$ are the numbers in that range which end in $39$, so what do you mean by 'calculate' them? – Dan Rust Aug 21 '14 at 17:01
• Not, you have the conditions writen in the exercise. – rgl4 Aug 21 '14 at 17:04
• Hopefully my edit makes it more clear what the exercise is. – Dan Rust Aug 21 '14 at 17:06

$x\,$ ends in $\,\color{#c00}3\color{#0a0}7\,$ in base $8\iff x\, =\, n\cdot 8^2\! + \color{#c00}3\cdot 8 + \color{#0a0}7\iff x\equiv 3\cdot 8+7\equiv 31\pmod{8^2}$

$x\,$ ends in $\,\color{#c00}3\color{#0a0}3\,$ in base $4\iff x\, =\, n\cdot 4^2\! + \color{#c00}3\cdot 4 + \color{#0a0}3\iff x\equiv 3\cdot 4+3\equiv 15\pmod{4^2}$

So the correct system of congruences is below, which we solve by CRT (Chinese Remainder).

$\qquad\qquad\qquad\,\ x\equiv 15 \pmod{16}$

$\qquad\qquad\qquad\,\ x \equiv 31 \pmod{64}$

$\qquad\qquad\qquad\,\ x \equiv 39 \pmod{100}$

$\text{Hence we have} \ x = 39\!+\!100k\,$ for $\,k\in\Bbb Z$ ${\rm mod}\ 16\!:\,\ 15\equiv x\equiv 39\!+\!100\color{#c00}k\equiv 7\!+\!4k\!\iff\! 8\equiv 4k\ \begin{cases}\!\!\!\iff\! 16\mid4k\!-\!8\\ \!\!\!\iff\ \, 4\mid k\!-\!2\\ \!\!\!\iff\! \color{#c00}{k = 2\!+\!4j}\end{cases}$ ${\rm mod}\ 64\!:\,\ 31\equiv x\equiv 39\!+\!100(\color{#c00}{2\!+\!4\color{#0a0}j})\equiv\, -17\!+\!16j\!\!\iff\!\! 48\equiv 16j\begin{cases}\!\!\!\iff\! 64\mid 16j\!-\!48\\ \!\!\!\iff\ \, 4\mid j\!-\!3\!\\ \!\!\!\iff\ \color{#0a0}{j = 3\!+\!4i} \end{cases}$

$\text{Hence we have} \ x = 39\!+\!100(\color{#c00}{2\!+\!4}(\color{#0a0}{3\!+\!4i}))\, =\ \_\_\_ + 100\cdot\color{#c00} 4\cdot \color{#0a0}4\, i\ \,$ for $\, \ i\in\Bbb Z$

No, the system is \eqalign{x &\equiv 39 \mod 100\cr x &\equiv 3\times 4 + 3 = 15 \mod 4^2\cr x &\equiv 3 \times 8 + 7 = 31 \mod 8^2\cr}

• I understand the first congruence, but not the others. Can you help me? – rgl4 Aug 21 '14 at 17:08
• The last two digits of $x$ in base $b$ are $d_1, d_0$ where $x = d_0 + b d_1 + b^2 (\ldots)$, i.e. $x \equiv d_0 + b d_1 \mod b^2$. – Robert Israel Aug 21 '14 at 18:03