Hi,
Since you didn't place any restriction on k, I'll assume k could be from 2 to $\displaystyle \phi(m)$. Further, I'm assuming you want all solutions x of the congruence x^{k} = a (mod m).
First observation. For a = 1, you're just asking for the elements of Z_{m} which have multiplicative order a divisor of k. From the well known structure of this group, for a given k it's "easy" to specify the number of such solutions. However, I know of no way to easily identify the solutions x.
For a > 1, I don't know of any formula for the number of solutions.
Example: m=15, a=4 and k=6. The 4 solutions are x=2, 7, 8 and 13. Here since phi(15) = 8, x^{4}=1 for any x and so this solution set is the same as for k=2. But I don't see how to generalize this.
Here's a little C program that computes the solutions x for given a, k and m; for small m it's quite reasonable.
Code:
#include <stdio.h>
#define MAX 500
int solns[MAX];
/* findSolutions finds all x with x^k congruent to a mod m where a is prime to m.
The return is the number of such x with solns array filled out with said x's.
*/
int findSolutions(int k, int a, int m);
int gcd(int a,int b);
int main(void) {
int a,m=15,k,solnCount,i;
int phi=1;
for (i=2;i<m;i++) {
if (gcd(i,m)==1) {
phi++;
}
}
for (a=1;a<m;a++) {
if (gcd(a,m)==1) {
for (k=2;k<phi;k++) {
solnCount=findSolutions(k,a,m);
if (solnCount>0) {
printf("a=%d k=%d solns=%d\n",a,k,solnCount);
for (i=0;i<solnCount;i++) {
printf("%d ",solns[i]);
}
printf("\n");
}
}
}
}
return(0);
}
/* Uses the Euclidean algorithm to compute d=gcd(a,b). Here, a and b MUST be
positive.
*/
int gcd(int a,int b) {
int r;
while (b!=0) {
r=a%b;
a=b;
b=r;
}
return(a);
}
/* Recursive computation of x^m mod n (so n != 0) where m>0.
Of course ints involved must be all < MAX_INT and also n^2 < MAX_INT
Algorithm works because x^m=(x^(m/2))^2*x^(m%2). At each step the result
is reduced mod n.
*/
int powmod(int x,int m,int n) {
int temp;
if (m==1) {
return(x%n);
}
temp=powmod(x,m/2,n);
temp*=temp;
if (m&1==1) {
temp%=n;
temp*=x;
}
return(temp%n);
}
int findSolutions(int k, int a, int m) {
int count=0,x;
a%=m;
for (x=1;x<m;x++) {
if (gcd(x,m)==1 && powmod(x,k,m)==a) {
solns[count++]=x;
}
}
return(count);
}