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;

}

## No comments:

Post a Comment