find the number of possible solution for the given the condition

Revision en5, by liveoverflow, 2020-03-31 09:39:57

Given an integer X. Your task is to find out how many positive integers n ( 1 <= n <= X) satisfies the following condition:-

$$$na^n \equiv \, b(mod\,p)$$$

Constraints:
2 <= p <= 106,
1 <= a,b< p,
1 <= X <= 1012
I have no idea how to solve this question, any approach or proof will be highly helpful.

Thanks.

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)