% This template was created by Stephen on 27th March 2000
%
% Title:  Euclidean Geometry
% Author: Stephen Farrar
% Date:   16/4/2000
%

% Set the document class
\documentclass[12pt,a4paper]{article}

% Resize the page, to save the forests.
\setlength{\topmargin}{-1cm} \setlength{\textheight}{24cm}
\setlength{\textwidth}{15cm} \setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}

% Just in case we want to do Black Board Bold letters.
%\input{amssymb.sty}
\usepackage{amssymb}

% So we can do multicolumns
\usepackage{multicol}
\setlength\columnseprule{0pt}   % no vertical lines inbetween columns
\setlength\multicolsep{0.5ex}     % space preceding a multicolumn

% A command to generate the header text
\newcommand{\myheader}
{\footnotesize April 2006}

% Change the headers and footers
\pagestyle{myheadings} \markboth{\myheader}{\myheader}

% New Commands to make numbered lists easier
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}

% New Commands to make in-text displayed math easier
\newcommand{\bdm}{$ \displaystyle}
\newcommand{\edm}{$}

% New Commands to do handle the black board bold sets:
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}

% New command for conjugates, arguments, etc.
\def\conj#1{\overline{#1}}
\def\arg{\,\mbox{arg}\,}
\def\Arg{\,\mbox{Arg}\,}
\def\cis{\,\mbox{cis}\,}
\def\Cis#1{\cos {#1} + i \sin {#1}}
\def\Re{\, \mbox{Re}\,}
\def\Im{\, \mbox{Im}\,}
\def\cosec{\,\mbox{cosec}\,}

% New command for the heading
\newcommand{\WorksheetHeading}[1]{{\par\noindent \bf \Large #1}}

% New command to fix spelling
\newenvironment{centre}{\begin{center}}{\end{center}}

% New command for itemised titles
\def\ite#1{\item{\bf #1.}}

%--------------------------------------------------------
% Let the document begin!
\begin{document}

\title{Number Theory (Senior)}%
\author{Peter McNamara}%
\date{April 18 2006}

\maketitle

\subsection*{Theory}

\begin{enumerate}

\ite{Factorisations} $x^n-1$ and $x^m+1$ for odd $m$ both
factorise. You should know this.

\ite{Fermat's Little Theorem} If $p$ is a prime and $a$ is an
integer then $$a^p\equiv a\pmod{p}.$$

\ite{Euler's generalisation} Suppose $n$ is a positive integer and
$a$ is an integer coprime to $n$. Then $$a^{\phi(n)} \equiv
1\pmod{n}$$ where $\phi(n)$ is the Euler-phi function.

\ite{Definition} Suppose $n$ is a positive integer and $a$ is
coprime to $n$. Then the {\it order} of $a$ modulo $n$ is equal to
the smallest positive integer $d$ such that $$a^d\equiv
1\pmod{n}.$$

\ite{Lemma} Let $d$ be the order of $a$ modulo $n$ and suppose
that $a^m\equiv 1\pmod{n}$. Then $d$ divides $m$.

\end{enumerate}

\subsection*{Problems}

\begin{enumerate}


\item Find all positive integers $n$ for which $n$ divides
$2^n-1$.

\item For which positive integers $n$ is $2^{n-1}+1$ divisible by
$n$?

\item Show that
\[
(a^m-1,a^n-1)=a^{(m,n)}-1.
\]

\item What is the largest power of 2 that divides $3^{2^n}-1$?

\item (IMO 1999 Q4) %% IMO4
Find all pairs $(n,p)$ of positive integers such that
\begin{itemize}
\item $p$ is prime; \item $n \leq 2p$; \item $(p-1)^n + 1$ is
divisible by $n^{p-1}$.
\end{itemize}

\item (Romania 1978) Show that for every natural number $a\geq 3$
there is an infinity of natural numbers $n$ such that $n\mid
a^n-1$.

\item Let $m=(4^p-1)/3$ where $p$ is a prime and $p>3$. Prove that $2^{m-1}$ has remainder 1 when divided by $m$.

\item Prove that for each positive integer $n$, there exist $n$ consecutive positive integers none of which is an integral power of a prime number.

\item (IMO 1998 Q3) %% IMO3, Belarus
For any positive integer $n$, let $d(n)$ denote the number of
positive divisors of $n$ (including 1 and $n$ itself). Determine
all positive integers $k$ such that $d(n^2)/d(n) = k$ for some
$n$.

\item (IMO 2000 Q5) %% IMO5
Determine if there exists a positive integer $n$ such that $n$ has
exactly 2000 prime divisors and $2^n+1$ is divisible by $n$.

\item (IMO 1990 Q3) Determine all integers $n > 1$ such that
$$\frac{2^n + 1}{n^2}$$
is an integer.

\item (IMO 1998 Q3) %% IMO3, Belarus
For any positive integer $n$, let $d(n)$ denote the number of
positive divisors of $n$ (including 1 and $n$ itself). Determine
all positive integers $k$ such that $d(n^2)/d(n) = k$ for some
$n$.

\item Let $q$ be a positive rational number. Show that $q$ can be expressed in the form
\[
\frac{a^3+b^3}{c^3+d^3}
\]
where $a$, $b$, $c$ and $d$ are positive integers.

\item Determine all positive integers $n$ for which there exists an integer $m$ so that $2^n-1$ divides $m^2+9$.

\item Find all integers $k$ such that there exist positive integers $a$ and $b$ satisfying
\[
\frac{a+1}{b}+\frac{b+1}{a}=k.
\]

\item The set of positive integers is partitioned into finitely many subsets. Show that some subset $S$ has the following property: for every positive integer $n$, $S$ contains infinitely many multiples of $n$.

\item Let $p$ be a prime number greater than 5. Prove that the set $X=\{p-n^2\mid n\in\mathbb{Z}\  {\rm and }\  n^2<p\}$ contains two distinct elements $x$ and $y$ with $x\neq 1$ such that $x$ divides $y$.

\item Let $b$, $m$, $n$ be positive integers such that $b>1$ and $m\neq n$. Prove that if $b^m-1$ and $b^n-1$ have the same prime divisors, then $b+1$ is a power of 2.

\end{enumerate}


\end{document}
