# Prove or disprove $a^{10}=b^{10} \pmod{10\alpha}$

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.

• $1990$ is not prime... It is obviously a multiple of $10$. – MoebiusCorzer Dec 21 '16 at 13:19
• i was providing refrence of question but main question is to prove or disprove property I used – Blaise Thunderstorm Dec 21 '16 at 13:37
• As a record, this question already has many alternative methods to prove the question in reference, but does not address the titular question. – Balarka Sen Dec 21 '16 at 14:50
• 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. – Daniel Fischer Dec 21 '16 at 14:51
• 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. – Doug M Dec 21 '16 at 15:45

## 1 Answer

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.