# Using CRT to reason about powers of $2$ where the power is two less than an odd prime

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?

• 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? – A.P. Oct 24 '15 at 11:29
• 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. – 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$.