Divisibility 2 – The Block Split Method

The Block Split Method

To derive the test of divisibility for n (a natural number), say we have this relation –

10^r \equiv\ k (mod n)

Let us take a natural number \underbrace{a_la_{l-1}\hdots a_{l-r}}_x\underbrace{a_{l-r-1}\hdots a_2a_1}_y. When will n | a_la_{l-1}\hdots a_2a_1? –

Interpret the number taken this way –

$latex a_{l}a_{l-1}\hdots a_2a_1= x\cdot 10^r +y$

If,

n|a_la_{l-1}\hdots a_2a_1

\implies n|10^rx+y

\implies kx+y \equiv\ 0 (mod n)

So we are done if the last congruence relation alone is checked.

Let us try applying this for certain simple cases –

Check for divisibility for 1001

Note that 10^3 \equiv\ -1 (mod 1001)

Let the number be \underbrace{XYZ}_p\underbrace{ABC}_q

Interpret the number as –

XYZABC = 10^3\cdot p + q

$latex 1001p + q – p$

Thus, essentially we can check the divisibility of the number XYZABC by checking the same for – ABC - XYZ.

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: