%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Number Theory (MAS3008): June 2001 Exam %%%%
%%%%% Last modified NPB 3.01.00 %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% using %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% LaTeX template SMS Examination Papers %%%%%
%%%%% created by J Hinde, 28/10/98 %%%%%
%%%%% %%%%%
%%%%% This must be LaTeXed twice %%%%%
%%%%% %%%%%
%%%%% This needs the style file exam.sty %%%%%
%%%%% and the packages fancyheadings and array %%%%%
%%%%% %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,11pt]{article}
\usepackage{exam}
%% include any optional packages here
\usepackage{}
\begin{document}
%% uncomment if multiple examiners
%%%\renewcommand{\examiner}{\examiners}
%% use to specify nonstandard rubric
%%%\renewcommand{\rubric}{ }
%% uncomment for stats tables
%%%\renewcommand{\extrarubric}{\stats}
%% uncomment for no calculators
%%%\renewcommand{\calculator}{\nocalculator}
%% use for other additions to rubric
%%%\renewcommand{\extrarubric}{ }
%% use for short papers
%%%\renewcommand{\duration}{2}
%% specify module code
\newcommand{\module}{MAS3008}
\cover
{NUMBER THEORY} %%% module name
{12 June 2001} %%% date of exam
{9:30 a.m. -- 12:30 p.m.} %%% time of exam
{Dr N.P. Byott} %%% examiners
\pretolerance=1000
\sectionA %%%%%%
%%%%%% parts of section A with indicative marks %%%%%%
\begin{enumerate}
%%%%% single question for Section A
\item
\begin{enumerate}
\item
Find all solutions of each of the following congruences, or show that
none exist:
\begin{enumerate}
\item $6x \equiv 17 \pmod{65}$;
\item $6x \equiv 21 \pmod{69}$;
\item $x^2 \equiv 1 \pmod{77}$;
\item $x^2 \equiv 2 \pmod{55}$;
\item $x^2 \equiv 2 \pmod{7^3}$;
\item $x^2 + 4x\equiv 6 \pmod{13^2}$.
\end{enumerate}
\marginpar{(14)}
\item Use the Binary Powering Algorithm to evaluate $3^{45} \bmod
577$. Show your working.
\marginpar{(6)}
\item State (without proof) the Law of Quadratic Reciprocity, including
the values of the Legendre symbols $\displaystyle{\left( -1 \over
p\right)}$ and $\displaystyle{\left( 2 \over p\right)}$ for an odd prime
number $p$. Evaluate the following Legendre symbols, showing your
working and justifying each intermediate step:
$$ {\rm(i)} \; \left( {5 \over 41} \right); \qquad
{\rm(ii)} \; \left({39 \over 79} \right); \qquad
{\rm(iii)} \; \left({-34\over 109} \right). $$
\marginpar{(9)}
\item
Find all integer solutions to the following Diophantine equations, or
show that none exist:
\begin{enumerate}
\item $15x+23y=7$;
\item $x^2 + 11y=5$;
\item $3x^2+6xy^2-6y^4=1$;
\item $x^2-4 y^2=21$.
\end{enumerate}
\marginpar{(11)}
\end{enumerate}
\marginpar{[{\bf 40}]} %%%%%%% mark for question
\newpage
\sectionB
%%%%%%
%%%%%% parts of section B with indicative marks
%%%%%%
%%%%%%% insert below the questions for Section B %%%%%%%%%%%%%%%%
\item
\begin{enumerate}
\item Give an account of Pollard's Rho method for factorizing a given
integer $n$. Your account should include a clear step-by-step description
of the algorithm, together with a brief explanation of why it works.
You may express the algorithm in pseudocode, or as a procedure in
MAPLE or some other computer language, if you wish. [Assume that a
subroutine is available to compute the greatest common divisor of two
integers.] Explain the roles of the various input parameters, and
indicate the various ways in which the algorithm may terminate.
If $p$ is a prime factor of $n$, roughly how many steps (on average)
of the Rho method would be needed to detect it?
\marginpar{(10)}
\item Illustrate your answer to part (a) by applying Pollard's Rho
method, with iteration function $f(x)=x^2+1$ and with initial value
$x_0=2$, in order to find a proper factor of $n=4661$. [You should
find a factor at the 4th step.]
\marginpar{(6)}
\item Show that if $p$ is prime then the only solution to the
congruence $x^2 \equiv 1 \pmod{p}$ is $x \equiv \pm 1 \pmod{p}$.
Use the fact that $748^2 \equiv 1 \pmod{8881}$ to find a proper factor of
8881.
\marginpar{(4)}
\end{enumerate}
\marginpar{[{\bf 20}]} %%%%%%% mark for question
%%% Use this for part and sub-parts
%%%\begin{enumerate}
%%%\item first part
%%% \begin{enumerate}
%%% \item first
%%% \item second
%%% \end{enumerate}
%%%\item second part
%%%\end{enumerate}
\item
\begin{enumerate}
\item Define Euler's totient function $\varphi$, and state, without
proof, a formula for $\varphi(n)$ in terms of the prime factorisation
of $n$. Show that, if $m$ is a factor of $n$, then $\varphi(m)$ is a
factor of $\varphi(n)$.
\marginpar{(5)}
\item In each of the following cases, find all natural numbers $n$ (if
there are any) such that:
\begin{enumerate}
\item $\varphi(n)=10$;
\item $\varphi(n)=18$;
\item $\varphi(n)=26$.
\end{enumerate}
\marginpar{(9)}
\item
Now consider the following property for a natural number $n$:
$$ \gcd(n , \varphi(n) ) =1. \eqno(*) $$
Show that if $n$ is prime then $n$ satisfies property ($*$), but that
if $n=p^e$ is a prime power with $e>1$ then $n$ does not satisfy
property ($*$). Show further that if $n$ is a composite number
satisfying property ($*$) then $n$ is a product of distinct odd
primes. Is the converse true?
\marginpar{(6)}
\end{enumerate}
\marginpar{[{\bf 20}]} %%%%%%% mark for question
\newpage
\item \begin{enumerate}
\item Let $n$ be a natural number and let $a$ be an integer with
$\gcd(a,n)=1$. What does it mean to say that $a$ is a {\em primitive root}
modulo $n$? Show that $a$ is a primitive root modulo $n$ if and only
if $a^{\varphi(n)/q} \not \equiv 1 \pmod{n}$ for every prime factor
$q$ of $\varphi(n)$, where $\varphi$ denotes Euler's totient function
\marginpar{(4)}
\item Show that 2 is a primitive root modulo 19. Make a table of the
powers $2^i \bmod 19$ for $0 \leq i \leq 17$, and use your table to
find all solutions to each of the following congruences (or to show
that no solutions exist):
\begin{enumerate}
\item $x^7 \equiv 5 \pmod{19}$;
\item $x^4 \equiv 8 \pmod{19}$;
\item $x^3 \equiv 11 \pmod{19}$;
\item $5 x^{11} \equiv 13 \pmod{19}$.
\end{enumerate}
\marginpar{(10)}
\item Let $p$ be prime and let $g$ be a primitive root mod $p$. Show
that either $g$ or $g+p$ is a primitive root mod $p^2$.
\marginpar{(6)}
\end{enumerate}
\marginpar{[{\bf 20}]} %%%%%%% mark for question
\item
\begin{enumerate}
\item Let $p$ be an odd prime, and let $a$ be an integer not divisible
by $p$. State Gauss' Lemma concerning the Legendre symbols
${\displaystyle \left( {a \over p } \right)}$, and use it to evaluate
the Legendre symbols ${\displaystyle \left( {-1 \over p } \right)}$
and ${\displaystyle \left( {2 \over p } \right)}$.
\marginpar{(6)}
\item Let $p$ be a prime such that $p \equiv 1 \pmod{4}$. Prove that
$p$ can be written as the sum of two integer squares.
Express 53 and 97 as sums of two squares, and hence find two
inequivalent expressions for $5141 = 53 \times 97$ as the sum of two
squares. [If $n=a^2+b^2$ then the 8 expressions $(\pm a)^2+(\pm b)^2$
and $(\pm b)^2 + (\pm a)^2$ for $n$ are considered to be equivalent.]
\marginpar{(9)}
\item Let $p$ be a prime such that $p \equiv \pm 1 \pmod{8}$. Show
that $p=2a^2-b^2$ for some integers $a$ and $b$.
\marginpar{(5)}
\end{enumerate}
\marginpar{[{\bf 20}]} %%%%%%% mark for question
\end{enumerate}
\label{lastpage}
\pe %%%%% end of paper
\end{document}