Sophie Germain prime

Question

Let $p$ be a Sophie Germain prime.

I need to find all possible options for the remainder of $x^p$ on division by $2p + 1$ for any integer $x$.

By Fermat's little theorem, we have that: $a^p - p$ is a multiple of $p$.

Answer 1

A) find all possible options for the remainder of $x^p$ on division by $2p+1$ for any integer $x$.

If the order of $x$ in $2p+1$ is exactly $p$ then:

$1\equiv x^p \pmod{2p+1} \iff Ord_{2p+1}(x)=p$

If the order of $x$ in $2p+1$ is exactly $2p$ then:

$2p\equiv x^p \pmod{2p+1} \iff Ord_{2p+1}(x)=2p$

---

Example time:

Take the sophie-germain prime $29$ and its associated safe prime $2p+1=59$.

Let be $x=19$

$Ord_{59}(19) = p = 29 \Rightarrow 1 \equiv 19^{29} \pmod{59}$

Let be $x=11$

$Ord_{59}(11) = 2p = 58 \Rightarrow 58 \equiv 11^{29} \pmod{59}$