# Divisibility 12

• Dec 20th 2008, 06:16 AM
Sea
Divisibility 12
Show that:

$\displaystyle n\in \mathbb{Z^{+}},$

a) $\displaystyle 3|4^{n}-1$

b) $\displaystyle 11|3^{n+3}-4^{4n+2}$

c) $\displaystyle 7|3^{2n+1}+2^{n+2}$

d) $\displaystyle 11|12^{n}+10$

e) $\displaystyle 17|3.5^{2n-1}+2^{3n-2}$

f) $\displaystyle 8|5n+2.3^{n-1}+1$
• Dec 20th 2008, 06:27 AM
running-gag
Hi

I did not read them all but most of them at least can be proved by induction
• Dec 20th 2008, 06:46 AM
Sea
Quote:

Originally Posted by running-gag
Hi

I did not read them all but most of them at least can be proved by induction

Thanks...but I cannot see the proves...:(...

Can you help me?...:)....
• Dec 20th 2008, 07:35 AM
Soroban
Hello, Sea!

Here's one of them ... a non-inductive proof.

Quote:

Show that: .$\displaystyle (d)\;\;11 \,|\,12^n + 10$

We have: .$\displaystyle 12^n + 10$

. . . $\displaystyle =\;(11+1)^n + (11-1)$

. . . $\displaystyle = \;\bigg[11^n \;+\; {n\choose n-1}11^{n-1} + {n\choose n-2}11^{n-2} + \hdots {n\choose 2}11^2 + {n\choose1}11\;+\;1\bigg] \;+\; \bigg[11 \;-\; 1\bigg]$

. . . $\displaystyle = \;11^n \;+\; {n\choose n-1}11^{n-1} + {n\choose n-2}11^{n-2} + \hdots {n\choose 2}11^2 + {n\choose1}11 + 11$

. . . $\displaystyle = \;\underbrace{11\,\bigg[11^{n-1} \;+\; {n\choose n-1}11^{n-2} + {n\choose n-2}11^{n-3} + \hdots {n\choose 2}11 + {n\choose1} + 1\bigg]}_{\text{a multiple of 11}}$

Therefore: .$\displaystyle 11\text{ divides }12^n + 10$

• Dec 20th 2008, 07:57 AM
Sea
Binomial theorem...:(...similar...a lot of question...a lot of binomial theorem...:(...very difficult...

But,

Thanks a million...;):)...
• Dec 20th 2008, 08:22 AM
Soroban
Hello, Sea!

I tried problem (e) by Induction.
. . It took more work than I anticipated . . .

Quote:

$\displaystyle e)\;\;17\,|\,3\cdot5^{2n-1}+2^{3n-2}$
We have .$\displaystyle S(n)\!:\;\;3\cdot5^{2n-1} + 2^{3n-2}\,\text{ is a multiple of 17.}$

Verify $\displaystyle S(1)\!:\;\;3\cdot5^1 + 2^1 \:=\:17$ . . . . True!

Assume $\displaystyle S(k)\!:\;\;3\cdot5^{2k-1} + 2^{3k-2} \:=\:17a\:\text{ for some integer }a$

Add .$\displaystyle \left[72\cdot5^{2k-1} + 7\cdot2^{3k-2}\right]$ to both sides:

. . $\displaystyle \underbrace{3\cdot5^{2k-1} \:{\color{blue}+ \:72\cdot5^{2k-1}}} + \underbrace{2^{3k-2} \:{\color{blue}+ \:7\cdot2^{3k-2}}} \;=\;17a \:{\color{blue}+ \:72\cdot5^{2k-1} + 7\cdot2^{3k-2}}$

. . $\displaystyle 3(1 + 24)\cdot5^{2k-1} + (1 + 7)\cdot2^{3k-2} \;=\; 17a + \overbrace{51\cdot5^{2k-1} + 21\cdot5^{2k-1}} + 7\cdot2^{3k-2}$

. . . . . . . .$\displaystyle 3\cdot5^2\cdot5^{2k-1} + 2^3\cdot2^{3k-2} \;=\;17a + 51\cdot5^{2k-1} + 7\underbrace{\left(3\cdot5^{2k-1} + 2^{3k-2}\right)}_{\text{This is }17a}$

. . . . . . . . . . . . $\displaystyle 3\cdot5^{2k+1} + 2^{3k+1} \;=\;17a + 51\cdot5^{2k-1} + 7(17a)$

