liveoverflow's blog

Number of solutions for the given condition
By liveoverflow, history, 4 years ago, In English

Given $$$X,p,a,b$$$, we need to find out how many $$$n\in\mathbb N,\;(1\leqslant n\leqslant X)\;$$$ satisfy the following condition:

>

$$$na^n\equiv b\pmod{p}$$$

Constraints:

$$$\begin{aligned}\begin{equation}2\leqslant p\leqslant 10^6\\1\leqslant a,b\lt p\\1\leqslant X\leqslant 10^{12}\end{equation}\end{aligned}$$$

I have no idea how to solve this question, any approach or proof will be highly appreciated.

Thank you in advance!

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Only $$$X$$$ is given? What about $$$a$$$ and $$$b$$$ and $$$p$$$? They can be anything?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems related to the discrete logarithm, so start by reading about it.

https://en.wikipedia.org/wiki/Discrete_logarithm

→ Reply