Sorry the write up is rushed, but I feel these are good problems, please
contact me if clarification is needed. I expect only one to be used.

1) Given a prime $p > 2$, and a number $a$, we wish to find all values of 
$0 \leq x < p$
such that $a \equiv x^2 \pmod p$. We know if $p = 3$ and $a=1$, there are
exactly two solutions. If if $p = 3$ and $a=2$, there are no solutions. Show
that for any such equation, there exist EXACTLY 0 or 2 solutions.

\solution{

  We show there cannot be any other number of solutions. We know there cannot 
be exactly one solution because if there is a solution
$x$, then there is a solution $-x$. $x$ cannot be congruent to $-x \mod p$,
because that would imply $2x \equiv 0 \pmod p$ which would imply $p$ is even.

  Say there is a $y$ such that $y^2 \equiv x^2 \pmod p$. This implies
$p | x^2 - y^2$ which implies $p|(x+y)(x-y)$ which implies $p|x+y$ or
$p|x-y$. So $y \equiv x \pmod p$ or $y \equiv -x \pmod p$. So there cannot
be more than two solutions.

}



2) Suppose we have a $n$ card deck. Define a perfect shuffle to be
a shuffle where we split the deck in half, and shuffle so that each card
from each half is perfectly interlaced with the bottom card always remaining
at the bottom(I know this explanation is crap). For
example, if we have an 8 card deck 0,1,2,3,4,5,6,7 in that order, we split
the cards into (0,1,2,3) and (4,5,6,7). The shuffle goes as follows:
first 7 goes to bottom, then 3, then 6 then 2 and so on. So the new order
will be (0,4,1,5,2,6,3,7).

a) After one perfect shuffle, a card initially at position $i$ goes to what new
position (We might just give them this part)? How about after $x$ perfect
shuffles?

\solution{

card $i$ goes to $2i \pmod (n-1)$ after one perfect shuffle.
card $i$ goes to $2^{x}i \pmod (n-1)$ after $x$ perfect shuffle. 
}

b) Under what condition will the deck be restored to its original order
after $x$ perfect shuffles?
\solution{
  If $2^x \equiv 1 \pmod (n-1)$.
}

c) If the deck we use has 54 cards, how many perfect shuffles will 
restore the deck to its original order?
\solution{
  53
}

d) Let $x$ be the correct answer to part c. Suppose we want to find out if
this is the \emph{minimum} number of perfect shuffles needed to restore the
deck to its original order. We checked all factors of $x$ and noticed
that they were not sufficient. Now we need to be sure that all non-factors
of $x$ cannot be sufficient as well.
Show that no non-factors of $x$ perfect shuffles may restore the deck to its
original order.
\solution{
  Proof by contradiction. Let $d$ be the smallest such non factor. We know
  $x = qd + r$ by division algorithm. If $2^d \equiv 1 \pmod p$, then
  $2^{qd} \equiv 1 \pmod p$. Because $2^x \equiv 1 \pmod p$, then we know
  $2^r \equiv 1 \pmod p$. But $r < d$. This is a contradiction.
} 
