\documentclass{amsart} \include{mydefs} \newenvironment{lyxlist}[1] {\begin{list}{} {\settowidth{\labelwidth}{#1} \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep} \renewcommand{\makelabel}[1]{##1\hfil}}} {\end{list}} \theoremstyle{remark} \newtheorem*{rem*}{\protect Remark} \begin{document} \section*{Lior Silberman's Math 312: Problem Set 4 (due 6/6/18)} \begin{center} \textbf{Multiplicative Order}\bigskip{} \par\end{center} \begin{lyxlist}{10.} \item [{1.}] Let $n$ be a pseudoprime to base $2$ (recall that this means $2^{n-1}\equiv1\,(n)$). Show that $m=2^{n}-1$ is also a pseudoprime to base $2$.\\ \emph{Hint}: Show that $n|m-1$ and use the fact that you know the order of $2$ mod $m$. \bigskip{} \item [{{*}2.}] Let $p$ be a prime divisor of the $n$th Fermat number $F_{n}=2^{2^{n}}+1$. \begin{lyxlist}{10.} \item [{(a)}] Find the order of $2$ mod $p$. \item [{(b)}] Show that $p\equiv1\,(2^{n+1})$. \item [{(c)}] For any $k\geq1$ show that there are infinitely many primes $p$ for which the order of $2$ mod $p$ is divisible by $2^{k}$. \item [{RMK}] Note that (b) simplifies the search for prime divisors of Fermat numbers. We will later show that $p\equiv1\,(2^{n+2})$ holds. \item [{\bigskip{} }]~ \end{lyxlist} \item [{3.}] Elements of order $2$ mod $m$. \begin{lyxlist}{10.} \item [{(a)}] Let $p$ be an odd prime, and let $k\geq1$. Show that the congruence $x^{2}\equiv1\,(p^{k})$ has only the two obvious solutions $x\equiv\pm1\,(p^{k})$.\\ \emph{Hint}: Can both $x-1,x+1$ be powers of $p$? \item [{({*}b)}] Let $n$ be an odd number, divisible by exactly $r$ distinct primes. Set up a bijection between congruence classes mod $n$ satisfying $x^{2}\equiv1\,(n)$ and functions $f\in\left\{ \pm1\right\} ^{r}$. Conclude that there are precisely $2^{r}$ congruence classes mod $n$ which solve the equation.\bigskip{} \end{lyxlist} \item [{4.}] Using Fermat's Little Theorem, show that for all integers $n$, $30|n^{9}-n$.\\ \emph{Hint}: For each prime $p|30$ show that $n^{p}-n|n^{9}-n$ as polynomials.\bigskip{} \end{lyxlist} \begin{center} \textbf{Wilson's Theorem}\bigskip{} \par\end{center} \begin{lyxlist}{10.} \item [{5.}] We will show that if $n\geq6$ is composite then $(n-1)!\equiv0\,(n)$. \begin{lyxlist}{10.} \item [{(a)}] (The easy case) Assume first that $n$ is divisible by at least two distinct primes, that is that $n=\prod_{j=1}^{r}p_{j}^{k_{j}}$ for some distinct primes $p_{j}$ where $k_{j}\geq1$ for all $j$ and $r\geq2$. Show that $(n-1)!\equiv0\,(n)$.\\ \emph{Hint}: It is enough to show the congruence mod each $p_{j}^{k_{j}}$ separately. Why is $(n-1)!$ divisible by $p_{j}^{k_{j}}$? \item [{(b)}] Let $p$ be prime and let $k\geq3$. Show that $p^{k}|(p^{k}-1)!$\\ \emph{Hint: }Find some powers of $p$ dividing the factorial. \item [{(c)}] Let $p\geq3$ be prime. Show that $p^{2}|(p^{2}-1)!$\\ \emph{Hint}: Now you need to consider multiples of $p$ as well. \item [{RMK}] Note that $3!\not\equiv0\,(4)$. Ensure that your solution to (c) used the fact that $p\neq2$ at some point!\bigskip{} \end{lyxlist} \end{lyxlist} \newpage{} \begin{center} \textbf{The Euler Function and RSA}\bigskip{} \par\end{center} Recall that $\phi(m)=\#\left\{ 1\leq a\leq m\mid\left(a,m\right)=1\right\} $, and that for $p$ prime $\phi(p)=p-1$. \begin{lyxlist}{10.} \item [{6.}] Explicit calculations. \begin{lyxlist}{10.} \item [{(a)}] Calculate $\phi(4),\,\phi(9),\,\phi(12),\,\phi(15)$. \item [{(b)}] Show that $\phi(12)=\phi(3)\phi(4)$ and $\phi(15)=\phi(3)\phi(5)$ but that $\phi(4)\neq\phi(2)\cdot\phi(2)$, $\phi(9)\neq\phi(3)\cdot\phi(3)$.\bigskip{} \end{lyxlist} \item [{7.}] Let $p,q$ be distinct primes and let $m=pq$. \begin{lyxlist}{10.} \item [{(a)}] Show that there are $p+q-1$ integers $1\leq a\leq m$ which are not relatively prime to $m$.\\ \emph{Hint}: What are the possible values of $\gcd(a,m)$? For which $a$ do they occur? \item [{(b)}] Show that $\phi(pq)=(p-1)(q-1)$. \item [{RMK}] This means in particular that $\phi(pq)=\phi(p)\phi(q)$. \item [{(c)}] Give a formula for $p+q$ in terms of $m,\phi(m)$. \item [{SUPP}] Show how to factor $m$ given $m,\phi(m)$.\bigskip{} \end{lyxlist} \item [{8.}] Fix an integer $m$ and two positive integers $d,e$ so that $de\equiv1\,(\phi(m))$. Define functions $E,D$ by $E(x)=x^{e}\mod m$ and $D(y)=y^{d}\mod m$ (in other words, raise to the appropriate power and keep remainder mod $m$). \begin{lyxlist}{10.} \item [{(a)}] Let $M=\left\{ 1\leq a\leq m\mid(a,m)=1\right\} $ be the set of invertible residues ($\phi(m)$ is the size of this set). Show that both $D,E$ map the set $M$ into itself. \item [{(b)}] Show that for any $x,y\in M$, $D(E(x))=x$ and $E(D(y))=y$.\\ \emph{Hint:} Euler's Theorem.\bigskip{} \end{lyxlist} \end{lyxlist} \begin{center} \textbf{Supplementary problems (not for submission)}\bigskip{} \par\end{center} \begin{lyxlist}{10.} \item [{A.}] (The binomial formula) Prove by induction on $n\geq0$ that for all $x,y$, \[ (x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}\,. \] \bigskip{} \item [{B.}] Let $p$ be an odd prime. \begin{lyxlist}{10.} \item [{(a)}] Show that $(p-1)!\equiv(-1)^{\frac{p-1}{2}}\left(\left(\frac{p-1}{2}\right)!\right)^{2}\,(p)$. Conclude that if $p\equiv1\,(4)$ then there is $a\in\Z$ such that $a^{2}\equiv-1\,(p)$. \item [{(b)}] Conversely, assume that $a^{2}\equiv-1\,(p)$ for some integer $a$. Show that the order of $a$ mod $p$ is exactly $4$ and conclude that $p\equiv1\,(4)$. \end{lyxlist} \item [{C.}] Let $p$ be a prime and let $0\leq k