How do I solve equations of the form

x^k = a mod m (wheremis a composite integer,aandmare 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?

Printable View

- November 10th 2013, 07:51 AMeuphonyCongruence 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? - November 10th 2013, 08:39 AMSlipEternalRe: Congruence equations

You want to find such that for some integer . In other words, you want to find the solution to . Such a solution only exists if and are relatively prime.

But, then, you have:

- November 11th 2013, 10:43 AMjohngRe: Congruence equations
Hi,

Since you didn't place any restriction on k, I'll assume k could be from 2 to . 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);

}

- November 11th 2013, 06:06 PMjohngRe: Congruence equations
I thought a little more about the problem. Here are my thoughts:

Attachment 29711