3
$\begingroup$

How many solutions does $x^{p+1} \equiv 1 \mod p^{2017}$ have in set $\left\{0,1,...,p^{2017}-1 \right\}$? $p$ is prime > 2.

My observations
$1$ is one of solutions of given equation.
$p$ is prime so: $$x^{p-1} \equiv 1 \mod p $$ $$x^{p+1} \equiv x^2 \mod p $$ but I have problem with increase power of $p$ to $2017$ without breaking the rest... I know that I can do:

$$x^{p+1} p^{2016} \equiv x^2 p^{2016} \mod p^{2017} $$ and due to this is group I can say that there is one element such that $$p^{2016} \cdot t \equiv 1 \mod p^{2017} $$ but after multiplication from both side I get starting equation...

$\endgroup$
  • 2
    $\begingroup$ Do you know the existence of primitive roots mod $p^n$? $\endgroup$ – user10354138 Jun 8 at 9:37
  • $\begingroup$ I have just read what this exactly is, I didn't have on my lecture nothing about primitive roots $\endgroup$ – Tester1998 Jun 8 at 9:40
  • $\begingroup$ Yes, I know - $\varphi(2016) = \varphi(2^5) \varphi(3^2) \varphi(7) = (2^5 - 2^4)(6)(6) = 576 $ $\endgroup$ – Tester1998 Jun 8 at 9:50
  • $\begingroup$ I have the same doubts... $\endgroup$ – Tester1998 Jun 8 at 10:12
  • $\begingroup$ @HenningMakholm I would too. I completely missed that $\;p+1\;$ in that exponent, took it for $\;p-1\;$ and etc. Deleting that post. $\endgroup$ – DonAntonio Jun 8 at 10:17
1
$\begingroup$

Clearly $x$ must be coprime to $p^k$, so we're looking exactly for how many elements of the multiplicative group modulo $p^{2017}$ satisfy $x^{p+1}=1$.

The central fact we need to use is that the multiplicative group is cyclic when the modulus is a power of an odd prime. I don't recall offhand how to prove this, and you say you don't know about primitive roots, so the following is probably not the answer you need, but it would at least tell you the answer.

The multiplicative group has order $(p-1)p^{2016}$, so equivalently we're looking for solutions to $$ y(p+1) \equiv 0 \pmod{(p-1)p^{2016}} $$ where we fix a generator $g$ and set $x=g^y$.

By the Chinese Remainder Theorem this means we have to solve $$ yp+y \equiv 0 \pmod{p-1} \qquad yp+y \equiv 0 \pmod{p^{2016}} $$ The first of these is the same as $ 2y \equiv 0 \pmod{p-1} $ and since $p-1$ is even, this has exactly two solutions, namely $y=0$ and $y=\frac{p-1}{2}$.

For modulus $p^{2016}$ it is easy to prove by induction on $k$ that $$ yp+p\equiv 0 \pmod{p^k} \implies p^k\mid y $$ so this equation has the single solution $y=0\pmod{p^{2016}}$.

The number of solutions to the combined equation is therefore $2\cdot 1=2$.

$\endgroup$
1
$\begingroup$

Using Euler's Totient Theorem, $$x^{\phi(p^n)}\equiv1\pmod{p^n}, \ge1$$

If modulo order org$\displaystyle_{(p^n)}x=d,$

$d$ must divide $\phi(p^n)\ \ \ \ (1)$

and again $x^{p+1}\equiv1\pmod{p^n}\implies d$ must divide $p+1\ \ \ \ (2)$

$(1),(2)\implies d$ must divide $(p+1,\phi(p^n))=(p+1,p-1)=2$

So, if $d=2,x\equiv\pm1$ there two solutions namely $x\equiv\pm1$

What if $d=1?$

$\endgroup$
  • $\begingroup$ what is pair $(p+1,\phi(p^n))$? I know that $d$ should divide $n = p^{2017}$ $\endgroup$ – Tester1998 Jun 8 at 10:52
  • $\begingroup$ @Tester1998, $$(a,b)$$ meant greatest common divisor of $a,b$ $\endgroup$ – lab bhattacharjee Jun 8 at 10:56
  • $\begingroup$ @Tester1998: $(p+1,\varphi(p^n))$ is notation for the greatest common divisor of $p+1$ and $\varphi(p^n)$ ... but I'll admit I can't follow the reasoning here. $\endgroup$ – Henning Makholm Jun 8 at 10:56
  • $\begingroup$ I am not sure too... $\endgroup$ – Tester1998 Jun 9 at 8:19
  • $\begingroup$ @HenningMakholm, Please find the updated answer $\endgroup$ – lab bhattacharjee Jun 9 at 10:42
0
$\begingroup$

Use http://mathworld.wolfram.com/DiscreteLogarithm.html

$(p+1)\cdot$ind$_gx\equiv\phi(p^n)$

where $g$ is one of the primitive roots of $p^n,n\ge1$

Use https://proofwiki.org/wiki/Solution_of_Linear_Congruence to find the number of solutions to be

$(p+1,p^{n-1}(p-1))=(p+1,p-1)=2$ for odd $p$

$\endgroup$
  • $\begingroup$ I can't use methods which I didn't have on m lecture, but thanks for linking interesting materials... $\endgroup$ – Tester1998 Jun 8 at 10:32

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.