- Thread starter
- Admin
- #1

- Feb 14, 2012

- 3,682

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

- Thread starter anemone
- Start date

- Thread starter
- Admin
- #1

- Feb 14, 2012

- 3,682

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

$\displaystyle \begin{align*} S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m - r - 1} } \\ 5S &= 5\sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r-1} } \\ 5S &= \sum_{r = 0}^{m-1}{ {m\choose{r}} 5^{m-r} } \\ 5S &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}}5^{m-r} \cdot 1^r \right] } \\ 5S + 1 &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}} 5^{m-r} \cdot 1^r \right] } + 1 \\ 5S + 1 &= \sum_{r = 0}^{m - 1}{ \left[ {m\choose{r}} 5^{m - r} \cdot 1^r \right] } + {m\choose{m}} 5^0 \cdot 1^m \\ 5S + 1 &= \sum_{r = 0}^m{ {m\choose{r}} 5^{m - r} \cdot 1^r } \\ 5S + 1 &= \left( 5 + 1 \right) ^m \\ 5S + 1 &= 6^m \\ 5S &= 6^m - 1 \\ S &= \frac{6^m - 1}{5} \end{align*}$

So now we have to prove that $\displaystyle \begin{align*} \frac{6^m - 1}{5} \end{align*}$ is not prime if m is some odd integer greater than or equal to 5. I'm leaning towards induction...

Base step: m = 5

$\displaystyle \begin{align*} \frac{6^5 - 1}{5} &= \frac{7776 - 1}{5} \\ &= \frac{7775}{5} \\ &= 1555 \\ &= 5 \cdot 311 \end{align*}$

This is clearly not prime, so the base step is proven.

