What is the remainder?

Question

What is the remainder when 41⁷⁵ is divided by 3?

Answer 1

41/3=13 R2

41²/3=560 R1

41³/3=22,973 R2

41⁴/3=941,920 R1

the remainders oscillate back and forth from 1 to 3 to 1 to 3 ...

(41)⁷⁵=(41³)²⁵

(41³)²⁵/3 leaves a remainder of 2 because you divide 3 into only one of the 25 factors of (41³)

Answer 2

Use the fact that you can mod your value by 3:

 

41⁷⁵ (mod 3) ≡ (41 (mod3))⁷⁵ ≡ (2(mod3))⁷⁵ ≡ (8(mod3))²⁵

≡ (2(mod3))²⁵ ≡ (32(mod3))⁵ ≡ (2(mod3))⁵ ≡ 32(mod3) ≡ 

2(mod3)

 

So the remainder is 2.

 

*Note: I'm sure there is a theorem which makes this easier, but I can't remember it off-hand.

 

Answer 3

          (intentionally left blank)