Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently familiar with the method of checking if a number is divisible by $2$, $3$, $4$, $5$, $6$, $8$, $9$, $10$, $11$. However is there a way to check if a no is divisible by $23$ ?

I read something at this link regarding this matter but couldn't really figure out what the author was trying to say. Any help in this regard would be appreciated. Thanks.

share|improve this question
    
This is a repeat; see also here. See in particular Bill Dubuque's answer to the latter –  Arturo Magidin Jun 21 '12 at 21:18
    
Looking closer, I don't think this is a duplicate, since it's referencing the reversed universal test, which hasn't been (explicitly) explained in the prior links. –  Bill Dubuque Jun 21 '12 at 22:59

4 Answers 4

up vote 2 down vote accepted

The idea behind "all those checkings" is to look at divisibility by computing the number you want to check divisibility modulo the divisor. For instance, the trick for computing divisibility by $11$ all reduces to $$ a \times 10^3 + b \times 10^2 + c \times 10 + d \equiv -a + b - c + d \pmod{11} $$ so that you can look at the alternated sum of the numbers instead of looking at the big one. You can develop a similar trick modulo $23$, for instance since $100 \equiv 8 \pmod {23}$, you have $$ a \times 100^2 + b \times 100 + c \equiv a \times 64 + b \times 8 + c \equiv a \times (-5) + b \times 8 + c \pmod {23}. $$ Perhaps the trick doesn't look quite as good, but that's because the tricks work well when the numbers are small or pretty (such as : it is easy to look at divisibility by $10000000000$).

Hope that helps,

share|improve this answer
    
@Mark : Thanks for the edit –  Patrick Da Silva Jun 22 '12 at 5:46

Here is the explanation to that link:

We know that $10 \cdot 7 = 70 \equiv 1 \mod 23$ as $3 \cdot 23 = 69$.

Thus, if we consider $10a + b \mod 23$ and we note that $7$ is coprime to $23$, then $10a + b \equiv 0 \mod 23 \iff 7(10a + b) = 70a + 7b \equiv a + 7b \equiv 0 \mod 23$

And that is how he got that $10a + b$ is divisible by $23$ iff $a + 7b$ is divisible by $23$. And this lets that blogger get rid of a digit, more or less, at each step to easily verify divisibility.

share|improve this answer
1  
+1 This explanation tacitly uses the fact that $7$ and $10$ are inverses modulo $23$. I bring it up because that leads to a way to generalize divisibility tests of this kind for different moduli. –  Jyrki Lahtonen Jun 21 '12 at 21:30

He shows that any integer of the form $10a + b$ is divisible by 23 if and only if $a + 7b$ is divisible by 23. So for a number $n$ with more than one digit, you can repeatedly replace it with the number $a + 7b$, where $b$ is the last digit of $n$, and $a$ is the rest.

In his example, we have $n = 146096$ and we can write it as $10 \cdot 14609 + 6$, i.e. $a = 14609$, $b = 6$, and therefore $n$ is divisible by 23 if and only if $7a + b = 7 \cdot 14609 + 6 = 14651$ is. And we just repeat this until we have a small enough number.

As you can see, this is not a very practical test because we still have to do those multiplications.

share|improve this answer

Hint $\rm\begin{eqnarray}\mod\ 23\!:\ \ 0&\equiv&\rm\, \ \ a\,10^3 + b\,10^2 + c\,10 + d \\ \iff\ 0 &\equiv&\rm\,(a\,10^3 + b\,10^2 + c\,10 + d)\,7^3 \\ \iff\ 0 &\equiv&\rm\ \ a\ \ \ \, +\, \, \ \ b\:7\ \, +\, \ c\:7^2 + d\ 7^3\quad by\quad 10\cdot 7\equiv 1\,\ (mod\ 23) \end{eqnarray}$

Now evaluate it mod $23\,$ as $\rm\ a + 7\,(b + 7\,(c + 7\,d))\ $ in Horner form as I explain in detail here. This is essentially the universal divisibility test applied to the reversed radix polynomial. It has the disadvantage that, while it correctly tests zero equivalence, it does not yield the actual remainder.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.