%p15S.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 the Attendance Quiz \# 15 for Dr. Z.'s Number Theory
Course for  Oct. 28, 2013
}
\bigskip

{\bf 1.} Using the definition, find  $\phi(12)$ .

{\bf Sol. of 1}: 
$$
gcd(1,12)=1 \quad , \quad
gcd(2,12)=2 \quad , \quad
gcd(3,12)=3 \quad , \quad
gcd(4,12)=4 \quad , \quad
gcd(5,12)=1 \quad , \quad
$$
$$
gcd(6,12)=6 \quad , \quad
gcd(7,12)=1 \quad , \quad
gcd(8,12)=4 \quad , \quad
gcd(9,12)=3 \quad , \quad
gcd(10,12)=2 \quad , \quad
$$
$$
gcd(11,12)=1 \quad , \quad
gcd(12,12)=12 \quad .
$$
The set of integers relatively prime to $12$ is: $\{ 1, 5, 7, 11 \}$.
Since its number of elements is $4$, we have:

{\bf Ans. to 1}: $\phi(12)=4$ .

{\bf 2.} Using the formula, find  $\phi(1500)$.

{\bf Sol. to 2}: We first do a {\bf prime-power factorization}:
$$
1500= 15 \cdot 100= 3 \cdot 5 \cdot (2 \cdot 5)^2= 2^2 \cdot 3 \cdot 5^3 \quad .
$$
So
$$
\phi(1500)=
(2^2 \cdot 3 \cdot 5^3 ) \cdot (1- \frac{1}{2}) (1- \frac{1}{3}) (1- \frac{1}{5})
$$
$$
= (2^2 \cdot 3 \cdot 5^3 ) \cdot (\frac{1}{2}) (\frac{2}{3}) (\frac{4}{5})
$$
$$
= (2^1 \cdot 3^0 \cdot 5^2 ) \cdot (1 \cdot 2 \cdot 4)
$$
$$
= (50) (8)= 400 \quad .
$$

{\bf Ans. to 2}: $\phi(1500)=400$.

\end











