%p14S.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf Solutions to Attendance Quiz \# 14 for Dr. Z.'s Number Theory
Course for Oct. 24, 2013
}
\bigskip

{\bf 1.} Use Korslet's theorem to decide whether or not the following are
Carmichael numbers $1728$.

{\b Sol. to 1.}: $1728=2 \cdot 864= 2^2 \cdot 432$. This means that $1728$ is {\bf not} square-free
(it contains at least one prime ($2$) to a power higher than $1$. So the very first condition
to being a Carmichael number is wrong, so there is no way!

{\bf Ans. to 1}: $1728$ is {\bf not} a  Carmichael number.

{\bf 2.} Use the Fermat primality test to investigate whether the following integers are composite or probably primes

{\bf a.} $11$  \quad  {\bf b.} $10$  

{\bf Sol. to 2a}:  Let's pick $a=2$, and compute $2^{10} \pmod{11}$.
$$
2^1 \equiv 2 \pmod {11}
$$
$$
2^2 \equiv 2^2 \pmod {11} \equiv 4 \pmod {11}
$$
$$
2^4 \equiv 4^2 \pmod {11} \equiv 5 \pmod {11}
$$
$$
2^8 \equiv 5^2 \pmod {11} \equiv 3 \pmod {11}
$$
So
$$
2^{10}=2^8 \cdot 2^2 = 3 \cdot 4 \equiv 1 \pmod{11} \quad .
$$
Hence $11$ is {\bf probably a prime}. If you want to be more sure, then try other $a$'s.

{\bf Note:} Of course, we know already that $11$ is prime for sure. This is just to familiarize ourselves
with the method. In real life computers apply it to very large integers.



{\bf Sol. to 2b}:  Let's pick $a=2$, and compute $2^{0} \pmod{10}$.
$$
2^1 \equiv 2 \pmod {10}
$$
$$
2^2 \equiv 2^2 \pmod {10} \equiv 4 \pmod {10}
$$
$$
2^4 \equiv 4^2 \pmod {10} \equiv 6 \pmod {10}
$$
$$
2^8 \equiv 6^2 \pmod {10} \equiv 6 \pmod {11}
$$
So
$$
2^{10}=2^8 \cdot 2^2 = 6 \cdot 4 \equiv 4 \pmod{10} \quad .
$$
Since this is {\bf not} $1$, we know {\bf for sure} that $n=10$ is composite.


\end





