# Divisibility 12

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

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

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

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

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

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

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

f) $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: . $(d)\;\;11 \,|\,12^n + 10$

We have: . $12^n + 10$

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

. . . $= \;\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]$

. . . $= \;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$

. . . $= \;\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: . $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:

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

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

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

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

. . $\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}}$

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

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

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

. . . . . . . . . . . . $\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:

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

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

$\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) $11|3^{n+3}-4^{4n+2}$

There exists k such that :
$3^{n+3}-4^{4n+2}=11k$, that is to say :
$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 :
$3^{(n+1)+3}-4^{4(n+1)+2}=11m$

--->

\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 $256=253+3=11 \cdot 23+3$

\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:

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

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

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

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

We can write f(n) in the form

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

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

$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

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

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

and this completes the proof. We have shown

$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) $3|4^{n}-1$
$4=1 (\bmod 3)$
So \begin{aligned} 4^n-1
&=1^n-1 (\bmod 3) \\
&=0 (\bmod 3) \end{aligned}

Quote:

b) $11|3^{n+3}-4^{4n+2}$
\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) $7|3^{2n+1}+2^{n+2}$
\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) $11|12^{n}+10$
\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:

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

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

This is false...

Because;

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

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

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

and

I think...

Quote:

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

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

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

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

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

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

$= 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

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

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

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

$= 7 x 3^2m + 1$

$= 7 x 9^m + 1$

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

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

$= 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

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

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

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

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

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

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

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

$= -[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

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

and

Thanks Anthony...;):)...
• Dec 23rd 2008, 01:27 PM
JaneBennet
$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}$

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

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