%begin macros
%\magnification=\magstephalf
\magnification=\magstep1
\def\g{\bigtriangledown}
\def\L{{\cal L}}
%\baselineskip=14pt
%\parskip=10pt
\def\Tilde{\char126\relax}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\nopagenumbers
%end macros

\bigskip
{\bf Solutions to MATH 356, Dr. Z. ,  Exam 2, Tue., Nov. 26, 2024
8:30-9:50am SEC-204}
\bigskip
{\bf No Calculators! No Cheatsheets!}

{\bf 1}. (10 pts.)  

 Using the formula,
find the unique $x$ between $0$ and $2001$ such that
$$
x \equiv 1 \pmod {2} \quad , \quad
x \equiv 5 \pmod {7} \quad , \quad
x \equiv 6 \pmod {11} \quad , \quad
x \equiv 4 \pmod {13} \quad .
$$

{\bf Reminder}  (Chinese Remainder Theorem, General Version)
If $n_1, n_2, \dots, n_k$ are pairwise
relatively prime 
(i.e. $gcd(n_i,n_j)=1$, $1 \leq i<j \leq k$), then
the unique $x$ , $0 \leq x < n_1 \cdots n_k$ satisfying
$$
x \equiv a_i \pmod{n_i} \quad , \quad 1 \leq i \leq k 
$$
is (letting $N=n_1 \cdots n_k$)
$$
x= \sum_{i=1}^{k} a_i \frac{N}{n_i} 
\cdot \left ( (\frac{N}{n_i})^{-1} \pmod {n_i} \right )
$$


\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   1447
\bigskip
\bigskip
\bigskip
\hrule
\bigskip

We have

$$
x=
 1 \cdot (7 \cdot 11 \cdot 13) \cdot \left ( (7 \cdot 11 \cdot 13)^{-1} \pmod 2\right )
+ 5 \cdot (2 \cdot 11 \cdot 13) \cdot \left ( (2 \cdot 11 \cdot 13)^{-1} \pmod 7\right )
$$
$$
+ 6 \cdot (2 \cdot 7 \cdot 13) \cdot \left ( (2 \cdot 7 \cdot 13)^{-1} \pmod{11}\right )
+ 4 \cdot (2 \cdot 7 \cdot 11) \cdot \left ( (2 \cdot 7 \cdot 11)^{-1} \pmod{13}\right )
$$

$$
=
 1 \cdot (1001) \cdot \left ( (1001)^{-1} \pmod 2\right )
+ 5 \cdot (286)               ) \cdot \left ( 286^{-1} \pmod 7\right )
$$
$$
+ 6 \cdot (182) \cdot \left ( (182)^{-1} \pmod {11}\right )
+ 4 \cdot (154) \cdot \left ( (154)^{-1} \pmod {13}\right )
$$
$$
=
 1 \cdot (1001) \cdot \left ( (1)^{-1} \pmod 2\right )
+ 5 \cdot (286)               ) \cdot \left ( (-1)^{-1} \pmod 7\right )
$$
$$
+ 6 \cdot (182) \cdot \left ( 6^{-1} \pmod {11}\right )
+ 4 \cdot (154) \cdot \left ( (-2)^{-1} \pmod {13}\right )
$$

By inspection
$$
6^{-1} \pmod {11}=2 \quad, \quad
2^{-1} \pmod {13}=7 \quad, \quad
$$
Hence

$$
x=
 1 \cdot (1001) \cdot (-1)
+ 5 \cdot (286)\cdot (-1)
+ 6 \cdot (182) \cdot 2
+ 4 \cdot (154) \cdot (-7)=
$$
$$
(1001-1430+2184-4312) \pmod {2002}
=
(1001-1430+182-308) \pmod {2002}=
1447 \quad.
$$


\vfill\eject


{\bf 2}. (10 pts.)   What is the day of the week of Nov. 26, 3024.

{\bf Reminders:} Every year that is a multiple of $4$ is a leap year, with the exception that every year that is a multiple of $100$ is {\bf not} a leap year,
with the exception to the exception that if the year is a multiple of $400$ it {\bf is} a leap year.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   Friday
\bigskip
\bigskip
\bigskip
\hrule
\bigskip

There are $1000$ years from now, and $250-10+2=242$ leap years. Today is day $3$ so
$$
3 + 1000+242 \pmod 7=
3 + 6+4 \pmod 7=13 \pmod 7 =6 \quad.
$$

\vfill\eject


