DRDO CSE 2022 Paper 2 | Question: 24

Question

Compute the following: $3^{32} \bmod 80$.

Answer 1

In the first method, we used the property (a * b) % m = (a % m * b % m) % m to compute 3^32 mod 80 as follows:

3^32 % 80 = (3^16 % 80 * 3^16 % 80) % 80 = (10304 % 80 * 10304 % 80) % 80 = (24 * 24) % 80 = 576 % 80 = 16

In the second method, we used the fact that 3^2 = 9 mod 80 to rewrite 3^32 as (3^2)^16, and then used the property (a^b) % m = (a % m)^b % m to compute 3^32 mod 80 as follows:

3^32 % 80 = (3^2)^16 % 80 = (9^16) % 80 = (6561^8) % 80 = (2401^8) % 80 = (1^8) % 80 = 1 % 80 = 1

Both of these methods are valid and will give the correct result, which is 3^32 mod 80 = 16.

 

@gatecse correct me if i m wrong

Comments

@DebRC I am not sure of it. I also would follow @ankitgupta.1729 Sir’s approach to this q. 

---

@Hira Thakuryou can check it by both method for large value  like in this question.

u get unexpected result from the limited calculator this give overflow

---

“just putting value in the gate calculator always gives the correct result??”

No, for this question, it would work but not for all the similar questions. Mod is defined for integers and if your calculator shows some numbers in the form of “E” as @Abhrajyoti00 has mentioned, it means that number is written in power of 10 with some decimal number and so we can’t get the exact result.

Here, you can get the integer value for $3^{32},$ So you can get the correct answer on your gate calculator.

If the number is big and still you have to use your gate calculator without any error then you can use the “repeating squaring” method.

For example, if the question is $3^{128} \mod 80$ then your gate calculator would not work but still you can use the gate calculator as:

 $3^{128} \mod 80 = (3^{64} \mod 80 \times 3^{64} \mod 80) \mod 80$

 $= ((3^{32} \mod 80 \times 3^{32} \mod 80) \mod 80  \times (3^{32} \mod 80 \times 3^{32} \mod 80)\mod 80 ) \mod 80$

Now, using gate calculator, $3^{32} \mod 80 = 1$

And So, your answer should be $1.$

Answer 2

3^32 = (3^4)^8 = 81^8  , So 3^32 mod 80 = 81^8 mod 80

Now , a^b mod m = ((a mod m) . (a mod m)... b times) mod m) , so 81^8 mod 80 = ((81 mod 80) . (81 mod 80)...8times ) mod 80

81 mod 80 = 1

(1.1.1.1.1.1.1.1 )mod 80 = 1 (Ans)

Answer 3

3³² ≅ (3⁴)⁸ mod 80 ≅ (81)⁸ mod 80 ≅ 1 mod 80

Hence ans is 1