Question
Find the remainder of \dfrac{5^{22}+7}{8}
Find the remainder of \dfrac{5^{22}+7}{8}
Let's denote r as remainder and evaluate the remainder of 8 divide 5^n
n =1, 5/8, r =5
n=2, 25/8, r=1
n=3, 125/8, r=5
n=4, 625/8, r =1
...
It is observated when n is odd, the reminder of 8 divide 5^n is 5 and when is even, the remainder of 8 divide 5^n is 1.
Therefor
The remainder of \dfrac{5^{22}}{8} is 1. The remainder of \dfrac{5^{22}+7}{8} is 0
Using the identity
x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1)
Using the power rule for exponent, the original expression is transformed to
\dfrac{5^{22}+7}{8} = \dfrac{25^{11}-1+8}{8}
Apply the binomial identity
25^{11}-1
= (25-1)(25^{10}+25^9+\dots+25+1)
=24\cdot (25^{10}+25^9+\dots+25+1)
Let k = 25^{10}+25^9+\dots+25+1
Obviously k is an integer
Then,
\dfrac{5^{22}+7}{8}
=\dfrac{24k+8}{8}
=3k+1
which leaves no remainder.