

%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




{\bf 1.} Using the {\bf formula} (no credit for other methods!),
find the unique $x$ between $0$ and $98$ such that

$$
x \equiv 7 \pmod {9} \quad , \quad
x \equiv 6 \pmod {11} \quad .
$$

{\bf Reminder}: The unique solution of the system $x \equiv a_1 \pmod{m_1},x \equiv a_2 \pmod{m_2}$  in $0 \leq x <m_1 m_2$,
when $m_1$ and $m_2$ are relatively prime
$$
x \equiv a_1 m_2 [m_2^{-1}]_{m_1}+ a_2 m_1 [m_1^{-1}]_{m_2} \,\, \pmod{m_1 m_2} \quad .
$$

(Note: you may find the modular inverse by trial-and-error rather than by the `official' way, using the Extended Euclidean Algorithm.)

{\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 $13$.

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

{\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$


{\bf 5}. (10 pts.)  Compute $\phi(18000)$ . Explain!


{\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 .
$$


{\bf 7}. (10 pts.)  Prove that  for every positive integer $n$, the number of partitions of $n$ into odd parts 
equals the number of partitions of $n$ with distinct parts.



{\bf 8}. (10 pts.)  
Prove that if $p$ is  prime, and $2^{p}-1$ is also prime, then $n=2^{p-1}(2^p-1)$ is a perfect number.




{\bf 9}. (10 pts.)  What is $\mu(2002)$? ($\mu(n)$ is the famous M\"obius function).



{\bf 10}. (10 pts.) Using the four rules below (most famously the Quadratic Reciprocity Law)
decide whether $17$ is a quadratic residue modulo $101$. Explain everything.
\bigskip
{\eightrm

{\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}: (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 .
$$
}

{\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.

{\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$.}

{\bf 12}. (10 pts.)   Apply Franklin's bijection to the distinct partition 
$\lambda=(15,14,13,12,6,5,2)$, 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.



{\bf 13}. (10 pts.)  Let $n$ and $k$ be a positive integers, with  $k \leq n$. Prove that the number
of partitions of $n$ with exactly $k$ parts equals the number of partitions of $n$ whose
largest part is $k$.


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


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

{\bf 16.} (10 pts.) In Planet $Z$ there are $9$ days in the week, and
the year-length is always the same (no leap years!), consisting of $400$ 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!


{\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 23 +n \cdot 97 \quad ,
$$ 
for some integers $m$ and $n$, and if it is possible, find $m$ and $n$.


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


{\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$ .

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


\end
