2
$\begingroup$

I actually do not have the basic idea on how to approach these type of questions....so please tell me a generalized method about all this too.

It came in RMO, and the question is:

What is the remainder when $2^{1990}$ is divided by $1990$ ?

$\endgroup$
6
$\begingroup$

Using Fermat's Little Theorem,

$2^4\equiv1\pmod 5\implies 2^{1990}=2^2\cdot(2^4)^{997}\equiv4\cdot1^{997}\pmod 5\equiv4\ \ \ \ (1)$

$2^{198}\equiv1\pmod {199}\implies 2^{1990}=2^{10}\cdot(2^{198})^{10}\equiv1024\cdot1^{10}\pmod{199}\equiv 29\ \ \ \ (2)$

Clearly, $2^{1990}\equiv0\pmod2\ \ \ \ (3)$

Apply the famous CRT on $(1),(2),(3)$

$\endgroup$
  • $\begingroup$ So this is a more generalized thing to do these type of questions...thanks again $\endgroup$ – Rohinb97 Oct 31 '13 at 5:57
1
$\begingroup$

As the $(2^{1990},1990)=2$

let us start with $\displaystyle\frac{2^{1990}}2\pmod {\frac{1990}2}$ i.e., $2^{1989}\pmod {995}$

Now $\displaystyle995=5\cdot 199$ and using Carmichael function, $\lambda(995)=396$

As $\displaystyle(2,995)=1, 2^{396}\equiv1\pmod{995}$

As $\displaystyle1989\equiv9\pmod{396},2^{1989}\equiv2^9\pmod{995}$

$\displaystyle\implies2^{1989}\equiv512\pmod{995}\ \ \ \ (1)$

Now we know if $x\equiv y\pmod m, a\cdot x\equiv a\cdot y\pmod {a\cdot m}$ where $a$ is any integer

So, multiply either sides of $(1)$ by $2$

$\endgroup$
  • $\begingroup$ Sounds good and easy...thanks! $\endgroup$ – Rohinb97 Oct 31 '13 at 5:56
  • $\begingroup$ Can I do this method in other questions...like where the numbers are something else? I doubt...but this sounds a lot better $\endgroup$ – Rohinb97 Oct 31 '13 at 5:59
  • $\begingroup$ @Rohinb97, can you supply some example? $\endgroup$ – lab bhattacharjee Oct 31 '13 at 6:22
0
$\begingroup$

Let $ x = 2^{1990}$
$1990 = 2 \cdot 5 \cdot 199$

Find $x_2 = x \pmod 2$
$\qquad 2^{1990} \equiv 2\cdot2^{1989} \equiv 0 \pmod 2$
$\qquad x_2 = 0$

Find $x_5 = x \pmod 5$
$\qquad 2^4 \equiv 1 \pmod 5$
$\qquad 2^{1990} \equiv 2^{4\cdot 497 + 2} \equiv 2^2 \equiv 4 \pmod 5 $
$\qquad x_5 = 4$

Find $x_{199} = x \pmod{199}$
$\qquad 2^{198} \equiv 1 \pmod {199}$
$\qquad 2^{1990} \equiv 2^{198 \cdot 10 + 10} \equiv 2^{10} \equiv 1024 \pmod{199} \equiv 29 \pmod{199}$
$\qquad x_{199} = 29$

Factors of $1990$ are $2, 5, 199$

Find $\alpha_2$ such that $\alpha_2 \equiv (1,0,0) \bmod (2,5,199)$
$\qquad 5 \cdot 199 = 995$
$\qquad 995 \equiv (1,0,0) \bmod{(2,5,199)}$
$\qquad \alpha_2 = 995$

Find $\alpha_5$ such that $\alpha_5 \equiv (0,1,0) \bmod (2,5,199)$
$\qquad 2 \cdot 199 = 398$
$\qquad 398 \equiv (0,3,0) \bmod {(2,5,199)}$
$\qquad 3^{-1} \equiv 2 \pmod 5$
$\qquad 2 \cdot 398 = 796$
$\qquad 796 \equiv (0,1,0) \bmod {(2,5,199)}$
$\qquad \alpha_5 = 796$

Find $\alpha_{199}$ such that $\alpha_{199} \equiv (0,0,1) \bmod (2,5,199)$
$\qquad 2 \cdot 5 = 10$
$\qquad 10 \equiv (0,0,10) \bmod {(2,5,199)}$

$\qquad \qquad $ Find $10^{-1} \pmod{199}$ \begin{array}{r|rrr} & 199 & 1 & 0 \\ -20 & 10 & 0 & 1 \\ & -1 & 1 & -20 \\ & 1 & -1 & \color\red{20} \\ \end{array}
$\qquad \qquad 10^{-1} \equiv 20 \pmod{199}$

$\qquad 20 \cdot 10 = 200$
$\qquad 200 \equiv (0,0,1) \bmod {(2,5,199)}$
$\qquad \alpha_{199} = 200$

$x = \alpha_2 \, x_2 + \alpha_5 \, x_5 + \alpha_{199} \, x_{199} \pmod{1990}$
$x = 0 \cdot 995 + 4 \cdot 796 + 29 \cdot 200 \pmod{1990}$
$x = 1024$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.