Number of solutions for the given condition

Revision en9, by liveoverflow, 2020-03-31 10:56:42

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!

Tags maths, #modular arithmetic, discrete math, #algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English liveoverflow 2020-03-31 10:56:42 6
en8 English liveoverflow 2020-03-31 10:55:09 311 Tiny change: 'nts: \n$$2⩽p⩽1061⩽a,b<p1⩽X⩽2012\begin{ali' -> 'nts: \n$$\begin{ali'
en7 English liveoverflow 2020-03-31 09:40:54 4
en6 English liveoverflow 2020-03-31 09:40:09 17 Reverted to en3
en5 English liveoverflow 2020-03-31 09:39:57 6 Reverted to en1
en4 English liveoverflow 2020-03-31 09:39:41 11 Reverted to en2
en3 English liveoverflow 2020-03-31 09:21:38 11 Tiny change: 'Given an integer X,p,a,b. ' -> 'Given X,p,a,b. '
en2 English liveoverflow 2020-03-31 09:20:51 6 Tiny change: ' integer X. Your tas' -> ' integer X,p,a,b. Your tas'
en1 English liveoverflow 2020-03-30 18:12:04 393 Initial revision (published)