\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{11: Various Number Theory Tricks}{Due Thursday, Week 6, at the start of class.}

Solve \textbf{three} of the following \textbf{six} problems.  As always, prove your claims!

Also: due to Veteran's Day, there is no class this Tuesday!  Therefore, this set is due Thursday.  Enjoy the holiday!

Themes for this problem set:
\begin{itemize}
\item Divisibility and primes!  It is sometimes useful to consider factorizations of numbers. ( You might have noticed this already.)
\item Mod $n$!  It's also useful.
\item Fermat's little theorem!  For any $n$, $n^{p} \equiv n \mod p$.
\item Wilson's theorem: for any $p$, $(p-1)! \equiv -1 \mod p$.
\end{itemize}
You can use those last two results without proof on the following problems!



\begin{enumerate}
\item[0.] Solve any un-signed-up-for problems from HW\#10!
\item Prove or disprove the following claim: there is no positive integer value of $n$ such that the set
\begin{align*}
\{n, n+1, n+2, n+3, n+4, n+5\}
\end{align*}
can be broken into two sets, with the product of the elements of the first set equal to the product of the elements in the second set.
\item 
\begin{enumerate}
\item Take any prime number $p$ and any positive integer $n$.  Look at the quantity $n!$.  Then, the number of times that $p$ occurs as a factor in $n!$ is given by the sum
\begin{align*}
\left\lfloor \frac{n}{p} \right\rfloor +\left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \ldots
\end{align*}
For example, the number of times that 2 occurs as a factor of $5!$ is 3, as $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 8 \cdot 15$; and indeed,
\begin{align*}
&\left\lfloor \frac{5}{2} \right\rfloor +\left\lfloor \frac{5}{4} \right\rfloor + \left\lfloor \frac{5}{8} \right\rfloor + \ldots \\
=& 2  + 1 + 0 + 0 + \ldots\\
=& 3.
\end{align*} 
Prove this fact!
\item Find all of the values of $n$ such that $n!$ ends in 100 zeroes.
\end{enumerate}
\item Suppose that $n$ is a perfect square such that its last four digits are all equal.  Prove that they are all equal to 0.
\item Show that for every prime $p$, there is an integer $n$ such that $2^n + 3^n + 6^n - 1$ is a multiple of $p$.

\item Suppose that there is some positive integer $n$ such that the \textbf{first} digit of $2^n, 5^n$ are the same.  What is this digit?  Prove your claim.
\item How many primes $p$ exist with the following property: if we write $p$ in base 10, then its digits are alternating 1's and 0's?  (For example, 101 is such a prime!)
\end{enumerate}





\end{document}


