

%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

\medskip
{\bf NAME: (print!)}  Hristo MOLNAR
\bigskip
 {\bf E-Mail address:}  \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

\bigskip
{\bf MATH 356, Dr. Z. ,  Make Up Final Exam, Mon., Jan. 27, 2025, 3:00-6:00pm, Hill 704}
\bigskip
\bigskip
Do not write below this line (office use only)
\medskip
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\medskip
1. \qquad  (out of 10)    
\medskip
2.  \qquad  (out of 10)    
\medskip
3.   \qquad (out of 10)    
\medskip
4.   \qquad (out of 10)    
\medskip
5.   \qquad (out of 10)    
\medskip
6.    \qquad (out of 10)    
\medskip
7.    \qquad (out of 10)   
\medskip
8.    \qquad (out of 10)    
\medskip
9.    \qquad (out of 10)    
\medskip
10.    \qquad (out of 10)    
\medskip
11.    \qquad (out of 10)    
\medskip
12.    \qquad (out of 10)    
\medskip
13.    \qquad (out of 10)    
\medskip
14.    \qquad (out of 10)    
\medskip
15.    \qquad (out of 10)    
\medskip
16.    \qquad (out of 10)    
\medskip
17.    \qquad (out of 10)    
\medskip
18.    \qquad (out of 10)    
\medskip
19.    \qquad (out of 10)    
\medskip
20.    \qquad (out of 10)    
\medskip
------------------
\medskip
tot.: \qquad \qquad (out of 200)    

\vfill\eject


{\bf 1.}
Find the unique $x$ between $0$ and $1019$ such that

$$
x \equiv 5 \pmod {20} \quad , \quad
x \equiv 5 \pmod {51} \quad .
$$
\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $x=$
\bigskip
\bigskip
\bigskip
\hrule

\vfill\eject

{\bf 2}. (10 pts.) Prove that if you take any 3-digit positive integer written in decimal positional notation
(as usual!)
$$
i_2 \, i_1 \, i_0 \quad , \quad ( 1 \leq i_2 \leq 9 \quad, \quad 0 \leq i_1 \leq 9 \quad , \quad 0 \leq i_0 \leq 9 \quad ) .
$$
then the 6-digit decimal integer obtained by repeating it (for example, if you take $395$ you make $395395$), namely
$$
i_2 \, i_1 \, i_0 \, i_2 \, i_1 \, i_0  \quad , 
$$
is divisible by $7$.

\vfill\eject


{\bf 3}. (10 pts.) State Wilson's theorem, and verify it empirically for $p=17$.

\vfill\eject


{\bf 4}. (10 pts.)  Use the Fermat primality test to investigate
whether $13$ is prime or composite by picking {\bf two} random $a$'s between $2$ and $12$


\vfill\eject


{\bf 5}. (10 pts.)  Compute $\phi(10^{10})$ . You can leave the answer in facored form. Explain!

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:   $\phi(10^{10})=$
\bigskip
\bigskip
\bigskip
\hrule

\vfill\eject


{\bf 6}. (10 pts.)  Suppose Alice used RSA to send you the encrypted message $c$, using the public key $e$ that
you gave her.  Check that this is an OK message (coprime to $n=pq$). Also check that the key is a valid key.
If they are both OK,  find her original message?, $m$.
$$
p=11 \quad , \quad q=13 \quad , \quad e=7 \quad , \quad c=3 \quad .
$$

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

\vfill\eject


{\bf 7}. (10 pts.)  Prove that  for every positive integers $n$ and $k$, the number of partitions of $n$ with exactly $k$ parts
equals the number of partitions of $n$ with largest part $k$.

\vfill\eject


{\bf 8}. (10 pts.)   State and prove Fermat's Little Theorem.

\vfill\eject

