# Remainder in Division using divisibility tests

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

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

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.
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)