# Thread: Residue Modulo

1. ## 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!

2. ## Re: Residue Modulo

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

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
}