What will be the reminder when (1234567890123456789)^24 is divided by 6561

Compute (1234567890123456789)^24 mod 6561. Note that 6561 = 3^8.

Find the power of 3 dividing the base.

• Sum of digits = 1+2+...+9+0+1+...+9 = 90, so the number is divisible by 9.

• To check divisibility by 27, group the decimal digits in blocks of three because 1000 ≡ 1 (mod 27). The three-digit groups are: 1, 234, 567, 890, 123, 456, 789.

• Their sum is 1+234+567+890+123+456+789 = 3060, and 3060 ≡ 9 (mod 27). So the base ≡ 9 (mod 27), i.e. divisible by 9 but not by 27. Therefore the 3-adic valuation v3(base) = 2.

• Then v3((base)^24) = 24 × v3(base) = 24 × 2 = 48, which is ≥ 8.

Since (base)^24 is divisible by 3^8 = 6561, the remainder upon division by 6561 is 0.