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{red}{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 \impliesx- 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{red}{10^{-1} \pmod {N}.} \\ 10x + y\equiv 0 \pmod {N} \Leftrightarrow x+10^{-1}y\equiv 0 \pmod {N}.\)

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestThank so much. It is a lot of improvement .

Log in to reply

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?

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.

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply