0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is this really algebra-precalculus? $\endgroup$ – Shahar Aug 21 '14 at 16:59
  • 1
    $\begingroup$ 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? $\endgroup$ – Dan Rust Aug 21 '14 at 17:01
  • $\begingroup$ Not, you have the conditions writen in the exercise. $\endgroup$ – rgl4 Aug 21 '14 at 17:04
  • 1
    $\begingroup$ Hopefully my edit makes it more clear what the exercise is. $\endgroup$ – Dan Rust Aug 21 '14 at 17:06
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I understand the first congruence, but not the others. Can you help me? $\endgroup$ – rgl4 Aug 21 '14 at 17:08
  • $\begingroup$ 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$. $\endgroup$ – Robert Israel Aug 21 '14 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.