0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Do you really mean $p^q$ and not $pq$? $\endgroup$ – Randall Sep 13 '17 at 17:17
  • 1
    $\begingroup$ 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}$. $\endgroup$ – user236182 Sep 13 '17 at 17:19
  • $\begingroup$ Even for $\bmod {pq},$ there a lots of counter-examples: e.g. $p=3, q=5, x=2,3,5,6\dots$ $\endgroup$ – gammatester Sep 13 '17 at 17:34
  • $\begingroup$ 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 $\endgroup$ – TheGrossSloth Sep 13 '17 at 17:35
  • 1
    $\begingroup$ 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}$$ $\endgroup$ – user236182 Sep 13 '17 at 18:42
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a super clean solution to the problem. $\endgroup$ – Steven Stadnicki Sep 13 '17 at 18:12
  • 1
    $\begingroup$ $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. $\endgroup$ – user236182 Sep 13 '17 at 18:23
  • $\begingroup$ OP said $p,q>2$ in the comments. $\endgroup$ – user236182 Sep 13 '17 at 18:36
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Sep 13 '17 at 18:43
1
$\begingroup$

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

$\endgroup$

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.