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$

Question

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

Answer 1

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

Answer 2

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