Now for the inductive step, assume that the statement is true for m = 2k + 1 (where k is another integer $\displaystyle \begin{align*} \geq 2 \end{align*}$, use this to prove the statement is true for m = 2k + 3.

So we assume $\displaystyle \begin{align*} \frac{6^{2k + 1} - 1}{5} \end{align*}$ is not prime, then

$\displaystyle \begin{align*} \frac{6^{2k + 3} - 1}{5} &= \frac{6^2 \cdot 6^{2k + 1} - 1}{5} \\ &= \frac{36 \cdot 6^{2k + 1} - 36 + 35}{5} \\ &= \frac{36 \left( 6^{2k + 1} - 1 \right) + 35}{5} \\ &= 36 \left( \frac{6^{2k + 1} - 1 }{5} \right) + 7 \end{align*}$

I'm not sure how to prove that this is not prime now...

Last edited by a moderator:

- Nov 4, 2013

- 428

$\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $

is not a prime number.

Notice that the given sum can be written as:

$${m\choose m}5^{m-1}-{m\choose m-1} 5^{m-2}+{m\choose m-2} 5^{m-3}-\cdots+{m\choose 1}$$

Since

$$(1+x)^m={m\choose 0}+{m\choose 1}x+{m\choose 2}x^2+\cdots +{m\choose m}x^m$$

$$\Rightarrow \frac{(1+x)^m}{x}=\frac{{m\choose 0}}{x}+{m\choose 1}+{m\choose 2}x+\cdots +{m\choose m}x^{m-1}$$

Substitute $x=-5$ to get,

$${m\choose 1}-{m\choose 2}\cdot 5+\cdots +{m\choose m}5^{m-1}=\frac{1}{5}+\frac{(1-5)^m}{-5}$$

The LHS is the summation (S) given in the question. Hence,

$$S=\frac{4^m+1}{5}=\frac{2^{2m}+1}{5}$$

For odd $m\geq 5$, $2^{2m}$ always ends with unit digit 4, hence, $2^{2m}+1$ is always divisible by 5 which proves that the given summation is not prime.

- Mar 31, 2013

- 1,309

I beg to disagree

Notice that the given sum can be written as:

$${m\choose m}5^{m-1}-{m\choose m-1} 5^{m-2}+{m\choose m-2} 5^{m-3}-\cdots+{m\choose 1}$$

Since

$$(1+x)^m={m\choose 0}+{m\choose 1}x+{m\choose 2}x^2+\cdots +{m\choose m}x^m$$

$$\Rightarrow \frac{(1+x)^m}{x}=\frac{{m\choose 0}}{x}+{m\choose 1}+{m\choose 2}x+\cdots +{m\choose m}x^{m-1}$$

Substitute $x=-5$ to get,

$${m\choose 1}-{m\choose 2}\cdot 5+\cdots +{m\choose m}5^{m-1}=\frac{1}{5}+\frac{(1-5)^m}{-5}$$

The LHS is the summation (S) given in the question. Hence,

$$S=\frac{4^m+1}{5}=\frac{2^{2m}+1}{5}$$

For odd $m\geq 5$, $2^{2m}$ always ends with unit digit 4, hence, $2^{2m}+1$ is always divisible by 5 which proves that the given summation is not prime.

- Nov 4, 2013

- 428

Ah yes, you are right.I beg to disagree

- Mar 31, 2013

- 1,309

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

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

smaller factor = $2^m - 2^{(m+1)/2} + 1$ ( as m is odd m+1 is even

> 5 for m >= 5 hence it is not prime

So now we have to prove that $\displaystyle \begin{align*} \frac{4^m + 1}{5} \end{align*}$ is not prime if m is some odd integer greater than or equal to 5. I'm leaning towards induction...

Base step: m = 5

$\displaystyle \begin{align*} \frac{4^5 + 1}{5} &= \frac{1024 + 1}{5} \\ &= \frac{1025}{5} \\ &= 205 \\ &= 5 \cdot 41 \end{align*}$

This is clearly not prime, so the base step is proven.

Now for the inductive step, assume that the statement is true for m = 2k + 1 (where k is another integer $\displaystyle \begin{align*} \geq 2 \end{align*}$, use this to prove the statement is true for m = 2k + 3.

So we assume $\displaystyle \begin{align*} \frac{4^{2k + 1} + 1}{5} \end{align*}$ is not prime, then

$\displaystyle \begin{align*} \frac{4^{2k + 3} + 1}{5} &= \frac{4^2 \cdot 4^{2k + 1} + 1}{5} \\ &= \frac{16 \cdot 4^{2k + 1} + 16 - 15}{5} \\ &= \frac{16 \left( 4^{2k + 1} + 1 \right) - 15}{5} \\ &= 16 \left( \frac{4^{2k + 1} + 1 }{5} \right) - 3 \end{align*}$

I'm still hitting a brick wall, can someone please help me finish?

- Mar 31, 2013

- 1,309

I do not think for proving

So now we have to prove that $\displaystyle \begin{align*} \frac{4^m + 1}{5} \end{align*}$ is not prime if m is some odd integer greater than or equal to 5. I'm leaning towards induction...

Base step: m = 5

$\displaystyle \begin{align*} \frac{4^5 + 1}{5} &= \frac{1024 + 1}{5} \\ &= \frac{1025}{5} \\ &= 205 \\ &= 5 \cdot 41 \end{align*}$

This is clearly not prime, so the base step is proven.

Now for the inductive step, assume that the statement is true for m = 2k + 1 (where k is another integer $\displaystyle \begin{align*} \geq 2 \end{align*}$, use this to prove the statement is true for m = 2k + 3.

So we assume $\displaystyle \begin{align*} \frac{4^{2k + 1} + 1}{5} \end{align*}$ is not prime, then

$\displaystyle \begin{align*} \frac{4^{2k + 3} + 1}{5} &= \frac{4^2 \cdot 4^{2k + 1} + 1}{5} \\ &= \frac{16 \cdot 4^{2k + 1} + 16 - 15}{5} \\ &= \frac{16 \left( 4^{2k + 1} + 1 \right) - 15}{5} \\ &= 16 \left( \frac{4^{2k + 1} + 1 }{5} \right) - 3 \end{align*}$

I'm still hitting a brick wall, can someone please help me finish?

But like you said,I do not think for proving

- Thread starter
- Admin
- #10

- Feb 14, 2012

- 3,682

@

@

@

- Mar 31, 2013

- 1,309

But like you said,

$(4^5+1)/5$ = 5 * 41

$(4^7+1)/5$ = 29 * 113

$(4^9+1)/5$ = 13 * 37 * 109

and we see that there is no commion factor