Find solution of ${x}^{p+1}\equiv{1}\pmod{{p}^{q}}$, where p and q are prime

Question

I am trying to find solution of problem above
We do know that p and q are prime number.

I tried 2 ways to approach this task

1.) Using Fermat's little theorem, Euler's theorem and modular aritmethic
The only conclusion I got was that ${x}^{{p}^{q}}\equiv{x}\pmod{{p}^{q}}$
and also that : ${x}^{a}\equiv{x^{b}}\pmod{{p}^{q}} \implies {x}^{a+p}\equiv{x^{b-1}}\pmod{{p}^{q}} $
But this doesn't get me anywhere
2.) Is was similar to RSA, but I couldn't figure out anything that makes sens

I would be really thankful for any hint, method of approach or tip.
If you know similar task, where instead p or q are given numbers please let me know.
I am stacked

P.S
I tried it for some prime numbers in WolframAlpha and the solutions always were $x = \pm1$

Answer 1

I'm assuming $p$,$q$ are primes $>2$.

If you know any abstract algebra, we can rephrase this problem as finding some element $x$ in the multiplicative group $(\mathbb{Z}/(p^{q})\mathbb{Z})^{*}$ with order dividing $p+1$. It is a fact that the order of an element must also divide the order of the group, which in this case is $\varphi(p^q) = p^q - p^{q-1} = (p-1)(p^{q-1})$. What are possible common factors of these two numbers? Only $1$ and $2$. Therefore, our possible values of $x$ are elements of order dividing $1$ or $2$. The only element of order dividing $1$ is the idenity, $1$.

Now the question is to find elements of order dividing $2$, ie to find $y$ such that $y^2 \equiv 1 (\text{mod $p^q$})$. The solutions $1$ and $-1$ are obvious, and actually the only roots, as the quadratic can have only two roots (see Jyrki Lahtonen's comment). Therefore, the only solutions are $1,-1$ as you observed.

Answer 2

One important observation is that $x^{p+1}\equiv 1\pmod{p^q}$ if and only if (iff) $x^{p+1}\equiv 1\pmod{p^i}$ for all $i\in\{1,2,\ldots,q\}$.

Let $p=2$. You said in the comments that $p,q>2$, but I'll solve this case too because it's easy. We don't need to know $q$ is prime. Let $q=a$ be any positive integer.

$x^3\equiv 1\pmod{2^a}$

$x^3-1=(x-1)(x^2+x+1)$

$x^2+x+1=x(x+1)+1$ is odd for all $x\in\mathbb Z$, because, e.g., $x(x+1)$ is a product of two consecutive integers, so $x(x+1)$ must be even and $x(x+1)+1$ must be odd.

Therefore by Euclid lemma $x^3\equiv 1\pmod{2^a}$ is equivalent to $x\equiv 1\pmod{2^a}$.

---

Let $p$ be an odd prime. We don't need to know $q$ is prime. Let $q=a$ be any positive integer.

By Fermat's little theorem $x^{p+1}\equiv (x^p)\cdot x\equiv$

$\equiv x\cdot x\equiv x^2\equiv 1\pmod{p}$, $p\mid x^2-1=(x+1)(x-1)$. By Euclid lemma $x\equiv \pm 1\pmod{p}$, i.e. (equivalently) $x=pk\pm 1$ for some $k\in\mathbb Z$.

Use induction. Let $x=p^tm\pm 1$ for some $t\ge 1$, $t\in\mathbb Z$, $m\in\mathbb Z$.

If $a=t$, then $x\equiv \pm 1\pmod{p^a}$ and we're done. Let $a>t$.

By binomial theorem

$(p^tm\pm 1)^{p+1}\equiv$

$\equiv (p+1)(p^tm)(\pm 1)^{p}+(\pm 1)^{p+1}$

$\equiv (p^{t+1}m+p^t m)(\pm 1)^p + (\pm 1)^{p+1}$

$\equiv p^t m(\pm 1)^p+(\pm 1)^{p+1}$

$\equiv p^t m (\pm 1) + 1\equiv 1\pmod{p^{t+1}}$

because $p+1$ is even, so $(\pm 1)^{p+1}=1$. Subtract $1$ from both sides:

$p^t m (\pm 1)\equiv 0 \pmod{p^{t+1}}$.

$p^{t+1}\mid p^t m (\pm 1)$, i.e. $p\mid m$, so $x\equiv \pm 1\pmod{p^{t+1}}$.

By induction $x\equiv \pm 1\pmod{p^a}$, and indeed when we plug in $x=p^a s\pm 1$ for some $s\in\mathbb Z$ into $x^{p+1} - 1$ we get an integer divisible by $p^a$, where you could've used binomial theorem or modular arithmetic. Notice that $p+1$ is even, so $(\pm 1)^{p+1}=1$.

Answer:

if $p=2$, then $x^{p+1}\equiv 1\pmod{p^a}$ for any $a\ge 1$, $a\in\mathbb Z$ has the only solutions $x\equiv 1\pmod{2^a}$.

If $p$ is an odd prime, then $x^{p+1}\equiv 1\pmod{p^a}$ for any $a\ge 1$, $a\in\mathbb Z$ has the only solutions $x\equiv \pm 1\pmod{p^a}$.