Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - Congruence equations

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Pennsylvania
    Posts
    23

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    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}
    Last edited by SlipEternal; November 10th 2013 at 07:42 AM.
    Thanks from euphony
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    659
    Thanks
    271

    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);
    }
    Last edited by johng; November 11th 2013 at 10:01 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    659
    Thanks
    271

    Re: Congruence equations

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

    Congruence equations-mhfnumbertheory5.png
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Equations
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: October 15th 2011, 01:54 AM
  2. Prime numbers and congruence equations.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 21st 2010, 11:54 PM
  3. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 17th 2010, 10:10 PM
  4. solving congruence equations
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 9th 2009, 02:17 PM
  5. Congruence Equations
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2006, 07:02 PM

Search Tags


/mathhelpforum @mathhelpforum