0
$\begingroup$

We have this question on a review sheet in my discrete math class and I have also provided the given answer. I am totally lost when it comes to this stuff, and I would just like an explanation of why each step is taken. All the numbers below are represented in base 10 as usual. Find the last two digits of each in the base representation requested. (That is, reduce the number modulo the appropriate modulus, and then convert into the new base.)

$74^{1001}67^{300}$ in base 3

To get the last 2 digits, reduce modulo 9. $$74^{1001}67^{300}≡2^{1001}4^{300}≡2^{1001}2^{600}≡2^{1601}≡2^5 2^{1596} ≡32\cdot ({2^6})^{266}≡5\cdot 64^{266}≡5\cdot1^{266}≡5 \pmod 9$$ Convert to base $3$: $5_{10}≡12_{3}$

$\endgroup$
2
$\begingroup$

First of all, you have to reduce modulo $9$, because $9=3^2$, so finding the last two digits is the same as finding the answer modulo $9$.

The first step is:

$74^{1001}67^{300}\equiv 2^{1001}4^{300}$.

This is the result of reducing $74$ and $67$, modulo $9$, to $2$ and $4$, respectively. At this point, we note that $4$ is also a power of $2$, so we're really just looking at a single power of $2$, and we write it that way:

$2^{1001}4^{300}\equiv 2^{1001}2^{600}\equiv 2^{1601}$.

Next, we think about powers of $2$, modulo $9$. Look at the first few:

$\begin{align}2^1&\equiv 2\\ 2^2&\equiv 4\\ 2^3&\equiv 8\\ 2^4&\equiv 7\\ 2^5&\equiv 5\\ 2^6&\equiv 1\equiv 2^0\end{align}$

Since every sixth power of $2$ is unity, we want to look at the exponent $1601$ as a multiple of $6$, plus a remainder. Note, by the division algorithm, that $1601=6\cdot 266 + 5$. Thus:

$2^{1601}\equiv 2^{6\cdot 266}2^5\equiv (2^6)^{266}2^5\equiv 1^{266}2^5\equiv 2^5\equiv 5$.

Finally, any number congruent to $5$ modulo $9$ must have its ternary expansion ending in the digits $12$.

Does that answer your question?

$\endgroup$
  • $\begingroup$ Yes, thank you very much! Your explanation cleared up any confusion I had. $\endgroup$ – pythonbeginner4556 Jul 7 '15 at 2:59

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.