. . . . . . . . . . . . $\displaystyle \underbrace{3\cdot5^{2k+1} + 2^{3k+1}}_{\text{This is }S(k+1)}\;=\; \underbrace{17\left(a + 3\cdot5^{2k-1} + 7a\right)}_{\text{This is a multiple of 17}}$

The inductive proof is compete.

• Dec 20th 2008, 10:16 AM
Moo
Hello,
Quote:

Originally Posted by Sea
Show that:

$\displaystyle n\in \mathbb{Z^{+}},$

a) $\displaystyle 3|4^{n}-1$

$\displaystyle \sum_{k=0}^{n-1} 4^k=\frac{4^n-1}{4-1}=\frac{4^n-1}{3}$
The LHS is an integer, hence the RHS has to be integer.
• Dec 20th 2008, 10:32 AM
Moo
If you've studied congruences, it would be much easier ^^'
Quote:

Originally Posted by Sea
b) $\displaystyle 11|3^{n+3}-4^{4n+2}$

There exists k such that :
$\displaystyle 3^{n+3}-4^{4n+2}=11k$, that is to say :
$\displaystyle 4^{4n+2}=-11k+3^{n+3}$ (inductive hypothesis - you'll have to check for n=0)

The purpose is to prove that there exists an integer m such that :
$\displaystyle 3^{(n+1)+3}-4^{4(n+1)+2}=11m$

--->

\displaystyle \begin{aligned} 4^{4(n+1)+2} &=4^{4n+2+4} \\ &=4^4 \cdot 4^{4n+2} \\ &=4^4 \cdot \left(11k+3^{n+3}\right) \\ &=\underbrace{4^4 \cdot 11k}_{=11k'}+4^4 \cdot 3^{n+3} \\ &=11k'+256 \cdot 3^{n+3} \end{aligned}

Note that $\displaystyle 256=253+3=11 \cdot 23+3$

\displaystyle \begin{aligned} 4^{4(n+1)+2} &=\underbrace{11k'+11 \cdot (253 \cdot 3^{n+3})}_{=11k''}+3 \cdot 3^{n+3} \\ &=11k''+3^{n+4} \end{aligned}

And you're done.
• Dec 21st 2008, 04:16 AM
Sea
Quote:

Originally Posted by Sea
Show that:

$\displaystyle n\in \mathbb{Z^{+}},$

c) $\displaystyle 7|3^{2n+1}+2^{n+2}$

We must show$\displaystyle f(n) = 3^{(2n+1)} + 2^{(n+2)} = 0 (mod 7)$

$\displaystyle f(n) = 3 \times 9^n + 4 \times 2^n = 0 (mod 7)$

We can write f(n) in the form

$\displaystyle f(n) = 3 \times (7 + 2)^n + 4 \times 2^n$

$\displaystyle 3[7^n + C(n,1)7^{(n-1)}.2 + .... + 2^n] + 4 \times 2^n$

$\displaystyle 3 \times M(7) + 3 \times 2^n + 4 \times 2^n$

where M(7) means 'is a multiple of 7'

The first term = 0 (mod 7) so now we are reduced to finding

$\displaystyle 3 \times 2^n + 4 \times 2^n$

This can be written $\displaystyle 2^n[3 + 4] = 2^n \times 7 = 0 (mod 7)$

and this completes the proof. We have shown

$\displaystyle 3^{(2n+1)} + 2^{(n+2)} = 0 (mod 7)$

i.e., the expression on the left is a multiple of 7

and

Thanks Anthony...;):)...
• Dec 21st 2008, 07:32 AM
Moo
Gaaaaah T.T so you know congruences !

Quote:

a) $\displaystyle 3|4^{n}-1$
$\displaystyle 4=1 (\bmod 3)$
So \displaystyle \begin{aligned} 4^n-1 &=1^n-1 (\bmod 3) \\ &=0 (\bmod 3) \end{aligned}

Quote:

b) $\displaystyle 11|3^{n+3}-4^{4n+2}$
\displaystyle \begin{aligned} 3^{n+3}-4^{4n+2} &= {\color{red}27} \cdot 3^n-{\color{red}16} \cdot ({\color{red}4^4})^n \\ &=5 \cdot 3^n-5 \cdot 3^n (\bmod 11) \\ &=0 (\bmod 11) \end{aligned}

Quote:

c) $\displaystyle 7|3^{2n+1}+2^{n+2}$
\displaystyle \begin{aligned} 3^{2n+1}+2^{n+2} &=3 \cdot ({\color{red}3^2})^n+{\color{red}4} \cdot 2^n \\ &=3 \cdot 2^n-3 \cdot 2^n (\bmod 7) \\ &=0 (\bmod 7) \end{aligned}

