Finding the remainder

Number Theory Level 4

Find the remainder when 2 1990 2^{1990} is divided by 1990.


The answer is 1024.

Deepansh Jindal by Deepansh Jindal , 19, India

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 22, 2016

Relevant wiki: Euler's Theorem

Since 2 and 1990 ( = 2 × 5 × 199 =2\times 5 \times 199 ) are not coprime integers, we have to consider 2 1990 mod 2 2^{1990} \text{ mod }2 , 2 1990 mod 5 2^{1990} \text{ mod }5 , and 2 1990 mod 199 2^{1990} \text{ mod }199 separately.

2 1990 ≡ 0 (mod 2) \begin{aligned} 2^{1990} & \equiv 0 \text{ (mod 2)} \end{aligned}

2 1990 ≡ 2 1990 mod ϕ ( 5 ) (mod 5) As gcd ⁡ ( 2 , 5 ) = 1 , Euler’s theorem applies ≡ 2 1990 mod 4 (mod 5) ϕ ( 5 ) = 4 ≡ 2 2 (mod 5) ≡ 4 (mod 5) \begin{aligned} 2^{1990} & \equiv 2^{\color{#3D99F6}{1990 \text{ mod } \phi(5)}} \text{ (mod 5)} & \small \color{#3D99F6}{\text{As }\gcd(2,5) = 1 \text{, Euler's theorem applies}} \\ & \equiv 2^{\color{#3D99F6}{1990 \text{ mod } 4}} \text{ (mod 5)} & \small \color{#3D99F6}{\phi(5)=4} \\ & \equiv 2^{\color{#3D99F6}{2}} \text{ (mod 5)} \\ & \equiv 4 \text{ (mod 5)} \end{aligned}

2 1990 ≡ 2 1990 mod ϕ ( 199 ) (mod 199) As gcd ⁡ ( 2 , 199 ) = 1 , Euler’s theorem applies ≡ 2 1990 mod 198 (mod 199) ϕ ( 199 ) = 198 ≡ 2 10 (mod 199) ≡ 1024 (mod 199) \begin{aligned} 2^{1990} & \equiv 2^{\color{#3D99F6}{1990 \text{ mod } \phi(199)}} \text{ (mod 199)} & \small \color{#3D99F6}{\text{As }\gcd(2,199) = 1 \text{, Euler's theorem applies}} \\ & \equiv 2^{\color{#3D99F6}{1990 \text{ mod } 198}} \text{ (mod 199)} & \small \color{#3D99F6}{\phi(199)=198} \\ & \equiv 2^{\color{#3D99F6}{10}} \text{ (mod 199)} \\ & \equiv 1024 \text{ (mod 199)} \end{aligned}

Since 1024 ≡ 0 (mod 2) ≡ 4 (mod 5) ≡ 1024 (mod 199) 1024 \equiv 0 \text{ (mod 2)} \equiv 4 \text{ (mod 5)} \equiv 1024 \text{ (mod 199)} ⟹ 2 1990 ≡ 1024 (mod 1990) \implies 2^{1990} \equiv \boxed{1024} \text{ (mod 1990)} .

10 Helpful 0 Interesting 0 Brilliant 0 Confused

Deepansh How did you do it?

Achal Jain - 4 years, 10 months ago

Very nice solution, one small typo. The fourth, third and second from last last line should all be (mod 199), not (mod 5).

Wei Chen - 4 years, 10 months ago

Log in to reply

Thanks.Cut and paste without checking.

Chew-Seong Cheong - 4 years, 10 months ago

I don't get the last step.Like, why is the last step directly implying the conclusion? I didn't have to face it because I used CRT, which does get messy, but is handy if progress is made in a systematic manner.

Mehul Arora - 4 years, 10 months ago

Log in to reply

We need to find a number n n such that n ≡ 0 (mod 2) ≡ 4 (mod 5) ≡ 1024 (mod 199) n \equiv 0 \text{ (mod 2)} \equiv 4 \text{ (mod 5)} \equiv 1024 \text{ (mod 199)} . Now, let n = 1024 n=1024 and it satisfies.

Chew-Seong Cheong - 4 years, 10 months ago

Log in to reply

Will solution be accepted at an olympiad? I mean, this is number checking, isn't it?

Mehul Arora - 4 years, 10 months ago

Log in to reply

@Mehul Arora – I see this as similar to CRT. It just happens that 1024 satisfies the three conditions, else we have to use CRT. In fact 1024 is just an obvious solution. I just used n n to explain I didn't really need to do number checking. 0 ( m o d 2 ) 0 \pmod{2} means that the number is even which 1024 is. 4 ( m o d 5 ) 4 \pmod{5} means the number ends with 4, which 1024 is. 1024 ( m o d 1990 ) 1024 \pmod{1990} is 1024.

Chew-Seong Cheong - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...