Not remainders this time?

By modulus properties: $31^{29} \equiv _{41} \left( { - 10} \right)^{29} \equiv _{41} - 10 \cdot 100^{14} \equiv _{41} - 10 \cdot 18^{14} \equiv _{41} - 10 \cdot 324^7$ $31^{29} \equiv _{41} - 10 \cdot \left( { - 4} \right)^7 \equiv _{41} 40 \cdot 64^2 \equiv _{41} - 18^2 \equiv _{41} - 324 \equiv _{41} 4$ Therefore: $31^{29} = 41Q + 4$ Now, we check out every option, first, $15$ : $31^{29} \equiv _{15} 1^{29} \equiv _{15} 1 \equiv _{15} 41Q + 4 \equiv _{15} - 4Q + 4$ $- 4Q + 4 \equiv _{15} 1$ $- 4Q \equiv _{15} - 3 \Rightarrow Q\not \equiv _{15} 0$ $15$ is not a divisor of $Q$ , now for $6$ , notice that $31^{29} \equiv _{6} 1^{29}$ , and thus the result is exactly the same as in the case of $15$ . Finally, we check out the case of $21$ : $31^{29} \equiv _{21} \left( {10} \right)^{19} \equiv _{21} 10 \cdot 100^{14} \equiv _{21} 10 \cdot \left( { - 5} \right)^{14} \equiv _{21} 10 \cdot 25^7$ $31^{29} \equiv _{21} 10 \cdot 4^7 \equiv _{21} 40 \cdot 64^2 \equiv _{21} - 2 \cdot 1^2 \equiv _{21} - 2 \equiv _{21} 41Q + 4$ $41Q + 4 \equiv _{21} - 2$ $- Q \equiv _{21} - 6 \Rightarrow Q\not \equiv _{21} 0$ In conclusion, none of the choices divide $Q$ .

By fermat's theorem 31^40 = 1 mod(41)

But is 40 the smallest values such that 31^x = 1 mod(41)?

clearly, x has to be the divisor of 40. 31^2 = 18 mod(41),

31^4 = 324 mod(41) => 31^4 = -4 mod(41)

=> 31^5 = -124 mod(41) => 31^5 = -1 mod(41)

clearly such smallest x is 10 as 31^10 = (-1)^2 mod(41) => 31^30 = 1 mod(41),

if 31^29 = a mod(41) => 31^30 = 31a mod(41) => 31a = 41K + 1, => a = 4. Thus, 31^29 = 41*Q + 4. => Q is always odd.

If Q is divisible by 5 then 31^29 should leave remainder 4 on division by 5. but 31^29 = (30+1)^29, hence the remainder is 1 by 5.

Similarly, 31^29 leaves 5 by 7 and not 4.

Hence the correct answer is 'none of these choices'

Here all the factors of Q are factors of 31^29. As 21 ,15 and 6 are not factors of 31^29(31 not a factor of 3), Q should not have these as factors or Q is not divisible by them.Hence 'none of these' remains as the answer this time.