{\bf 3}. {\bf a} (5 pts.)  What is is the remainder when you divide $102!$ by 103? Explain! What theorem are you using?
\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $-1$ alias $102$
\bigskip
\bigskip

\hrule
\bigskip
Wilson's theorem claims that if $p$ is a prime then $(p-1)! \pmod p=-1$. Since $103$ is a prime, this follows.


{\bf b} (5 pts.)  What is is the remainder when you divide $11^{1002}$ by $1003$? What theorem are you using?
\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $1$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
Pascal's identity says
$$
a^{p-1} \pmod p =1 \quad,
$$
if $a \neq 0$. Since $1003$ is a prime, it follows.

\vfill\eject


{\bf 4}. {\bf a} (3 pts.)   Define Euler's Toitent function $\phi(n)$.

$\phi(n)$ is the numebr of positive integers less than $n$ that are relatively prime to $n$.

{\bf b} (7 pts. altogether)

State (2 pts.) and prove (5 pts), Euler's Classical Formula for  Euler's Toitent function $\phi(n)$.

(a)
$$
\sum_{d|n} \phi(d) = n \quad
$$

(b)
Write all the $n$ fractions with denominator $n$ and numerators from $1$ to $n$
$$
\frac{1}{n}, \frac{2}{n},  \dots, \frac{n}{n} \quad
$$
Now {\it reduce} them so that the top and bottom are relatively primes.
The denominators that show up at the bottom are all divisors of $n$, and for each such divisor $d$, all the integers relatively prime to $d$ show up.
There are $\phi(d)$ of them. Adding them up gives $n$.

\vfill\eject


{\bf 5}. (10 pts.)  

Using the RSA encrypton method, with   $p=5 \quad , \quad q=11 \quad , \quad e=7$ , Alice sent you the encripted message $c=2$
what was her original message $m$?


\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $m=8$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip

$n=5 \cdot 11=55$, $\phi(n)=(5-1) \cdot (11-1)=40$; $gcd(7,40)=1$, so $e=7$ is an OK key.
We need to find d
$$
d= 7^{-1} \pmod 40=23 \quad
$$

(either by trial-and-error or the Extended Euclidean algorithm applied to $gcd(40,7)$
$$
{\bf 40}= 5 \cdot {\bf 7}+ 5 \quad ; \quad 5={\bf 40} - 5 \cdot {\bf 7}
$$
$$
{\bf 7}= 1 \cdot 5 +2 \quad;\quad 2= {\bf 7} -5=6 \cdot {\bf 7} -{\bf 40}
$$
$$
5=2 \cdot 2 +1 \quad; \quad 1=5-2\cdot 2= ={\bf 40} - 5 \cdot {\bf 7} - 2(6 \cdot {\bf 7} -{\bf 40})= 3 {\bf 40} -17 {\bf 7}
$$
Taking mod $40$
$$
7^{-1} \pmod 40= -17 \pmod {40}=23
$$

So 
$$
m=c^{23} \pmod 40=2^{23} \pmod {40}
$$
$$
2^1=2 \quad; \quad
2^2=4 \quad; \quad
2^4=16 \quad; \quad
2^8=16^{2} \pmod 40= 16 \quad; \quad
$$
$$
2^{16}=16^{2} \pmod 40= 16 \quad; \quad
$$
Hence
$$
2^{23} \pmod 40= 2^{16+4+2+1} \pmod 40= 16 \cdot 16 \cdot 4 \cdot 2 \pmod 40= 8 \quad .
$$
\vfill\eject


{\bf 6}. (10 pts., 2 pts. each)  What are $\sigma(105)$, $\sigma_2(105)$, $\sigma_3(105)$, $\sigma_4(105)$, $\sigma_5(105)$?

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   
$\sigma(105)=192$
\bigskip
$\sigma_2(105)=(1+3^2)(1+5^2)(1+7^2)=13000$,
\bigskip
$\sigma_3(105)=(1+3^3)(1+5^3)(1+7^3)$
\bigskip
$\sigma_4(105)=(1+3^4)(1+5^4)(1+7^4)$ 
\bigskip
$\sigma_5(105)=(1+3^5)(1+5^5)(1+7^5)$ 

\bigskip
\bigskip
\hrule
\bigskip
The prime factorization  of $105$ is
$$
105=3 \cdot 5 \cdot 7 \quad.
$$
\vfill\eject


{\bf 7}. (10 pts., 5 pts. each)  Find {\bf (a):} $\mu(2002)$ {\bf (b):} $\mu(4004)$. Explain!


\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  (a) $1$ 
\bigskip
{\bf a:}  
\bigskip
{\bf b:}  $0$
\bigskip

\bigskip
\bigskip
\bigskip
\hrule
\bigskip

$2002=2 \cdot 7 \cdot 11 \cdot 13$ is a product  {\bf four} distinct primes, hence $\mu(2002)=(-1)^4=1$

$4004=2^2 \cdot 7 \cdot 11 \cdot 13$ is {\bf not} a product  of distinct primes, hence $\mu(4004)=0$

\vfill\eject


{\bf 8}. (10 pts.)  Is $17$ a quadratic residue modulo $281$? Explain!
\bigskip
{\bf Reminders:}

{\bf Rule 1}: If $p$ is an odd prime and $a$ and $b$ are  not multiples of $p$, then
$$
\left ( \frac{ab}{p} \right ) = \left ( \frac{a}{p} \right ) \cdot \left ( \frac{b}{p} \right )
$$

{\bf Rule 2}: If $p$ is an  odd prime then
$$
\left ( \frac{-1}{p} \right ) =  (-1)^{(p-1)/2} \quad .
$$

{\bf Rule 3}: If $p$ is an  odd prime then
$$
\left ( \frac{2}{p} \right ) =  (-1)^{(p^2-1)/8} \quad .
$$


{\bf Rule 4}: ({\bf THE QUADRATIC-RECIPROCITY LAW})

If $p$ and $q$ are distinct odd primes, then
$$
\left ( \frac{p}{q} \right ) \left ( \frac{q}{p} \right ) = (-1)^{(p-1)(q-1)/4} \quad .
$$



\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  Yes; $17$ is a quadratic residue of $281$.
\bigskip
\bigskip
\bigskip
\hrule
\bigskip
$\left ( \frac{17}{281} \right ) \left ( \frac{281}{17} \right ) = (-1)^{280)(16)/4}=1$ 


