Let $p$ be any odd prime.

Using the Chinese Remainder Theorem and Fermat's Little Theorem, we know that:

$$\frac{2p}{2} + \left(\frac{2p}{p}\right)\left(\frac{2p}{p}\right)^{p-2} = p + 2^{p-1} \equiv 1 \pmod {2p}$$

There exists $c$ where $c < p$ and $2^{p-2} \equiv c \pmod p$ and $p + 2c \equiv 1 \pmod {2p}$

Since $c < p$, it follows that $p < p + 2c < 3p$ so that $p + 2c = 2p+1$

This gives us that $c = \frac{p+1}{2}$

So, then it follows in all cases that:

$$2^{p-2} \equiv \frac{p+1}{2} \pmod p$$

Is my reasoning correct?

  • 1
    $\begingroup$ What are you trying to prove, exactly? Furthermore, if (as it seems) you are asking us to check your proof, could you please add the proof-verification tag? $\endgroup$ – A.P. Oct 24 '15 at 11:29
  • $\begingroup$ Good point. I added a proof verification tag. I was reasoning about this using CRT and I came to this conclusion. It may not be interesting at all but I wanted to check my logic. $\endgroup$ – Larry Freeman Oct 24 '15 at 11:31

In the first line, you have a term $\frac{2p}{2}$ mod $2p$. That is a dangerous thing to write, because we cannot divide by $2$ mod $2p$. This is because both $2\cdot 0 = 2p$ mod $2p$ and $2\cdot p = 2p$ mod $2p$, so both 0 and $p$ can be said to be equal to $2p/2$ mod $2p$. In general, it is a bad idea to divide by zero divisors.

However, in this case it works out, because in the end you are taking the result mod $p$, and then this ambiguity disappears.

Note also that your argument can be done more easily mod $p$ instead of mod $2p$: setting as you do $c$ positive such that $c < p$ and $c = 2^{p - 2}$ mod $p$, we have by Fermat's little theorem $2c = 1 \mod p$, and we have $1 < 2c < 2p$, which again leads to $2c= p +1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.