Given $k, p, q$, we need to find the solutions for
$x ^{k}\equiv p$ (mod $q)$.
How to find the number of solutions for $x$ up to some upper limit of $x$.
Asked
Active
Viewed 69 times
1
-
Project Euler?? – Jyrki Lahtonen Aug 07 '13 at 19:47
-
Are $k,p,q$ each arbitrary positive integers, or are $p$ and/or $q$ meant to be prime? – Ben Grossmann Aug 07 '13 at 19:47
-
Yes, they are arbitrary positive integers and p is less than q. – user1580096 Aug 07 '13 at 19:52
1 Answers
1
Here $x$ is a solution if and only if $x+aq$ is for some integer $a$. Therefore you can brute force this by checking $x=0,1,2,\ldots,q-1$ and using the above observation from that point on.
There are several shortcuts for specific inputs $q,k$. For example, if $q$ is a prime, and $k$ has no common divisors with $q-1$, then we know that in the range $0\le x<q$ there will be exactly one solution irrespective of the value of $p$. Such shortcuts rely on an understanding of the multiplicative structure of the ring $\mathbb{Z}_q$ and its group of units.
Jyrki Lahtonen
- 133,153