KA
{\bf 9}. (10 pts.)  What is $\mu(2002)$? ($\mu(n)$ is the famous M\"obius function).
\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $\mu(2002)=$
\bigskip
\bigskip
\bigskip
\hrule


\vfill\eject


{\bf 10}. (10 pts.) 
Decide whether $121$ is a quadratic residue modulo $1001$. Explain.

  
\bigskip
\hrule
\bigskip
\bigskip
{\bf Ans.}:  $121$  \qquad is/ is not \qquad a quadratic residue mod $1001$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip

\vfill\eject

{\bf 11}. (10 pts)   Apply the famous Bressoud-Zeilberger map to the pair 
$$
\lambda=(7,5,3,2,2,2,1,1,1) \quad , \quad j=2 \quad .
$$
Call the output $(\lambda', j')$. Then apply it to the output, and show that you get $(\lambda,j)$ back.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $\lambda' \, =$  \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad  $j'=$
\bigskip
\bigskip
\bigskip
\hrule
\bigskip

{\bf Reminder}: {\eightrm Let $\lambda=(\lambda(1), \dots, \lambda(t))$, where $t$ is the number of parts.
If $t+3j \geq \lambda(1)$ then $\lambda'=(t+3j-1, \lambda(1)-1, \dots, \lambda(t)-1)$ 
(erasing all zeros at the end, of course), and $j'=j-1$. Otherwise
$\lambda'=(\lambda(2)+1 , \dots, \lambda(t)+1, 1^{\lambda(1)-3j-t-1})   $, and $j'=j+1$.}

\vfill\eject

{\bf 12}. (10 pts.)   Apply Franklin's bijection to the distinct partition 
$\lambda=(15,14,13)$, if it is applicable. 
If it is indeed applicable, call the output $\lambda'$, and apply
Franklin's bijection to $\lambda'$ and show that you get $\lambda$ back.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $\lambda'=$
\bigskip
\bigskip
\bigskip
\hrule


\vfill\eject

{\bf 13}. (10 pts.)  What is the day of the week on Jan. 27, 9025 . Explain!



\vfill\eject

{\bf 14}. (10 pts.)    Convert $\frac{11}{77}$ into a simple continued fraction.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $\frac{11}{77}=$
\bigskip
\bigskip
\bigskip
\hrule


\vfill\eject

{\bf 15}. (10 pts.)    Evaluate the infinite continued fraction $x=[5,1,1,1,1,, \dots]$
(i.e. $x=[5,(1)^{\infty}]$ that starts with $5$ followed by $1$ repeated an infinite number of times)
as a quadratic irrationality.

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  $x=$
\bigskip
\bigskip
\bigskip
\hrule


\vfill\eject

{\bf 16.} (10 pts.) In Planet $Z$ there are $10$ days in the week, and
the year-length is always the same (no leap years!), consisting of $100$ days.

If today is $3$-Day, what day of the week would it  be (on planet $Z$) at the same date as today,
but exactly $1000$ years later? Explain!



\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  It would be  $\quad$-Day .
\bigskip
\bigskip
\bigskip
\hrule


\vfill\eject



{\bf 17}. (10 pts.)  Using the Extended Euclidean algorithm (no credit for other methods!),
find out whether it is possible to express $1$ as a linear combination 
$$
1=m \cdot 13 +n \cdot 17 \quad ,
$$ 
for some integers $m$ and $n$, and if it is possible, find $m$ and $n$.

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


\vfill\eject



{\bf 18}. (10 pts.)  
Express the integer $32$ (written in our usual (base 10) notation)
in  base $3$, in (i) sparse notation (4 pts) (ii) dense notation (3 pts) (iii) base-seven positional notation (3 pts)

\bigskip
\hrule
\bigskip
\bigskip
\bigskip
{\bf Ans.}:  (i)
\bigskip
(ii)
\bigskip
(iii)
\bigskip
\bigskip
\bigskip
\hrule

\vfill\eject

{\bf 19}. (10 pts.)  
Let $T_n$ be the Tribonacci numbers, defined by
$$
T_1=1 \quad , \quad T_2=1 \quad , \quad T_3=1 \quad ,
$$
and for $n \geq 4$,
$$
T_n=T_{n-1}+T_{n-2}+T_{n-3} \quad .
$$
Give a Zeilberger-style proof of the following identity, 
$$
T_{n+2}=4T_{n-1}+3T_{n-2}+2T_{n-3} \quad .
$$
by checking it empirically for $n=4,5,6,7$ .

\vfill\eject


{\bf 20}. (10 pts.)  Use the Fundamental Theorem of Discrete Calculus  to prove the identity
$$
\sum_{i=1}^{n} i^3 = \left ( \frac{n(n+1)}{2}\right )^2 \quad .
$$


\end
