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

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$

• Do you really mean $p^q$ and not $pq$? – Randall Sep 13 '17 at 17:17
• By Euler's theorem, if $\gcd(x,p^q)=1$, i.e. if $p\nmid x$, then $x^{\phi(p^q)}\equiv 1\pmod{p^q}$, where $\phi(p^q)=p^{q}-p^{q-1}$. For all $x\in\mathbb Z$ we have $x^{\phi(p^q)+q}\equiv x^q\pmod{p^q}$. Proof: if $p\nmid x$, then divide both sides by $x^q$, where $\gcd(x^q,p^q)=1$, to get $x^{\phi(q)}\equiv 1\pmod{p^q}$, which is true. If $p\mid x$, then $p^q\mid x^q\mid x^{\phi(q)+q}$, so $x^{\phi(p^q)+q}\equiv x^q\equiv 0\pmod{p^q}$. Done. Your claim $x^{p^q}\equiv x\pmod{p^q}$ is wrong. Here's a counterexample: $2^{2^2}\equiv 2^4\equiv 16$ $\equiv 0\not\equiv 2\pmod{2^2}$. – user236182 Sep 13 '17 at 17:19
• Even for $\bmod {pq},$ there a lots of counter-examples: e.g. $p=3, q=5, x=2,3,5,6\dots$ – gammatester Sep 13 '17 at 17:34
• Thanky you very much for your anwser it is really helpful. I forgot to mention that p,q are greather than 2. Yes, you are right. I assumed that $gcd(x,p^q) = 1$ so in this case scenario counterexample doesn't work. Thank you very much once again – TheGrossSloth Sep 13 '17 at 17:35
• Counterexample of your formula $x^{p^q}\equiv x\pmod{p^q}$ for odd primes $p,q$, $\gcd(x,p^q)=1$, $x\in\mathbb Z$, which is wrong. $\phi(3^3)=3^3-3^2=18$, $\gcd(2,3^3)=1$ and $$2^{3^3}\equiv 2^{27}\equiv 2^{18}2^{9}\equiv 1\cdot 2^9$$ $$\equiv 2^9\equiv -1\not\equiv 2 \pmod{3^3}$$ – user236182 Sep 13 '17 at 18:42

## 2 Answers

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.

• This is a super clean solution to the problem. – Steven Stadnicki Sep 13 '17 at 18:12
• $y^2\equiv 1\pmod{p^q}$ is equivalent to $p^q\mid y^2-1=(y+1)(y-1)$. OP said $p>2$, and if $p\mid y+1$ and $p\mid y-1$, then $p\mid (y+1)-(y-1)=2$, so either $p^q\mid y+1$ or $p^q\mid y-1$, i.e. (equivalently) $y\equiv \pm 1\pmod{p^q}$, which are all the solutions. – user236182 Sep 13 '17 at 18:23
• OP said $p,q>2$ in the comments. – user236182 Sep 13 '17 at 18:36
• This is otherwise correct (+1), but I don't understand you bringing up $GF(p^q)$. After all, the equation is in the ring $R=\Bbb{Z}/p^q\Bbb{Z}$ and has nothing to do with the field $GF(p^q)$. You can either use the argument given by @user236182, or use the fact that the unit group of $R$ is cyclic of order $\phi(p^q)$ (here we need $p>2$). In a cyclic group of order $n$ the equation $x^m=1$ has exactly $\gcd(m,n)$ solutions - in this case two. – Jyrki Lahtonen Sep 13 '17 at 18:43

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}$.