1

We want to find the minimum natural number that satisfies the equation

$2^{100} \equiv x \bmod 9$

Textbook says: We observe that $2^{3} \equiv 8 \equiv -1\bmod 9$

After that it simply breaks down $2^{100} $ until it reaches the desired form

$(2^3)^{33}2 \equiv (-1)^{33}2 \equiv -2 \equiv x\bmod 9 $

My question is, how did he thought the first step? Why for example chose to break it with $2^3$ and not something else, like $2^4$ for example? Im new to modulo concepts and find it quite confusing

Than1
  • 331
  • 2
    They could have started with other numbers. $2^6\equiv 1\pmod 9$, for instance. The point is simplicity...we want to start with some number $m$ such that we know $2^m\pmod 9$. – lulu Sep 13 '21 at 14:38
  • 3
    Because $2^3=-1$. One just looks $2=2$, $2^2=4$ not much good, $2^3=-1$ oh that makes the sums easy. – ancient mathematician Sep 13 '21 at 14:39
  • 4
    Because $2^{100}=(2^4)^{25}=16^{25}$ is not much more easy to mange than the original $2^{100}$ while $(-1)^{33}$ is... – Mauro ALLEGRANZA Sep 13 '21 at 14:40
  • 2
    Looking for an expression of $2^y \equiv \pm 1$ is always advantageous, since you then know that $2^{kr} \equiv (\pm 1)^r$, which is always easy to compute. – user2661923 Sep 13 '21 at 14:40
  • Related – Rushabh Mehta Sep 13 '21 at 14:41
  • 1
    The smallest natural number satisfying this congruence is nothing else as the remainder , if $2^{100}$ is divided by $9$, so the goal is to determine $2^{100}\mod 9$. Because of $2^3\equiv -1\mod 9$ we have $2^6\equiv 1\mod 9$. That means that we can reduce the exponent modulo $6$ giving $4$. So we have $2^{100}\equiv 2^4=16\equiv 7\mod 9$, hence the answer is $7$. – Peter Sep 13 '21 at 15:04

1 Answers1

1

The idea is to keep it simple stupid (kiss). Unlike just any base, $1$ and $-1$ have easily known powers regardless of modulus. This allows fast computation via $(a^b)^c=a^{bc}$, and $a^b\equiv 1,-1$ . While we could write out $2^{100}$ (as it has under 40 digits), that same approach wouldn't be as feasible long before the exponent reaches $3321928095$ ( a billion or more digits when written out). The smart approach, is to find a pattern that will allow us to not have to write it out. In this case, they've settled for the easiest pattern ($2^{7}\equiv 2$ could also be used ). In fact modular arithmetic is math you can use for telling time, but follows nearly all basic arithmetic rules from grade school.

Roddy MacPhee
  • 859