# Congruence equations

• Nov 10th 2013, 07:51 AM
euphony
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?
• Nov 10th 2013, 08:39 AM
SlipEternal
Re: Congruence equations
$x^{nk} = \left(x^k\right)^n \equiv a^n \pmod{m}$

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

But, then, you have:

$x^{nk} = x^{p\varphi(m)+1} = \left(x^{\varphi(m)}\right)^p\cdot x \equiv 1^p\cdot x = x \pmod{m}$
• Nov 11th 2013, 10:43 AM
johng
Re: Congruence equations
Hi,
Since you didn't place any restriction on k, I'll assume k could be from 2 to $\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); }
• Nov 11th 2013, 06:06 PM
johng
Re: Congruence equations
I thought a little more about the problem. Here are my thoughts:

Attachment 29711