The question is given in the title:
Find the remainder when $2^{31}$ is divided by $5$.
My friend explained me this way:
$2^2$ gives $-1$ remainder.
So, any power of $2^2$ will give $-1$ remainder.
So, $2^{30}$ gives $-1$ remainder.
So, $2^{30}\times 2$ or $2^{31}$ gives $3$ remainder.
Now, I cannot understand how he said the last line. So, please explain this line.
Also, how can I do this using modular congruency?
$\endgroup$6 Answers
$\begingroup$Your friend is wrong in one statement. Indeed you have $2^2 \equiv -1 \pmod 5$. But this implies that $(2^2)^n \equiv (-1)^n \pmod 5$ not that any power of $ 2^2 $ will give $ -1 $ remainder.
However you get $$(2^2)^{15} = 2^{30} \equiv (-1)^{15} = -1 \pmod 5.$$ And therefore $2^{31} \equiv 2 \cdot 2^{30} = -2 = 3 \pmod 5$.
$\endgroup$ 1 $\begingroup$We have that $5$ is a prime, so, $2^4 \equiv 1 \pmod 5$ (see Fermat's little theorem).
Then, $(2^4)^{7} = 2^{28} \equiv 1 \pmod 5$. Multiplying this by $2^3$, we get $2^{31} \equiv 8 \equiv 3 \pmod 5$.
Your friend is saying that:
$$2^{30} \equiv -1 \pmod 5 \implies 2^{31} \equiv -1 \times 2 \equiv -2 \equiv -2 + 5 \equiv 3 \pmod 5.$$
$\endgroup$ 1 $\begingroup$The salient feature here is that when taking the remainder of a product modulo some integer, it doesn't matter if you first take the remainder or first compute the product. In other words: $$ab = (a \bmod n)(b \bmod n) \bmod n$$ Thus $2^{30} \times 2 =(2^{30} \bmod 5)(2\bmod 5) = ((-1)^{15} \bmod 5)2 = -2 = 3 \bmod 5$
$\endgroup$ 2 $\begingroup$This may be easier: $2^4$ is $16$. Clearly this gives a remainder of $1$. Another way of saying this is that $2^4=5k+1$ for some $k$.
Thus $2^{28}=(2^4)^7=(5k+1)^7$ and if you have ever expand out terms you know that the last constant will still be $1$ and everything else will have a $5k$ in it. Thus the remainder divided by $5$ is still $1$.
Similarly $2^{31}=2^{28}\cdot 2^3$, and since $2^3=8$ has a remainder of $3$, we have two terms who when you multiply you get a reminder of $1\cdot 3$.
$\endgroup$ 0 $\begingroup$Notice the pattern.
2 divided by 5 remainder is 2.
4 divided by 5 remainder 4.
8 divided by 5 remainder 3.
16 divided by 5 remainder 1.
For 32 it is 2 again , 64 - 4, 128 - 3, 256- 1 and so on.
So for 2 to the power 31 -
Remainder is 2 for the power 29 and 3 for the power 31.
From Fermat's Little Theorem-
$a^{p-1}\equiv1\pmod p$
Putting $a=2$ and $p=5$ we have,
$2^4\equiv 1\pmod 5$
$\implies 2^{28}\equiv 1\pmod 5$
Now,$2^{31}=2^{28}\times 2^{3}$.So,it is equivalent to finding the remainder when $2^3$ is divided by $5$..which is $3$.So,the remainder when $2^{31}$ is divided by $5$ is $3$..
$\endgroup$
