Divisibility test of N for integers 10x+y

In this note, we want to look at how a general divisibility test for NN could be obtained. For each NN, we want to find a corresponding nn such that N10x+yNx+ny N \mid 10x + y \Leftrightarrow N \mid x + n y .

This is a generalization of the famous divisibility test of 7, in which we multiply the last digit by 2 and then add it to the rest of the number. Namely, 10x+y 10 x + y is a multiple of 7 if and only if x+2y x + 2y is a multiple of 7. This gives us a quick way to find if the number 123456 is a multiple of 7, by checking 12345+12=12357 12345+12 = 12357, and then checking 1235+14=1249 1235+14 = 1249 and then checking 124+18=142 124 + 18 = 142 and then checking 14+4=18 14 + 4 = 18 , which we know is not a multiple of 7.

Let number be 10x+y\color{#D61F06}{10x + y}, e.g. 93468 as 109346+810 * 9346 + 8, so x=9346x=9346 and y=8y=8 .

Nn\quad \quad N \quad\quad\quad\quad \quad \quad n .

7:~~~ 10x + y~~~ \implies~~~x+5y~~~.... n=5.\\~~~~~~~~ OR~~~ 10x + y \impliesx- 2y ~~~....n=-2\\~~~~~~~~ OR ~~~~~~~~ \text{ 10x + y has the same remainder when divided by 7 as 3x + y.} \\ ~~~~~~~~Say~~ 371:~~~ 3×3 + 7 = 16~ remainder~ 2,~ and~ 2×3 + 1 = 7.~\therefore 7|371.
13:   10x+y          x+4y     n=417:   10x+y          x+5y     n=519:   10x+y          x+2y     n=223:   10x+y          x+7y     n=729:   10x+y          x+3y     n=331:   10x+y          x3y     n=337:    10x+y          x+11y     n=1141:   10x+y          x4y     n=443:   10x+y          x+13y     n=1347:   10x+y          x14y     n=1453:   10x+y          x+16y     n=1659:   10x+y          x+6y     n=613:~~~10x + y~~~\implies~~~x+4y~~~~~n=4\\ 17:~~~10x + y~~~\implies~~~x+5y~~~~~n=5\\19:~~~10x + y~~~\implies~~~x+2y~~~~~n=2\\23:~~~10x + y~~~\implies~~~x+7y~~~~~n=7\\29:~~~10x + y~~~\implies~~~x+3y~~~~~n=3\\31:~~~10x + y~~~\implies~~~x-3y~~~~~n=-3\\37: ~~~~ 10x + y~~~\implies~~~x+11y~~~~~n=11\\41:~~~10x + y~~~\implies~~~x-4y~~~~~n=-4\\43:~~~10x + y~~~\implies~~~x+13y~~~~~n=13\\47:~~~10x + y~~~\implies~~~x-14y~~~~~n=- 14\\53:~~~10x + y~~~\implies~~~x+16y~~~~~n=16\\59:~~~10x + y~~~\implies~~~x+6y~~~~~n=6

To illustrate , Test 41|2829:-x=282, y=9 and for 41, n=4. 282-4 * 9=246 . Repeat for 246. 24-4 * 6=0 so 41|246.Repeat several times for a big number.Say   4128648914    x=2864891, y=4,   286489144=2864875,x=286487,y=5,   28648745=286467,x=28646,y=7,   2864647=28618,x=2861, y=8,   286148=2829,x=282, y=9,,   28249=246,x=24, y=6,,   2446=0.  Note, final result will be 0 if the number is divisible.  4128648914.   I am adding Calvin Lin’s comment below. It is nice general result.For given value of N that satisfies gcd(N,10) = 1,corresponding value of n is just 101(modN).10x+y0(modN)x+101y0(modN). \text{To illustrate , Test 41|2829:-x=282, y=9 and for 41, n=4.}\\ \therefore \text{ 282-4 * 9=246 . Repeat for 246. 24-4 * 6=0 so 41|246.}\\\text{Repeat several times for a big number.}\\Say~~~41|28648914~~~~\\x=2864891, ~y=4,~~\therefore~2864891-4*4=2864875,\\x=286487, y=5,~~\therefore~286487-4*5=286467, \\x=28646, y=7,~~\therefore~28646-4*7=28618,\\x=2861, ~y=8 ,~~\therefore~2861-4*8=2829,\\x=282, ~y=9, ,~~\therefore~ 282-4*9=246,\\x=24,~y=6,,~~\therefore~24-4*6=0.~~\\\text{Note, final result will be 0 if the number is divisible.}\\\therefore ~~41|28648914 . \\~~ \\ \text { I am adding Calvin Lin’s comment below.} \\ \text { It is nice general result.} \\\text {For given value of N that satisfies gcd(N,10) = 1,} \\ \text{corresponding value of n is just } \color{#D61F06}{10^{-1} \pmod {N}.} \\ 10x + y\equiv 0 \pmod {N} \Leftrightarrow x+10^{-1}y\equiv 0 \pmod {N}.

Note by Niranjan Khanderia
4 years, 1 month ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Do you know why this is true? IE 710x+y7x+5y 7 \mid 10x + y \Leftrightarrow 7 \mid x + 5y ?

Also, for a given value of NN , what would the corresponding value of nn be? Why?

Calvin Lin Staff - 4 years, 1 month ago

Log in to reply

Yes. From theory of numbers, we can see why it works. But these are simple short cut notes. Is it of much use now with our calculator?? But for solving related problem, we may just use it in stead of going into full proof. Just like saying rationalize the denominator and put the result with out intermediate steps.

Niranjan Khanderia - 4 years, 1 month ago

Log in to reply

There's a simple one line proof of that.

710x+y    10x+y0(mod7)    ÷5×550x+5y0(mod7)    x+5y0(mod7)    7x+5y7\mid 10x+y\iff 10x+y\equiv 0\pmod{7}\overset{\times 5}{\underset{\div 5}{\iff}} 50x+5y\equiv 0\pmod{7}\iff x+5y\equiv 0\pmod{7}\iff 7\mid x+5y

The ×5\times 5 part is for the forward direction and the ÷5\div 5 part is for the backward direction in the proof. Note that division by 55 is well defined here since gcd(5,7)=1\gcd(5,7)=1.

Prasun Biswas - 4 years, 1 month ago

Log in to reply

@Prasun Biswas Great! So, for a given value of NN which satisfies gcd(N,10)=1 \gcd (N, 10 ) = 1 , the corresponding value of nn is just 101(modN) 10 ^ { - 1} \pmod{N} .

10x+y0(modN)x+101y0(modN) 10x + y \equiv 0 \pmod {N} \Leftrightarrow x + 10^{-1} y \equiv 0 \pmod{N}

Calvin Lin Staff - 4 years, 1 month ago

Log in to reply

@Calvin Lin Ah, nice general result. :)

Prasun Biswas - 4 years, 1 month ago

Log in to reply

@Calvin Lin Thank you for a short simple general result. I am adding it to my notes as a comment from you. Thanks a lot for editing the note to make it more understandable.

Niranjan Khanderia - 4 years, 1 month ago

Log in to reply

Thank so much. It is a lot of improvement .

Niranjan Khanderia - 3 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...