1
$\begingroup$

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)

$\endgroup$
3
  • 2
    $\begingroup$ Hint $2^{3n}=8^n$ $\endgroup$ Commented Aug 23, 2012 at 16:07
  • 1
    $\begingroup$ Implicitly, somewhere induction will be involved. You can prove it directly using theorems, but then those theorems used induction. $\endgroup$ Commented Aug 23, 2012 at 16:12
  • 1
    $\begingroup$ 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...) $\endgroup$
    – rschwieb
    Commented Aug 23, 2012 at 16:22

4 Answers 4

7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Dan Hoise
    Commented Aug 23, 2012 at 16:20
  • $\begingroup$ 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? $\endgroup$
    – user11470
    Commented Aug 23, 2012 at 16:24
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

$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})$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The question asked for a way not involving induction. $\endgroup$ Commented Sep 17, 2012 at 17:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .