British Maths Olympiad 1993 Round 2 Problem 3

My solution to an Olympiad problem.

By Vamshi Jandhyala in mathematics

September 20, 2019

Let $m=\frac{4^p-1}{3}$, where $p$ is a prime number exceeding $3$. Prove that $2^{m-1}$ has remainder $1$ when divided by $m$.

Solution

If $m=\frac{4^p-1}{3}$, then
$$ \label{e1} \begin{align} m = \frac{(2^p-1)(2^p+1)}{3} \end{align} $$

We have,

$$ \label{e2} \begin{align} 2^{m-1} - 1 = 2^{\frac{4^p-4}{3}}-1 &= (2^{(\frac{4^{p-1}-1}{3})})^4-1 = (2^{(\frac{4^{p-1}-1}{3})}-1) (2^{(\frac{4^{p-1}-1}{3})}+1) (2^{2(\frac{4^{p-1}-1}{3})}+1) \end{align} $$

The first factor of $\ref{e2}$, $$ \begin{align} 2^{(\frac{4^{p-1}-1}{3})}-1 = (2^{\frac{2^{p-1}-1}{3}})^{(2^{p-1}+1)}-1 \end{align} $$

is divisible by first factor of $\ref{e1}$ because $2^{p-1}-1$ is divisible by both $p$ and $3$.

The second factor of $\ref{e2}$, $$ \begin{align} 2^{(\frac{4^{p-1}-1}{3})}+1 = (2^{\frac{2^{p-1}-1}{3}})^{(2^{p-1}+1)}+1 \end{align} $$

is divisible by $2^{p}+1$ because $2^{p-1}-1$ is odd and divisible by both $p$ and $3$ and $2^{p-1}+1$ is also an odd number.

We made use of the following facts:

  1. Fermat’s Little Theorem (FLT) which states $a^{p-1}-1$ is divisible by $p$ when $p$ is prime and $p$ doesn’t divide $a$.
  2. $a^{n}-b^{n}$ is divisible by $a-b$ for all $n$.
  3. $a^{n}+b^{n}$ is divisible by $a+b$ if $n$ is odd.