Formally prove that $3^ {80} - 2^{20}$ divisible by $5$

Question

I am not sure how to formally prove that prove that $3^{80} - 2^{20}$ divisible by $5$; any hints would be much appreciated. My initial approach was to write a table with examples that when both $3$ and $2$ at an even exponent their difference is divisible by $5$ while if the exponents are odd, the difference is not divisible by $5$.

Answer 1

A number is divisible by $5$ if the units digit is $0$ or $5$.

$3^1=003$

$3^2=009$

$3^3=027$

$3^4=081$

$3^5=\_\_3$

$3^6=\_\_9$

$3^7=\_\_7$

...

$3^{80}=\_\_1$

Similarly $2^n$ cycles units digits $(2 , 4 , 8 , 6)$ for $n>0$

$6-1 = 5$

Answer 2

$3^{80} \mod 5 = 9^{40} \mod 5 = (-1)^{40} \mod 5 = 1 \mod 5$.

$2^{20} \mod 5 = 4^{10} \mod 5 = (-1)^{10} \mod 5 = 1 \mod 5$.

The difference is $0\mod 5$.

Edit:

$m \mod n$ is the remainder of the integer division of $n$ by $m$.

Answer 3

That thinking is along the right track, yeah. What you need to do with questions like this is to think in terms of modular arithmetic. Specifically, you want apply three facts: if $a$ is divisible by $5$, then $a\equiv 0 \mod(5)$; if $a\equiv p \mod(5)$ and $b\equiv q \mod(5)$, then $a+b\equiv p+q \mod(5)$; finally, if $a\equiv p\mod(5)$, then $a^k\equiv p^k \mod(5)$.

Now, here's the deal. We first want to find $r$ and $s$ such that $3^r\equiv 2^s\mod(5)$. These are called the multiplicative orders of $2$ and $3$ (modulo $5$) and can be found by multiplying successive numbers of $3$ and $2$ with themselves until the result of each has the same remainder when divided by $5$; spoiler alert, it turns out that $r=s=4$ are these multiplicative orders. That's because $3^4=81$, which obviously has a remainder of $1$; likewise, $2^4=16$, which also has a remainder of $1$.

Now we apply the third fact: if $3^4\equiv 1\mod(5)$, then $(3^4)^k \equiv 1^k \mod(5)$, for all natural values of $k$, and similarly for $2^4$. Of course, $1^k\equiv 1\mod(5)$ (this is true regardless of any nonzero modulus). Now notice that $80=4\times20$ and that $(3^4)^{20} = 3^{80}$. By the fact just established, this means that $3^{80}\equiv 1 \mod(5)$. As mentioned, this also true for $(2^4)^k$; the factorization in this case is $(2^4)^5$.

To recap, we have determined that $3^{80}\equiv 2^{20}\equiv 1\mod(5)$. We now apply the second fact to obtain that $3^{80}-2^{20}\equiv 1-1\equiv 0 \mod(5)$; by the first fact, this means that $3^{80}-2^{20}$ is divisible by $5$. QED.

Answer 4

If you know That $a^n-b^n$ is always divisible by $a-b$, Then the solution is simple

consider number $$3^{80}-2^{20}=3^{80}-(2)^{20}=3^{80}-2^{80}+2^{80}-2^{20}$$

$$=[3^{80}-(-2)^{80}]+[2^{80}-2^{20}]$$

Now first term is of form $a^n-b^n$ where $a=3,b=-2,n=80$ hence $3^{80}-(-2)^{80}$ is divisible by $3-(-2)=5$

now second term is $$[2^{80}-2^{20}]=2^{20}[2^{60}-1]=2^{20}[4^{30}-(-1)^{30}]$$ which is again divisible by $4-(-1)=5$

as both terms are divisible by $5$, Their addition that is required number, is also divisible by $5$

Q.E.D