Quote:

d) $\displaystyle 11|12^{n}+10$
\displaystyle \begin{aligned} {\color{red}12}^n+{\color{red}10} &=1^n+(-1) (\bmod 11) \\ &=0 (\bmod 11) \end{aligned}

(the red parts are changed into an equivalent modulo ..)
• Dec 21st 2008, 08:07 AM
Sea
I know congruences...:)...

I understand

and...

Thanks a million...;):)...
• Dec 21st 2008, 10:05 AM
Sea
And

Quote:

Originally Posted by Sea
Show that:

$\displaystyle n\in \mathbb{Z^{+}},$

f) $\displaystyle 8|5n+2.3^{n-1}+1$

This is false...

Because;

$\displaystyle n=2 \Rightarrow 5n+2.3^{n-1}+1=5\times 2+2\times3^{2-1}+1=10+6+1=17$

But $\displaystyle 8 \nmid 17$
• Dec 21st 2008, 10:57 PM
Sea
Quote:

f)$\displaystyle 5n + 2 x 3^{(n-1)} + 1$
This is false

and

I think...

Quote:

$\displaystyle 8|5^n + 2 x 3^{(n-1)} + 1$
This is true...

$\displaystyle f(n) = 5^n + 2 x 3^{(n-1)} + 1$

Now if n=2 we get 25 + 2 x 3 + 1 = 32 = M(8)

and if n=3 we get 125 + 2 x 9 + 1 = 144 = M(8)

and so we must prove $\displaystyle f(n) = 5^n + 2 x 3^{(n-1)} + 1 = 0 (mod 8)$

It will be more convenient to use f(n+1) but this does not alter the proof

$\displaystyle f(n+1) = 5^{(n+1)} + 2 x 3^n + 1$

$\displaystyle = 5 x 5^n + 2 x 3^n + 1$

$\displaystyle = 5 x (8 - 3)^n + 2 x 3^n + 1$

$\displaystyle = 5 x [8^n + M(8) +- 3^n] + 2 x 3^n + 1$

$\displaystyle = 5 x [8^n + M(8)] +- 5 x 3^n + 2 x 3^n + 1$

We can ignore the first term as it will be divisible by 8 and look at

$\displaystyle 5 x 3^n + 2 x 3^n + 1$ if n is even .......(1)

and $\displaystyle -5 x 3^n + 2 x 3^n + 1$ if n is odd .......(2)

For (1) we have $\displaystyle 3^n[5 + 2] + 1$ and putting n = 2m to make it even

$\displaystyle = 7 x 3^2m + 1$

$\displaystyle = 7 x 9^m + 1$

$\displaystyle = 7 x (8 + 1)^m + 1$

$\displaystyle = 7 x (8^m + M(8) + 1) + 1$

$\displaystyle = 7 x (8^m + M(8)] + 7 + 1$

= M(8) + 8 = 0 (mod 8) so OK if n is even

For (2) we have n odd and write it 2m+1 so we have

$\displaystyle = 3^{(2m+1)}.[-5 + 2] + 1$

$\displaystyle = 3^{(2m+1)}.[-3] + 1$

$\displaystyle = -3^{(2m+2)}+ 1$

$\displaystyle = -9^{(m+1)} + 1$

$\displaystyle = -(8+1)^{(m+1)} + 1$

$\displaystyle = -[8^{(m+1)} + M(8) + 1] + 1$

$\displaystyle = -[8^{(m+1)} + M(8)] - 1 + 1$

$\displaystyle = -[8^{(m+1)} + M(8)] = 0 (mod 8)$ so OK if n is odd

and so for n either even or odd we have shown

$\displaystyle 5^n + 2 x 3^{(n-1)} + 1 = 0 (mod 8)$

and

Thanks Anthony...;):)...
• Dec 23rd 2008, 01:27 PM
JaneBennet
$\displaystyle 5^n=(8-3)^n\equiv(-3)^n\pmod{8}\equiv\begin{cases}-3\pmod{8}\ \mbox{if$n$is odd}\\ 1\pmod{8}\ \mbox{if$n$is even}\end{cases}$

$\displaystyle 2\times3^{n-1}=2\times(4-1)^{n-1}\equiv2\times(-1)^{n-1}\pmod{8}$

Hence, if $\displaystyle n$ is odd, $\displaystyle 5^n+2\times3^{n-1}+1\equiv-3+2+1=0\pmod{8}$ and if $\displaystyle n$ is even, $\displaystyle 5^n+2\times3^{n-1}+1\equiv1-2+1=0\pmod{8}.$