But $281 \pmod 17=9$, hence

$\left ( \frac{17}{281} \right ) \left ( \frac{9}{17} \right ) = 1 $


So
$$
\left ( \frac{17}{281} \right ) =  \left ( \frac{9}{17} \right )
=  \left ( \frac{3\cdot 3}{17} \right )=
=  \left ( \frac{3}{17} \right )^2 =1 \quad.
$$
Since the Legendre symbol  $\left ( \frac{p}{q} \right )$ is either $1$ or $-1$ its square is always $1$. So we don't need to know
 $\left ( \frac{3}{17} \right )$

\vfill\eject


{\bf 9}. (10 pts.)   For the following partitions $\lambda$, (i) Draw the Ferrers graph (ii) Find the conjugate partition $\lambda'$.

$$
\lambda=(7,5,5,3,2,1,1,1)
$$


(i)

$$
\matrix{ * & * & * & * & * & * & * \cr
         * & * & * & * & * \cr
         * & * & * & * & * \cr
         * & * & *   \cr
         * & * & *   \cr
         *    \cr
         *    \cr
         *    \cr
}\quad .
$$
\quad
(ii) $(8,5,4,3,3,1,1)$

\vfill\eject


{\bf 10}. (10 pts. altogether)  

\bigskip
{\bf i.} (5 pts) Apply Glashier's bijection (in the distinct $\rightarrow$  odd direction)
to the distinct partition $(8,6,3,2,1)$ to get an partition, call it $\mu$

$$
8=8 cdot 1 \quad; \quad
6=2 \cdot 3 \quad; \quad
3=1 \cdot 3 \quad; \quad
2=2 \cdot 1 \quad; \quad
1=1 \cdot 1 \quad.
$$
\bigskip
This becomes $1^8, 3^2, 3^1, 1^2, 1^1$

Combining, we get $1^{11} 3^3$ and in the usual notation
$$
\mu=(3,3,3,1,1,1,1,1,1,1,1,1,1,1) \quad
$$
{\bf ii.} (5 pts.) Apply Glashier's bijection  (in the odd $\rightarrow$ distinct direction) to the 
partition $\mu$ and show that you get  $(8,6,3,2,1)$ back, as you should.

$$
(3^3, 1^{11})= (3^{2+1}, 1^{8+2+1})= (6,3.8,2,1)
$$
Putting it in order, we get that indeed the reverse mapping gives $(8,6,3,2,1)$


\end