/*
   Lab : Lab5 
   Day : Tuesday  [ 02 Sept 08 ]

   Problem Number: 01
   Problem Title : Remainder of a large number when divided by a small number
   
   Theory : 

     analyze the expression    ( a^b ) %c      as follows

	   -----------------------------------------------------------------------------------------------
     	    value of b  	( a^b ) %c      
           -----------------------------------------------------------------------------------------------
		1		 a%c  	                                                say it  v_1
                2		(a^2)%c = (  a%c    X a%c )%c = ( v_1 X a%c )%c   	say it  v_2
		3		(a^3)%c = ( (a^2)%c X a%c )%c = ( v_2 X a%c )%c   	say it  v_3
		4		(a^4)%c = ( (a^3)%c X a%c )%c = ( v_3 X a%c )%c   	say it  v_4
		:		:		:		:		:		:
		i		(a^i)%c = ( (a^i-1)%c X a%c )%c = ( v_i-1 X a%c )%c  	say it  v_i		
		:		:		:		:		:		:
		b-2		(a^b-2)%c = ( (a^b-3)%c X a%c )%c = ( v_b-3 X a%c )%c  	say it  v_b-2		
		b-1		(a^b-1)%c = ( (a^b-2)%c X a%c )%c = ( v_b-2 X a%c )%c  	say it  v_b-1
		b		(a^b)%c = ( (a^b-1)%c X a%c )%c = ( v_b-1 X a%c )%c  	say it  v_b
	   -----------------------------------------------------------------------------------------------

        Above analysis explains that we can follow incremental method to find ( a^b ) %c 
 */

class sol_lab5_prob01{

   	public static void main(String args[])
	{		
		int a = 3;   // Assign value to a
		int b = 247; // Assign value to b
		int c = 17;  // Assign value to c
		int i = 1;   // i is used as loop counter
		int result;       // result along with value of i, represents v_i

		result = a % c;   // this value represents v_1
		for( i = 2 ; i <= b ; i++ )
		{
			result = (  result  *  a%c  )%c ;	// as written in step i, result represents v_i		
		}  

		System.out.println("\n ( " +a+" ^ "+b+" ) % "+ c +" = "+ result);
	}	
}