Modular Arithmetic Combination

Question

I'm trying to find the remainder of $\frac{2^{2010}}{35}$. The first two parts of the question asked for the remainder when dividing $2^{2010}$ by 5 and then by 7.

To solve for the first two problems, I used Euler's Theorem: $$2^{2010}=(2^{3})^{670}$$ Let $a=2$ and $n=5$, then $$2^{3}\equiv1\pmod 5$$ $$2^{2010}=(2^{3})^{670}\equiv1^{670}\equiv1\pmod5$$ And so I found that the remainder was 1 (please correct me if I made a mistake). I repeated the process for dividing by 7, and got the same result, the only difference where the exponents which did not effect the result.

How would I combine the two results, $2^{2010}\equiv1\pmod5$ and $2^{2010}\equiv1\pmod7$?

Answer 1

Another way:

$$2^4\equiv1\pmod5,2^3\equiv1\pmod7$$

$$\implies2^{\text{lcm}(3,4)}\equiv1\pmod{\text{lcm}(5,7)}$$

Now lcm$(5,7)=35$ and lcm$(3,4)=12,2010\equiv6\pmod{12}$

$$\implies2^{2010}\equiv2^6\pmod{35}\equiv?$$

Answer 2

$$2^{2010} \pmod{35}$$

Note that $2^2 \equiv 4 \equiv -1 \pmod 5$

So $2^{2010} \equiv (2^2)^{1005} \equiv (-1)^{1005} \equiv -1 \pmod 5$

Note that $2^3 \equiv 8 \equiv 1 \pmod 7$

So $2^{2010} \equiv (2^3)^{670} \equiv 1 \pmod 7$

The Chinese remainder theorem states that there is an isomorphism

$$f:\mathbb Z_{35} \to \mathbb Z_5 \times \mathbb Z_7$$

Beyond that, it states that

$f(n) = (n,n)$ and,

if $f(A) = (1,0)$ and $f(B) = (0,1)$, then $f^{-1}(m,n) = Am + Bn \pmod{35}$

Let $n \equiv 2^{2010} \pmod{35}$. You have found that $n \equiv -1 \pmod 5$ and $n \equiv 1 \pmod 7$.

You what to find the value of $n$ for which $f(n) = (-1,1)$.

First we need to find some number $x$ such that $f(x) = (1,0)$ That means $x \equiv 1 \pmod 5$ and $x \equiv 0 \pmod 7$.

$x \equiv 0 \pmod 7$ means that $x$ is a multiple of $7$. The first few multiples of $7$ are $7, 14, 21$ and we see that

$$21 \equiv 1 \pmod 5 \ \text{and} \ 21 \equiv 0 \pmod 7$$

So $f(21) = (1, 0)$

Next we need to find $y$ such that $y \equiv 0 \pmod 5 \ \text{and} \ y \equiv 1 \pmod 7$

Thr first few multiples of $5$ are $5, 10, 15$ and we see that

$$15 \equiv 0 \pmod 5 \ \text{and} \ 15 \equiv 1 \pmod 7$$

It follows that $f^{-1}(-1,1) \equiv -1(21) + 1(15) \equiv -6 \equiv 29 \pmod{35}$

So your answer is that the remainder is $29$.