Remainder (3)

Number Theory Level 3

Find the remainder of 3 3 × 3 3 33 × 33 3 333 × 333 3 3333 \large \color{#D61F06} 3^3\times 33^{33}\times 333^{333}\times 3333^{3333} when divided by 100 \color{#D61F06}100 .

21 19 18 22 20

Hana Wehbi by Hana Wehbi , 51, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Chew-Seong Cheong
Jul 21, 2017

Relevant wiki: Euler's Theorem

3 3 × 3 3 33 × 33 3 333 × 333 3 3333 ≡ 3 3 × 3 3 33 × ( 300 + 33 ) 333 × ( 3300 + 33 ) 3333 (mod 100) ≡ 3 3 × 3 3 33 + 333 + 3333 mod ϕ ( 100 ) (mod 100) Since gcd ⁡ ( 33 , 100 ) = 1 , Euler’s theorem applies. ≡ 3 3 × 3 3 3699 mod 40 (mod 100) Euler’s totient function ϕ ( 100 ) = 40 ≡ 3 3 × 3 3 19 (mod 100) ≡ 9 9 3 × 3 3 16 (mod 100) ≡ ( 100 − 1 ) 3 × 3 3 16 (mod 100) ≡ − 3 3 16 (mod 100) ≡ − 3 16 × 1 1 16 (mod 100) ≡ − ( 10 − 1 ) 8 ( 10 + 1 ) 8 ( 10 + 1 ) 8 (mod 100) ≡ − ( 100 − 1 ) 8 ( 1 0 8 + 8 × 1 0 7 + ⋯ + 8 × 10 + 1 ) (mod 100) ≡ − 81 (mod 100) ≡ 19 (mod 100) \begin{aligned} 3^3 \times 33^{33} \times 333^{333} \times 3333^{3333} & \equiv 3^3 \times 33^{33} \times (300+33)^{333} \times (3300+33)^{3333} \text{ (mod 100)} \\ & \equiv 3^3 \times 33^{33+333+3333 \color{#3D99F6} \text{ mod } \phi(100)} \text{ (mod 100)} \quad \quad \small \color{#3D99F6} \text{Since }\gcd(33,100) = 1 \text{, Euler's theorem applies.} \\ & \equiv 3^3 \times 33^{3699 \color{#3D99F6} \text{ mod } 40} \text{ (mod 100)} \quad \quad \small \color{#3D99F6} \text{Euler's totient function }\phi(100) = 40 \\ & \equiv 3^3 \times 33^{\color{#3D99F6} 19} \text{ (mod 100)} \\ & \equiv 99^3 \times 33^{16} \text{ (mod 100)} \\ & \equiv (100-1)^3 \times 33^{16} \text{ (mod 100)} \\ & \equiv -33^{16} \text{ (mod 100)} \\ & \equiv -3^{16}\times 11^{16} \text{ (mod 100)} \\ & \equiv -(10-1)^8(10+1)^8(10+1)^8 \text{ (mod 100)} \\ & \equiv -(100-1)^8(10^8+8\times10^7+ \cdots + 8 \times 10+1) \text{ (mod 100)} \\ & \equiv -81 \text{ (mod 100)} \\ & \equiv \boxed{19} \text{ (mod 100)} \end{aligned}

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Thank you for sharing a nice solution. This question could also be "the last two digits".

Hana Wehbi - 3 years, 10 months ago

We can shorten this solution by using the Carmichael's lambda function instead of Euler's totient function. λ ( 100 ) = 20 \lambda\left(100\right) = 20 , so 3 3 × 3 3 19 ≡ 27 × 3 3 − 1 ≡ 27 × ( − 3 ) ≡ − 81 ≡ 19 ( m o d 100 ) 3^3 \times 33^{19} \equiv 27 \times 33^{-1} \equiv 27 \times \left(-3\right) \equiv -81 \equiv 19 \pmod{100} because we can easily see that 3 3 − 1 ≡ − 3 ( m o d 100 ) 33^{-1} \equiv -3 \pmod{100} .

Jesse Nieminen - 3 years, 10 months ago

Log in to reply

Thanks for the better solution.

Chew-Seong Cheong - 3 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...