%\batchmode
\documentclass[12pt]{article}
\topmargin -0.5in
\pagestyle{empty}
\oddsidemargin 0pt
\textwidth 6.7in
\textheight 9.5in
\newcommand{\binom}[2]{{#1\choose #2}}
\newcommand{\bigfrac}[2]{\frac{\textstyle #1}{\textstyle #2}}
   	\def\bbd#1{\leavevmode\setbox0=\hbox{#1}%
   	\kern-.025em\copy0 \kern-\wd0
   	\kern .05em\copy0 \kern-\wd0
  	\kern-.025em\raise.0433em\box0
  	}
   	\def\nexto{\kern -0.54em}
    	\def\DN{ \mbox{\rm {I\ \nexto N}} }
    	\def\DZ{ \mbox{\rm Z \kern -0.82em Z} }
    	\def\DC{ \mbox{\rm\hbox{C \kern-0.8em\raise0.2ex
    	\hbox{\vrule height5.4pt width0.7pt} \kern0.45em}} }
    	\def\DQ{ \mbox{\rm\hbox{Q \kern-0.85em\raise0.25ex
    	\hbox{\vrule height5.4pt width0.7pt} \kern0.45em}} }
    	\def\DP{ \mbox{\rm\hbox{P\kern-0.75em
	\hbox{\vrule height9pt width0.7pt} \kern0.45em}} }
%\input epsf
%\epsfverbosetrue
%\def\pict#1#2#3{\epsfxsize=#1in \epsfysize=#2in \epsffile{#3.eps}}


\begin{document}

	\begin{center}
{\bf $\stackrel{\mbox{MA330 (Sathaye)}}{\mbox{\bf(140405)}}$
\hfill  Quiz 4\hfill    Name:\rule{2in}{0.01in}  }
	\end{center}
%\hfill \rule{6in}{0.01in}\hfill
{\bf This is a take-home quiz.
It should be submitted on or before Wednesday April 9.}


\begin{enumerate}
\item
Develop a divisibility test by $23$ patterned after Bh\={a}rat\={i}
K\d{r}sh\d{n}a's method. Explicitly state what multiplier you obtain.

%Illustrate how the test works by testing a couple of small numbers.

Decide if $2452559$ is divisible by $23$ using the test.

Decide the divisibility of a comparably large number of your choice by
the same test.

\item Develop a divisibility test by $37$ patterned after Bh\={a}rat\={i}
K\d{r}sh\d{n}a's method. Explicitly state what multiplier you obtain.

Illustrate with a couple of fairly large numbers of your choice.

\item Work out the factorization technique of N\={a}r\={a}ya\d{n}a to factor the number:
$n=259$.

Illustrate the technique with two more three digit numbers of your choice.

For your information, the technique is described here.

Start with a number $n$ which is odd. (Also a factor of $5$ is easy to note and remove, so assume $5$ does not divide $n$.)
We illustrate with $n=203$.

\begin{itemize}
\item Start with a least choice of $t$ such that $t^2>n$.
Set $s=t^2-n$.

Thus for $n=203$, we start with $t=15, s=22$.

\item Check if $s$ is a square. This can be done from a table of squares, or using a calculator. 

If $s=y^2$, then $n=t^2-y^2$, so we have a factorization $n=(t-y)(t+y)$.
Declare ``Success''!!

For our example, $22$ is a non square, so continue.

\item If there is no success, then replace $s$ by $s+2t+1$ and then replace  $t$ by $t+1$. Check again.

We change $(t,s)$ to $(15+1,22+2(15)+1)=(16,53)$. Since $53$ is a non square, we repeat the process and get 
$(t,s)=(17,86)$. Repeating the step, we get $(t,s) = (18,121)$.

Thus $203 = 18^2 - 11^2 = (7)(29)$.

\item When do we conclude that $n$ must be a prime? This happens if $t-y=1$ i.e. $t+y=n$ where $y^2=s$. 
\end{itemize}

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



