@ revival
buddy...cud u plz xplain me the "mod" sol approach to ques below...im nt able to undersatnd the "mod" solution process...
find the remainder when (38^16!)^1777 is divided by 17
Buddy, it is very simple. 'mod' simply is an operation which gives you the remainder when a number is divided by another.
Ex: 16 mod 9 = 8 because the remainder when 16 is divided by 9 is 8.
The method by which you solve these problems is known as remainder theorem.
I will give an example which will allow you to understand how this remainder theorem is used and then will solve the question asked by you.
Remainder Theorem:
Suppose you have to find what is the remainder when 16*12*13*4 is divided by 9.
What you do is, you check what is the remainder when each of the numbers in the numerator is individually divided by 9.
Which is, effectively that number(the one in the numerator) mod 9
16 mod 9 = 7
12 mod 9 = 3
13 mod 9 = 4
4 mod 9 = 4.
Once you obtain these numbers, you can find the remainder when (7*3*4*4) is divided by 9. It will be the same as the remainder when (16*12*13*3) is divided by 9.
So, the question reduces to: (7*3*4*4) mod 9.
= (21*16) mod 9.
Again, we can find the individual remainders: 21 mod 9 = 3
16 mod 9 = 7.
So, the question further reduces to (3*7) mod 9.
=21 mod 9 = 3.
So, when 16*12*13*3) is divided by 9 the remainder is 3.
The same question could have been done using the following method:
You can always cancel any common factors in the numerator and denominator and find the remainder. But remember to multiply the remainder you finally obtain by the factors you cancelled.
For example, for the same question, we could have done: (16*12*13*4) mod 9 --->
(16*4*13*4) mod 3 -----> (1*1*1*1) mod 3 = 1. But, since we have cancelled out a factor of 3, we need to multiply it back.
So, the final remainder is 1*3 = 3, which is the same as we obtained before.
Another approach to Remainder Theorem (Using negative remainders)
There is another way to solve the above question, using the method of negative remainders.
Suppose, we divide 99 by 100. The remainders can be written as 99 or -1.
Here, the concept is that since negative remainders are not possible, we need to add back the negative remainder that we obtain to the divisor.
Negative remainders are a handy tool and can be used in the question asked by you.
Suppose we need to find the remainder when 1001*10005*998*1003 is divided by 1000.
(1001*10005*998*1003) mod 1000 = (1*5*-2*3) mod 1000 = -30.
So, final remainder is 1000 - 30 = 970.
Suppose it would have been: (1001*10005*998*1003*997) mod 1000:
(1001*10005*998*1003*997) mod 1000 ---> 1*5*-2*3*-3 mod 1000 ---> 90 mod 1000 = 90.
So, final remainder is 90.
Your question: (38^16!)^1777 mod 17.
= (19*2)^(16!*1777) mod 17.
= 19^(16!*1777) * 2^(16!*1777) mod 17
= 2^(16!*1777) * 16^(16!*1777/4) mod 17
= 16^(16!*1777/4) * 16^(16!*1777/4) mod 17
= -1^(16!*1777/4) * -1^(16!*1777/4)
= 1*1 = 1 (Since 16! is even, so the whole power is even)
So, the final remainder is 1.
---------------------------------------------------------------------------------------------------
P.S: I think I was able to explain it. If you face any problems, do get back to me. :thumbsup:
- the number of steps I used here was just for an explanation. The questions can be solved really fast if one is handy with the remainder theorem.
