Results 1 to 2 of 2

Math Help - Residue Modulo

  1. #1
    Junior Member
    Joined
    Feb 2013
    From
    Charlotte, NC
    Posts
    50

    Residue Modulo

    1.Compute the least positive residue modulo 10,403 of 7651^891




    2.Compute the least positive residue modulo 10,403 of 7651^20!

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    633
    Thanks
    255

    Re: Residue Modulo

    Hi,
    The answer to the first question is 1362 and the second is 1. See the attachment:

    Residue Modulo-mhfmod.png

    Here's a little C program that computes 1362:

    Code:
    #include <stdio.h>
    
    int powmod(int x,int m,int n);
    int chineseRemainderTheorem(int a,int b,int m,int n);
    
    int main(void) {
    	int m=101,n=103,a,b,x;
    	a=powmod(7651,891,m);
    	b=powmod(7651,891,n);
    	x=chineseRemainderTheorem(a,b,m,n);
    	printf("7651^891 mod 101*103 is %d\n",x);
    	if (powmod(7651,891,m*n)!=x) {
    		printf("oops\n");
    	}
    	return(0);
    }
    
    /* 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;
    	temp%=n;
    	if (m%2) {
    		temp*=x;
    	}
    	return(temp%n);
    }
    
    /* Obvious algorithm to compute x with x mod m = a and x mod n = b, given that
       m and n are relatively prime.
    */
    int chineseRemainderTheorem(int a, int b, int m, int n) {
    	a%=m;
    	b%=n;
    	int x=a,k;
    	for (k=0;k<n;k++) {
    		if (x%n==b) {
    			return(x);
    		}
    		x+=m;
    	}
    	return(x); // make compiler happy
    }
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Reduced residue system modulo m
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 20th 2010, 08:12 PM
  2. Distinct residue modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 24th 2009, 02:08 PM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  4. complete residue modulo
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 5th 2009, 02:53 PM
  5. residue modulo - wilson's theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum