0
$\begingroup$

I'm a bit lost / behind in my number theory class, but hey what can I do but try to catch up.

I'm asked to find the remainder in division by $m= 3,7,9,11,13$ using divisbility tests for $1234567 \times 10^{89}$

For division by 3 (and 9), I know that the sum of the digits must be divisible by 3 (or 9).

Immediately it follows that both 3 and 9 do not divide our monster number. To find the remainder, this is what I did though I'm not sure if I am correct.

$28 \equiv 1 \mod 3$ and so I say that the remainder in division by 3 of $1234567 \times 10^{89}$ is 1.

For 7,11,13 I see that $123 - 456 + 700 = 367$ and that none of 7,11,13 divide 367.

This is where I'm stuck -- the test is developed using the fact that $7*11*13 = 1001$ and $1000 \equiv -1 \mod 1001$.

Do i set $367 \equiv x \mod 143$ ? Or is the remainder in division from 7,11 and 13 all $367 \mod 1001$?

$\endgroup$
2
  • $\begingroup$ Are you required to compute the remainder, or merely to test for divisibility? (as you seem to be doing). $\endgroup$ – Bill Dubuque Aug 4 '14 at 2:49
  • $\begingroup$ I need to find the remainder using facts from the divisibility tests. $\endgroup$ – David D. Aug 4 '14 at 2:50
2
$\begingroup$

I assume you haven't talked about algorithms yet, and it is just for practice of the basic concepts? You can try breaking it up in a product of prime numbers, since $10^{89}=(2\times 5) \times (2\times 5) \times ...\times(2\times 5)$ and $1234567$ isn't that big a number.

(This answer would be better as a comment, but i do not have enough rep so...)

$\endgroup$
2
$\begingroup$

Hint $\ n\equiv a\pmod{\color{#0a0}{\!7\cdot11\cdot 13}}\,\Rightarrow\, n\equiv a \pmod{\color{#c00}7},\,$
because $\ \ \ \ \, a\, +\, (\color{#0a0}{7\cdot 11\cdot 13})\,k\, =\, a\, +\, \color{#c00}7\:(11\cdot 13 k),\ $ or note $\ 7j\mid n\!-\!a\,\Rightarrow\, 7\mid n\!-\!a.$
Similarly for the moduli $\,11,\, 13.$

By casting nines, an integer is congruent to its digit sum mod $3,9,\,$ by $\,10\equiv 1\,\Rightarrow\,10^n\equiv 1$.

Compute $10^{89}$ via $\,10\equiv 1,$ mod $3,9,\,$ and $\,10^3\equiv 1$ mod $\,7,11, 13\,$ (as you remark)

$\endgroup$

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.