2
$\begingroup$

Let $m = 2p$

If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$.

I have no idea on how to start. I was trying to find a form such that

$a^{m - 2} \equiv 1 \pmod m$. But I got stuck. Can someone give me a hint here?

$\endgroup$
5
  • 1
    $\begingroup$ Can you give the complete list of the even primes? It is a short one. $\endgroup$
    – Martigan
    Commented Feb 13, 2015 at 10:00
  • 1
    $\begingroup$ @Martigan: It is widely used in math books and articles. $\endgroup$
    – mesel
    Commented Feb 13, 2015 at 10:03
  • 1
    $\begingroup$ @Martigan, only 2 $\endgroup$
    – JOX
    Commented Feb 13, 2015 at 10:04
  • $\begingroup$ Your title speaks of $a^{2p}\equiv a$ but your question of $a^{2p-1}\equiv a$. $\endgroup$
    – drhab
    Commented Feb 13, 2015 at 10:40
  • $\begingroup$ Oh thanks, I made a mistake $\endgroup$
    – JOX
    Commented Feb 13, 2015 at 10:44

3 Answers 3

3
$\begingroup$

Hint: $$\phi(2p)=\phi(p)$$ for all odd primes where $\phi$ is the Euler-phi function.

Edit:
$$a^{\phi(2p)}\equiv a^{\phi(p)}\equiv a^{p-1}\equiv 1 \pmod {2p}$$

Hence $a^p\equiv a$ and $a^{p-1}\equiv 1 \Rightarrow a^{2p-1}\equiv a \pmod {2p}$.

$\endgroup$
3
  • $\begingroup$ I was trying to use Fermat's theorem but I got confused because a and m are not always relatively prime. $\endgroup$
    – JOX
    Commented Feb 13, 2015 at 10:11
  • $\begingroup$ @JOX: Are you familiar with the theorem $$a^{\phi(n)}\equiv 1 \ mod \ n$$. $\endgroup$
    – mesel
    Commented Feb 13, 2015 at 10:15
  • $\begingroup$ @mesel yes I am familiar with it, I can determine that $a^{p-1}\equiv 1 \mod p$ but from there I can't advance. $\endgroup$
    – JOX
    Commented Feb 13, 2015 at 10:45
2
$\begingroup$

By the chinese remainder theorem, congruence modulo $2p$ is uniquely determined by modulo $p$ and modulo $2$ together (this is true for any odd number $p$).

By Fermat's small theorem, we have $a^{2p-1} = a^p\cdot a^{p-1} \equiv a\cdot 1 =a\pmod p$. This is true for any prime $p$. Also, we must have $a^{2p-1} \equiv a\pmod 2$, since that's true for any natural exponent. Therefore, we have $$ a^{2p-1} \equiv \begin{cases}a \pmod p\\ a \pmod 2\end{cases} $$ which gives the desired $a^{2p-1} \equiv a \pmod {2p}$.

$\endgroup$
0
$\begingroup$

Fermat: $p\mid a^{p}-a$ so $p\mid\left(a^{p-1}+1\right)\left(a^{p}-a\right)=a^{2p-1}-a$.

Next to that $2\mid a\iff2\mid a^{2p-1}$ so that $2\mid a^{2p-1}-a$.

So $2$ and $p$ are two distinct ($p$ is odd, so $p\neq2$) primes both dividing $a^{2p-1}-a$.

Conclusion: $$2p\mid a^{2p-1}-a$$

$\endgroup$

You must log in to answer this question.

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