I am trying to prove that $7|3^{41}-5$.
The way I have been approaching this problem is by trying to factor the exponent of $41$ into a product of smaller exponents that will help me find a number that is divisible by $7$ with a remainder of $5.$
I have not gotten far, but my idea is:
$3^{41} = (3^{2})^{20}\times 3 – 5$
The part that I am getting hung up on is the fact that $41$ is a prime number. In my class, we have done examples where the exponent is factorable, so there is not a lingering 3 being multiplied into the factored exponent. I believe I understand the process of how this works when the exponent is not a prime number, but I cannot seem to understand how to accomplish this proof given these parameters.
We have covered modular arithmetic in this class and I am thinking maybe I should be using that to handle this problem, but I am not sure how to do so.
Best Answer
Fermat's little theorem: since $7$ is prime, we have $3^6\equiv1\pmod7$. Thus $3^{42}\equiv(3^6)^7\equiv1$. Thus we just need to "divide by $3$". What's the inverse of $3 \pmod7$? It's $5$, since $5\cdot3\equiv15\equiv1\pmod7$. Thus we get the result.