1. ## Congruence equations

How do I solve equations of the form

x^k = a mod m (where m is a composite integer, a and m are relatively prime)

without using the Chinese Remainder Theorem?

I know it will be true that

x^φ(m) = 1 mod m, but what do I do after that?

2. ## Re: Congruence equations

$\displaystyle x^{nk} = \left(x^k\right)^n \equiv a^n \pmod{m}$

You want to find $\displaystyle n\in \mathbb{Z}_{\ge 0}$ such that $\displaystyle nk = p\varphi(m) + 1$ for some integer $\displaystyle p$. In other words, you want to find the solution to $\displaystyle nk \equiv 1 \pmod{\varphi(m)}$. Such a solution only exists if $\displaystyle k$ and $\displaystyle \varphi(m)$ are relatively prime.

But, then, you have:

$\displaystyle x^{nk} = x^{p\varphi(m)+1} = \left(x^{\varphi(m)}\right)^p\cdot x \equiv 1^p\cdot x = x \pmod{m}$

3. ## Re: Congruence equations

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 xk = a (mod m).

First observation. For a = 1, you're just asking for the elements of Zm 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, x4=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);
}

4. ## Re: Congruence equations

I thought a little more about the problem. Here are my thoughts: