4
$\begingroup$

Let $a = 31$. Consider the set of integers $T = \{a, 8a, 8^{2}a, 8^{3}a, \cdots \}$. Does $T$ contain the integer:

$999999999900000000000090909090000000000000000008$?

So far I've deduced that if we work mod $9$ that the set $T$ can be reduced to a reduced residue system modulo $9$ by using $8$ as a root. Additionally, because $(a, 9) = (31, 9) = 1$ we can eliminate $a$ from the elements of $T$.

Continuing, remark that $ord_{9}(2) = \phi(9) = 6$ and $ord_{9}(2^{3}) = \frac{6}{3} = 2$. Taking $8^{k} \mod 9$ for $k \in \mathbb{Z^{+}}$ we see that we get the set of reduced residues $\{8, 1\}$. $8$ is an element of this set so $T$ contains $999\ldots 0008$.

That's where I am so far but I have a feeling that I went wrong early on in this one.

  • 1
    Can whoever just downvoted my question explain the downvote?2012-12-17
  • 0
    I don't know, but maybe is because it looks too exaggerated to be an *actual* question and you show no own work on it? This can be solved sharing some of your own efforts, insights and self work in this problem and, perhaps, adding some background of where/how did this question come from.2012-12-17
  • 0
    I suppose...it was downvoted like 10 seconds after I uploaded it though so whoever downvoted it didn't even bother to think about it.2012-12-17

2 Answers 2

3

Hint

$$8 \equiv -1 \pmod 9$$ $$31 \equiv 4 \pmod 9$$

Thus

$$8^k a \equiv ??? \pmod 9$$

  • 0
    I'm sure you're on the right track but could you explain where you're coming from? I'm not seeing your thought process here.2012-12-17
  • 2
    @decave Your number is huge, but the "huge" part contains only 9's and 0's, so it is natural to look at it mod 9... Modulo 9, the question you ask implies "Can $8^ka \equiv 8 \pmod 9$?"2012-12-17
  • 0
    @N.S: Amusing! :) What if the number was 999999999900000000000090909090000000000000000004?2012-12-17
  • 0
    So we know that $9 \mid 99999\ldots00090909\ldots 0000$? I guess you could just factor out a 9....wow...I really need to learn to work better under pressure haha.2012-12-17
  • 1
    @Isomorphism That's why I said implies... If the number was what you said, that one needs to find a differenta approach, because that is a DIFFERENT problem ;)2012-12-17
  • 0
    @N.S. To apply your congruence to Isomorphism's new problem couldn't you just rewrite it as "Can $8^{k}a \equiv 4 (\mod 9)$"?2012-12-17
  • 0
    Okay so we have that $8^{k} \equiv (-1)^{k} \mod 9$ so the only two possible solutions to the congruence $8^{k}a \mod 9$ are $32 \equiv 5 \mod 9$ and $4 \mod 9$? (Meaning that the answer to Isomorphism's question is "yes" :-)2012-12-17
  • 0
    @Decave Nope, because the two problems are not equivalent. If the equation modulo $9$ has no solution, we get that the original equation has no solution. But if the equation modulo $9$ has solution, it doesn't imply that the original one has solution.2012-12-17
  • 0
    @Decave The fact that the equation has solution modulo $9$ only means that there exists some $a$ so that $8a^2=999999999900000000000090909090000000000000000004$ + multiple of $9$......2012-12-17
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6763/discussion-between-decave-and-n-s)2012-12-17
2

The largest power of $8$ that divides our number is $8^1$. Our number is not $(8)(31)$.

Note that the only thing that was used is that our number ends in $008$.

  • 0
    Also, the number is not divisible by $31$. It is, in fact, $8 \times 220654023912941 \times 566497713347021146672084609906661$ where the last two factors are primes.2012-12-17
  • 5
    But $31$ is further than I can comfortably count, even after taking my shoes off.2012-12-17