1
$\begingroup$

Today I got a question:

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

I tried as follows

$199$ is a prime, so by Fermat's theorem

$$2^{199}\equiv 2 \pmod{199}$$

Now I used if $$a\equiv b \pmod{\alpha}$$

Then $$a^{10}\equiv b^{10}\pmod{ 10\alpha}$$

Then$$2^{1990}\equiv 2^{10}\pmod{1990}$$

Which is the answer.

But I am not able to prove the property that I had used. I would be pleased if someone would help me to prove or disprove the property. If I had used a wrong property then please provide other method to find the remainder.

$\endgroup$
  • $\begingroup$ $1990$ is not prime... It is obviously a multiple of $10$. $\endgroup$ – MoebiusCorzer Dec 21 '16 at 13:19
  • $\begingroup$ i was providing refrence of question but main question is to prove or disprove property I used $\endgroup$ – Blaise Thunderstorm Dec 21 '16 at 13:37
  • $\begingroup$ As a record, this question already has many alternative methods to prove the question in reference, but does not address the titular question. $\endgroup$ – Balarka Sen Dec 21 '16 at 14:50
  • $\begingroup$ The property doesn't hold, consider for example $a = 2,\, b = 5,\, \alpha = 3$. Then $a^{10}$ is even and $b^{10}$ is odd, so they can't be congruent modulo any even integer. $\endgroup$ – Daniel Fischer Dec 21 '16 at 14:51
  • $\begingroup$ You can say that if $a\equiv b\pmod x \implies a^n\equiv b^n\pmod x$ But you do not change the modulo. $\endgroup$ – Doug M Dec 21 '16 at 15:45
0
$\begingroup$

The claimed property is false. Let's look at the exact instance you attempt to use here, namely $\, a \equiv 2\pmod{\!199}\Rightarrow\, a^{\large 10}\equiv 2^{\large 10}\pmod{\!1990}.\,$ Notice that $ $ odd $\,a:= 201 \equiv 2\,\pmod{\!199}\,$ $\, $ however we have $ $ odd $\,a^{\large 10}\!\neq 2^{\large 10}\!+1990k= $ even, so it fails. Below is one correct proof.

By Fermat $\, 2^{\large 4}\! \equiv 1\pmod{\! 5},\,\ 2^{\large 198}\!\equiv 1\pmod{\!199}\ $ so $\ \color{#c00}{2^{\large 396}\equiv \bf 1}\pmod {5\cdot 199}$

Therefore $\,\ {\rm mod}\,\ \color{#0a0}{5\cdot 199\!:\,\ 2^{\large 1998}}\! \equiv 2^{\large 9+5(396)}\! \equiv 2^{\large 9} (\color{#c00}{2^{\large 396}})^{\large 5}\!\equiv 2^{\large 9}{\color{#c00}{\bf 1}}^{\large 5}\!\equiv \color{#0a0}{2^{\large 9}} $

So $\,\ 2^{\large 1990}\!\bmod 1990\, =\, 2\,(\color{#0a0}{2^{\large 1989}\!\bmod\ 5\cdot 199})\, =\, 2(\color{#0a0}{2^{\large 9}}) = 2^{\large 10} =1024$

We used $\ ca\bmod cn =\, c\,(a\bmod n)\ $ in the prior line. See here for more on that.

$\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.