Saturday, May 20, 2017

elementary number theory - Prove that if $n$ is a positive integer then $2^{3n}-1$ is divisible by $7$.



I encountered a problem in a book that was designed for IMO trainees. The problem had something to do with divisibility.




Prove that if $n$ is a positive integer then $2^{3n}-1$ is divisible by $7$.




Can somebody give me a hint on this problem. I know that it can be done via the principle of mathematical induction, but I am looking for some other way (that is if there is some other way)



Answer



Hint: Note that $8 \equiv 1~~~(\text{mod } 7)$.

So,
$$2^{3n}=(2^3)^n=8^n\equiv \ldots~~~(\text{mod } 7)=\ldots~~~(\text{mod } 7)$$
Try to fill in the gaps!



Solution:
Note that $8 \equiv 1~~(\text{mod } 7)$. This means that $8$ leaves a remainder of $1$ when divided by $7$. Now assuming that you are aware of some basic modular arithmetic,
$$2^{3n}=(2^3)^n=8^n\equiv 1^n ~~(\text{mod } 7)=1~~(\text{mod } 7)$$
Now if $2^{3n}\equiv 1~~(\text{mod } 7)$ then it follows that,


$$2^{3n}-1=8^n-1\equiv (1-1)~~(\text{mod } 7)~\equiv 0~~(\text{mod } 7)\\ \implies 2^{3n}-1\equiv 0~~(\text{mod } 7)$$
Or in other words, $2^{3n}-1$ leaves no remainder when divided by $7$ (i.e. $2^{3n}-1$ is divisible by $7$). As desired

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...