Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
2  
Hint $2^{3n}=8^n$ –  Thomas Andrews Aug 23 '12 at 16:07
1  
Implicitly, somewhere induction will be involved. You can prove it directly using theorems, but then those theorems used induction. –  Thomas Andrews Aug 23 '12 at 16:12
1  
For example Bidit's solution reduces the problem to $1^n-1$. It might seem silly to have to prove $1^n=1$, but formally it has to be done with induction. Many teachers would let you take $1^n=1$ for granted though (unless they are specifically looking for induction arguments...) –  rschwieb Aug 23 '12 at 16:22

4 Answers 4

up vote 7 down vote accepted

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

share|improve this answer
    
So this is where I got so far from your help $$2^{3n}=(2^3)^n=8^n\equiv 1^n ~~~(\text{mod } 7)=1~~~(\text{mod } 7)$$ Which means $2^{3n} \equiv 1 ~~~(\text{mod } 7)$ ,right? Now what? –  Dan Hoise Aug 23 '12 at 16:20
    
So if $2^{3n}$, when divided by $7$ leaves a remainder of $1$, what remainder must $2^{3n}-1$ (which is, as you may have noticed, $1$ less than $2^{3n}$) leave when divided by 7? –  Bidit Acharya Aug 23 '12 at 16:24

HINT: $2^{3n}=8^n$, and for integers $n\ge2$ there is a well-known factorization of $x^n-y^n$.

share|improve this answer

$2^{3n} -1 = 8^n -1 = (7+1)^n -1 =$ (By Binomial theorem)$= C^n _0.7^n + C^{n}_{1} . 7^{n-1} + \dotsb + C^n_{n-1}7 + C^n_n -1 = 7.(C^n _0.7^{n-1} + C^{n}_{1} . 7^{n-2} + \dotsb + C^n_{n-1})$

share|improve this answer

Use Proof by induction.It's easy to show that if this holds for "n" ,then it holds for "n+1" and of course it's true for n=1

share|improve this answer
    
The question asked for a way not involving induction. –  Rick Decker Sep 17 '12 at 17:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.