0
$\begingroup$

Let $m = \frac{(4^p - 1)}{3}$ where $p$ is prime and $p > 3$.

Show that the remainder when $2^{m - 1}$ is divided by $m$ is equal to $1$.

I've tried various ways of setting $2^{m - 1} = km + 1$ and trying to find an appropriate integer $k$, but to no avail.

Any ideas on a better way to approach this? Maybe some sort of modular arithmetic?

$\endgroup$

1 Answer 1

0
$\begingroup$

Note that $p\nmid 4^p - 1$ since $p>3$ and so $p\nmid m$. Now, let $q$ be a prime divisor of $m$. Then, $q\mid 4^p - 1$, which means that $q\mid 2^{2p}-1$. Thus, $\mathrm{ord}_q(2)\mid 2p$. It is easy to see that $2p \mid m-1$. This means that $q\mid 2^{m-1}-1$, since the order of $2$ modulo $q$ divides $m-1$.

In order to finish, we must show that if $q$ is a prime divisor of $m$, then $q^2\nmid m$. But if $q^2 \mid 4^p - 1$ then $4$ would be a double root of $x^p - 1$ in $\mathbb{F}_q$, and this is impossible since the derivative of $x^p -1$ is $px^{p-1}$ and $p\neq q$.

So, we have seen that $m = q_1\cdots q_r$ with $q_i$ primes and $2^{m-1}\equiv 1\pmod{q_i}$ for all $i$. This implies that $m \mid 2^{m-1}-1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .