
%%%%%
%\includegraphics[width=2.05in,height=1.39in]{welcome.bmp}
%\input epsf
%\epsfverbosetrue
%\def\pict#1#2#3{\epsfxsize=#1in \epsfysize=#2in \epsffile{#3.eps}}
\documentclass[12pt]{article}
%\usepackage{amssymb,amsmath,amscd}
\usepackage{graphicx}
\setlength{\oddsidemargin}{-.5in}
\setlength{\evensidemargin}{-.5in}
\setlength{\textwidth}{7.25in}
\topmargin  -.7in
\textheight 9.45in
\newcommand{\bigfrac}[2]{\frac{\textstyle #1}{\textstyle #2}}
\newcommand{\starttest}{\begin{enumerate}}
\newcommand{\nextpage}{\vspace*{\fill}\newpage}

\newcommand{\mat}[2]{\left( \begin{array}{*{#1}{c}}#2\end{array}\right)}
\newcommand{\matr}[2]{\left( \begin{array}{*{#1}{r}}#2\end{array}\right)}
\newcommand{\dat}[2]{\left| \begin{array}{*{#1}{c}}#2\end{array}\right|}

\begin{document}

%\thispagestyle{empty}
\begin{center}
{\bf $\stackrel{\mbox{MA330}}{Sathaye}$ \hfill {\bf A universal divisibility test } \hfill \ \  }
\end{center}

Given below is a certain universal divisibility test invented by
Bh\={a}rat\={i} K\d{r}\d{s}\d{n}a T\={i}rtha, who claimed (in 1950's) that
he found it in ancient vedic scriptures. While the claim is very doubtful,
the test is a nice alteration of the usual modern techniques.

The test is for checking if a given natural number $n$ is divisible by a
given natural number $d>1$.
\begin{enumerate}
\item First assume that $d$ is coprime with $10$, since for numbers
having common factors with $10$, the possible common factors $2,5$ can be
factored out from $d$.
The divisibility test by $2$ is very easy: $n$ must be even,
i.e. the units digit is among $0,2,4,6,8$.

The divisibility test by $5$ is easier: $n$ must have the units digit $0$ or
$5$.

\item It is easy to find a number $m$ such that $10m \equiv s
\pmod{d}$, where $s$ is $1$ or $-1$. (See more details below.)
The resulting product $sm$ shall be called a multiplier for $d$.


Write $n=10u+v$.

\item Then the divisibility test says that $d|n=10u+v$ iff  $d|u+smv$.
The number $u+smv$ is usually much smaller than $n$ and we can repeat the
test until divisibility becomes evident.

\item Here is an illustration.

Let $d=13$. Note that $(3)13+1 = (4)10$, so we can take $s=1$ and $m=4$.
Start with $n=34351 = 10(3435)+1$, so $u=3435$ and $v=1$. So we can
replece $n=34351$ by $u+smv = 3435+(4)1 = 3439$. Taking $n=3439 = (10)343
+9$, we next replace it by $343+(4)9 = 379$. Next replacement shall be
$37+(4)9 = 73$ and this is easily seen to be not divisible by $13$.

Usually, we don't spend time in the arguments.

We start with a given $n$ and a given $d$.
Find a suitable multiplier $sm$.
Use it to reduce $n$ until divisibility is easy.

Here is another example with $d=23$.

$3(23)=69$, so $(7)10=1+(3)(23)$. Thus, we can take $s=1,m=7$. The
multiplier is $(1)(7)=7$.

Take $n=314452$. Here are the reductions:
$$314452 \rightarrow 31445+(2)(7) = 31459 \rightarrow 3145 + (7)(9)
=3208 \rightarrow 320+(7)(8) = 376 \rightarrow 37+(7)(6) = 79.$$

The last number is clearly not divisible by $23$. (You could make a
further reduction if you like:
$$79 \rightarrow 7+(7)(9) = 70 \rightarrow 7+(7)(0)=7.$$


\item Here are simple recipies for finding the $s,m$.

If $d$ ends in $1$, then write $d=10m+1$, which defines $m$ and let
$s=-1$. Example: $d=31 = 10(3)+1$ so $m=3,s=-1$ and multiplier is $-3$.

If $d$ ends in $3$, then write $3d +1 = 10m $, which defines $m$ and set
$s=1$. Example: $d=43$ so $3d +1 = 130 = 10(13)$ so $m=13,s=1, sm=13$.

If $d$ ends in $7$, then write $3d = 10m + 1$ thereby defining $m$ and
$s=-1$. Example: $d=37$ so $3d = 111 = 10(11)+1$ so $m=11,s=-1, sm=-11$.

If $d$ ends in $9$, then write $d+1 = 10m$ thereby defining $m$ and
$s=1$. Example: $d=29$ so $d +1 = 30 = 10(3)$ so $m=3,s=1,sm=3$.

The original recipe of Swamiji stated the following:

{\it Find a multiple of the chosen $d$ which ends in $9$. Take the part
of the number before $9$ and add $1$ to it. This is the multiplier
$sm$. For instance, when $d=17$, we have $(7)(17)=119$; the part before
$9$ is $11$ so the multiplier is $1+11=12$.}


\item Now you should practice using the above multipliers as well as
practicing making your own multipliers.

\item {\bf Proof of the test:} Note that by assumption $10sm \equiv s^2
=1$ modulo $d$. Now, $d|n=10+v$ iff $d|(sm)n = 10smu + smv $. This last
expression is congruent to $u+smv$ modulo $d$. Hence the test is proved!

\item This reproduces the usual tests for divibility by $3,9,11$ since
the values of $sm$ come out to be $1,1,-1$ in these cases respectively.
You should verify how this leads to the usual tests.

\item We give one more example for practice.
Take $d=17$. As shown above, the multiplier is $12$. This is also $-5$
modulo $17$, so we choose the smaller size multiplier.

Take $n=214457$.
Here is the work:
$$214457 \rightarrow 21445 - (5)7 =21410 \rightarrow 2141 \rightarrow
214 -(5)1 = 209 \rightarrow 20 - (5)9 = -25.$$
The last is clearly non divisible.

\end{enumerate}

\vspace*{\fill}
\end{document}
