Wednesday, September 23, 2009

Beginner in Number Theory

Here is a small code for solving the problems of the following type:

Find the remainder when a^n is divided by div.

In this program, supply the values of a, n and div. You will get the remainder.

To solve the problem, we use the following property:--
If a ~ b (mod n) and c ~ d (mod n) then ac ~ bd (mod n).

Note: If you want to see the last digit of a^n, set div=10; for last two digits, set div=100 etc.

Here is the code: (Replace HEADER by stdio.h, within angle brackets)

#include HEADER
int main()
{
int n, i, b=1,a,div;
printf("\nEnter the base:");
scanf("%d",&a);
printf("\nEnter the power:");
scanf("%d",&n);
printf("\nEnter the divisor:");
scanf("%d",&div);
for(i=1;i<=n;i++)
{
b=b*a;
if(b>=div)
b=b%div;

printf("\n%d^%d ~ %d (mod %d)\n",a,i,b,div);
}
return 0;
}