Divisibility test of N for integers 10x+y

In this note, we want to look at how a general divisibility test for $N$ could be obtained. For each $N$, we want to find a corresponding $n$ such that $ 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, $10 x + y$ is a multiple of 7 if and only if $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$ , and then checking $1235+14 = 1249$ and then checking $124 + 18 = 142$ and then checking $14 + 4 = 18$ , which we know is not a multiple of 7.

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

$\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~~~\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$

$\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}.$

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
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"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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

Also, for a given value of $N$ , what would the corresponding value of $n$ be? Why?

Calvin Lin Staff - 5 years, 11 months ago

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 - 5 years, 11 months ago

There's a simple one line proof of that.

$7\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 $\times 5$ part is for the forward direction and the $\div 5$ part is for the backward direction in the proof. Note that division by $5$ is well defined here since $\gcd(5,7)=1$ .

Prasun Biswas - 5 years, 11 months ago

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

$10x + y \equiv 0 \pmod {N} \Leftrightarrow x + 10^{-1} y \equiv 0 \pmod{N}$

@Calvin Lin – Ah, nice general result. :)

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

Thank so much. It is a lot of improvement .

Niranjan Khanderia - 5 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$