Think of the number next to 1999

Find the last two digits in the decimal representation of 2 1999 + 3 1999 2^{1999}+3^{1999} .


The answer is 55.

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.

3 solutions

Chew-Seong Cheong
Jun 25, 2016

Relevant wiki: Euler's Theorem

Since 2 and 100 are not coprime, we have to consider 2 1999 m o d 4 2^{1999} \mod 4 and 2 1999 m o d 25 2^{1999} \mod 25 separately.

{ 2 1999 2 4 999 0 ( m o d 4 ) 2 1999 2 1999 m o d ϕ ( 25 ) 2 1999 m o d 20 2 19 1024 512 12 88 ( m o d 25 ) \begin{cases} 2^{1999} \equiv 2\cdot 4^{999} \equiv 0 \pmod 4 \\ 2^{1999} \equiv 2^{1999 \mod \phi (25)} \equiv 2^{1999 \mod 20} \equiv 2^{19} \equiv 1024 \cdot 512 \equiv -12 \equiv 88 \pmod {25} \end{cases}

Since 88 { 0 ( m o d 4 ) 88 ( m o d 25 ) 2 1999 88 ( m o d 100 ) 88 \equiv \begin{cases} 0 \pmod 4 \\ 88 \pmod {25} \end{cases} \implies 2^{1999} \equiv 88 \pmod {100}

Now, consider ( edited as suggested by @Alex G ):

x 3 1999 ( m o d 100 ) 3 x 3 2000 ( m o d 100 ) 3 2000 m o d ϕ ( 100 ) ( m o d 100 ) 3 2000 m o d 40 ( m o d 100 ) 1 ( m o d 100 ) 3 x 201 ( m o d 100 ) x 67 ( m o d 100 ) 3 1999 67 ( m o d 100 ) \begin{aligned} x & \equiv 3^{1999} \pmod{100} \\ 3x & \equiv 3^{2000} \pmod{100} \\ & \equiv 3^{2000 \mod \phi(100)} \pmod{100} \\ & \equiv 3^{2000 \mod 40} \pmod{100} \\ & \equiv 1 \pmod{100} \\ \implies 3x & \equiv 201 \pmod{100} \\ \implies x & \equiv 67 \pmod{100} \\ 3^{1999} & \equiv 67 \pmod{100} \end{aligned}

2 1999 + 3 1999 88 + 67 155 55 ( m o d 100 ) \implies 2^{1999}+3^{1999} \equiv 88 + 67 \equiv 155 \equiv \boxed{55} \pmod {100}

@Chew-Seong Cheong : evaluating 3 1999 m o d 100 3^{1999} \mod 100 can be made simpler by letting x 3 1999 m o d 100 x \equiv 3^{1999} \mod 100 , multiplying by 3 to both sides and then using ϕ ( 100 ) = 40 \phi(100) = 40 , resulting in 3 x 1 m o d 100 3x \equiv 1 \mod 100 . This means that either 3 x = 101 3x = 101 or 3 x = 201 3x=201 , as x is an integer x = 67 x=67 .

This same principle can be applied to evaluate 2 1999 m o d 25 2^{1999} \mod 25 without using brute force.

Alex G - 4 years, 11 months ago

Log in to reply

Thanks. I have changed the solution to show that.

Chew-Seong Cheong - 4 years, 11 months ago

this is better

Ayush G Rai - 4 years, 11 months ago

Actually it is better to consider ϕ ( 25 ) = 20 \phi(25)=20 to make it easier to compute.

Alex Spagnoletti - 4 years, 11 months ago

Log in to reply

Thanks. It was a mistake there.

Chew-Seong Cheong - 4 years, 11 months ago

Log in to reply

Now it's perfect ;)

Alex Spagnoletti - 4 years, 11 months ago
Gaurav Gupta
Jun 26, 2016

Did same but also calculated by elementary method by writting2^1999 =16^499*2 and using cyclity of two digits of 16 and similarly by using cyclity of 81

Observe that 2 100 76 ( m o d 100 ) 2^{100}\equiv 76 \pmod{100} and 3 100 1 ( m o d 100 ) 3^{100}\equiv 1 \pmod{100} . Thus,

2 1999 + 3 1999 2 99 + 3 99 88 + 67 55 ( m o d 100 ) 2^{1999}+3^{1999}\equiv 2^{99}+3^{99}\equiv 88+67 \equiv 55\pmod{100}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...